struct thread {
  int        sp;                /* curent stack pointer */
  char stack[STACK_SIZE];       /* the thread's stack */
  int        state;             /* running, runnable, waiting */
};

static thread_t all_thread[MAX_THREAD];

current_thread = &all_thread[0];
current_thread->state = RUNNING;

	.text

/* Switch from current_thread to next_thread. Make next_thread
 * the current_thread, and set next_thread to 0.
 * Use eax as a temporary register, which should be caller saved.
 */
	.globl thread_switch
thread_switch:
	/* YOUR CODE HERE */

	# We are running on current_thread's stack, push all registers to save
	# attention: first time we call thread_switch, we actually do not run on current_thread's stack
	# because current_thread point to all_thread[0], and we just fake it is running, but it does not matter
	pushal

	# Save current thread's stack pointer
	movl current_thread, %eax
	movl %esp, (%eax)

	# Switch stacks to next thread
	movl next_thread, %eax
	movl (%eax), %esp #point to sp'value, if is every thread's first-time-running, it already leaves the space to save registers

	# Set current_thread to next_thread 
	movl %eax, current_thread 
	# Set next_thread to 0
	movl $0, next_thread

	# Pop next thread's registers from the stack into the appropriate registers
	popal

	// exec current_thread
	ret				/* pop return address from stack */

(gdb) symbol-file _uthread
Load new symbol table from "/Users/kaashoek/classes/6828/xv6/_uthread"? (y or n) y
Reading symbols from /Users/kaashoek/classes/6828/xv6/_uthread...done.
(gdb) b thread_switch
Breakpoint 1 at 0x204: file uthread_switch.S, line 9.
(gdb) c

(gdb) print /x *next_thread
$1 = {sp = 0x4d48, stack = {0x0 , 0x61, 0x1, 0x0, 0x0}, state = 0x1}

???

Exercise 1: 实现kern/pmap.c的mmio_map_region函数，在kern/lapic.c的lapic_init中查看mmio_map_region函数的使用情况。需要做完Exercise 2之后才能通过对于mmio_map_region的测试。

//
// 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);
}

Exercise 2. 阅读boot_aps()和mp_main()，以及kern/mpentry.S，了解APs启动过程的control flow transfer。修改kern/pmap.c的page_init()实现，避免在MPENTRY_PADDR分配页，保证APs启动代码的拷贝、运行安全。

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];
	}
}

Question 1. 比较kern/mpentry.S和boot/boot.S。请记住：kern/mpentry.S被编译和链接后是运行在KERNBASE之上的，就像其他程序一样。设计MPBOOTPHYS宏的目的是什么？为什么boot/boot.S不需要它？

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中标识符的物理地址是直接由链接地址确定的。

Exercise 3. 修改kern/pmap.c的mem_init_mp()函数，将每个cpu的栈映射到KSTACKTOP以下部分，参考inc/memlayout.h。每个栈的大小是KSTKSIZE+KSTKGAP字节。

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;
	}
}

Exercise 4. kern/trap.c的trap_init_percpu()函数初始化了BSP的TSS和TSS描述符，修改这部分代码，使之支持所有cpu。提示：新代码将不会使用到全局变量ts。

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);
}

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

???

Exercise 5: 完成以上任务。

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

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

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

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

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();
}

Question 3.env_run()修改了参数e的成员状态之后就会调用lcr3切换到进程的页目录，这时候内存管理单元MMU所使用的寻址上下文立即发生了变化。在地址切换前后，为什么参数e仍能够被引用？

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

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

// 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();
}

// 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;
}

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

???

Exercise 7.完成以上内容。jos的envid2env()函数可以根据id获取对应的进程结构，并且传入0可以获取当前进程。

// 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;
}

// 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;
}

// 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;
}

// 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;
}

// 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;
}

Challenge! 添加系统调用以读取某个进程的所有重要状态。实现一个用户程序，该程序fork一个子进程，运行该程序（即循环迭代sys_yield()），然后获取子进程的完整snapshot或checkpoint，然后执行子程序一段时间。最后，恢复子进程在检查点的状态，然后继续执行子进程。这相当于从某个中间状态replaying子进程的执行。使用sys_cgetc()或readline()函数保证子进程与用户之间进行交互，以便用户可以查看和改变其内部状态。确保子进程在检查点处恢复执行时，子进程"forget"了之前任何发生在检查点之后的内容。

???

Exercise 8. 实现sys_env_set_pgfault_upcall系统调用，该系统调用用于注册用户程序触发页错误时的处理函数入口。

// 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;
}

Exercise 9. 完成kern/trap.c的page_fault_handler函数，该函数主要负责处理页错误，如果触发页错误的是用户进程，则检查页错误处理程序是否已设置、页错误处理程序地址是否合法、异常栈指针是否越界、是否递归触发页错误、是否已为异常栈分配物理页，然后在异常栈上存储UTrapframe，将栈指针指向异常栈，并跳转执行用户级页错误处理程序入口。

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);
}

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

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

#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

Exercise 11. 完成lib/pgfault.c的set_pgfault_handler()。该函数主要完成页错误处理程序的注册工作。如果是第一次注册，则申请分配并映射异常栈。

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;
}

// 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);
}

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

???

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

// 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;
}

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

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; 
}

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

???

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

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

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

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

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。

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();
	}
}

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;
}

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;
}

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;
}

Challenge! 为何ipc_send需要循环尝试发送?

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

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)的幂级数。

Challenge! 阅读 Improving IPC by Kernel Design (http://dl.acm.org/citation.cfm?id=168633)，改进jos的IPC效率。可扩展系统调用接口。

struct lock { int locked; }
    acquire(lk) {
      while(1){
        if(lk->locked == 0){ // A
          lk->locked = 1;    // B
          return;
        }
      }
    }

acquire(lk){
    while(1){
      if(xchg(&lk->locked, 1) == 0){
        break
      }
    }
  }

//see in spinlock.c
// Record the current call stack in pcs[] by following the %ebp chain.
void
getcallerpcs(void *v, uint pcs[])
{
  uint *ebp;
  int i;

  ebp = (uint*)v - 2;
  for(i = 0; i < 10; i++){
    if(ebp == 0 || ebp < (uint*)KERNBASE || ebp == (uint*)0xffffffff)
      break;
    pcs[i] = ebp[1];     // saved %eip
    ebp = (uint*)ebp[0]; // saved %ebp
  }
  for(; i < 10; i++)
    pcs[i] = 0;
}

t-A: calls insert() on bucket 1 (key = 6, 6 % NBUCKETS = 1)
t-B: calls insert() on bucket 1 (key = 21, 21 % NBUCKETS = 1)
...
...
t-A: executes e->next = n
t-B: executes e->next = n
t-A: executes *p = e
t-B: executes *p = e

互斥锁的使用：
pthread_mutex_t lock;     // declare a lock
pthread_mutex_init(&lock, NULL);   // initialize the lock
pthread_mutex_lock(&lock);  // acquire lock
pthread_mutex_unlock(&lock);  // release lock

static 
void put(int key, int value)
{
  pthread_mutex_lock(&lock);  // acquire lock

  int i = key % NBUCKET;
  insert(key, value, &table[i], table[i]);

  pthread_mutex_unlock(&lock);  // release lock
}

$ gcc -g -O2 ph.c -pthread
$ ./a.out 2

#include <stdlib.h>
#include <unistd.h>
#include <stdio.h>
#include <assert.h>
#include <pthread.h>
#include <sys/time.h>

#define SOL
#define NBUCKET 5
#define NKEYS 100000

struct entry {
  int key;
  int value;
  struct entry *next;
};
struct entry *table[NBUCKET];
int keys[NKEYS];
int nthread = 1;
volatile int done;

pthread_mutex_t lock;     // declare a lock

double
now()
{
 struct timeval tv;
 gettimeofday(&tv, 0);
 return tv.tv_sec + tv.tv_usec / 1000000.0;
}

static void
print(void)
{
  int i;
  struct entry *e;
  for (i = 0; i < NBUCKET; i++) {
    printf("%d: ", i);
    for (e = table[i]; e != 0; e = e->next) {
      printf("%d ", e->key);
    }
    printf("\n");
  }
}

static void 
insert(int key, int value, struct entry **p, struct entry *n)
{
  struct entry *e = malloc(sizeof(struct entry));
  e->key = key;
  e->value = value;
  e->next = n;
  *p = e;
}

static 
void put(int key, int value)
{
  pthread_mutex_lock(&lock);  // acquire lock

  int i = key % NBUCKET;
  insert(key, value, &table[i], table[i]);

  pthread_mutex_unlock(&lock);  // release lock
}

static struct entry*
get(int key)
{
  struct entry *e = 0;
  for (e = table[key % NBUCKET]; e != 0; e = e->next) {
    if (e->key == key) break;
  }
  return e;
}

static void *
thread(void *xa)
{
  long n = (long) xa;
  int i;
  int b = NKEYS/nthread;
  int k = 0;
  double t1, t0;

  //  printf("b = %d\n", b);
  t0 = now();
  for (i = 0; i < b; i++) {
    // printf("%d: put %d\n", n, b*n+i);
    put(keys[b*n + i], n);
  }
  t1 = now();
  printf("%ld: put time = %f\n", n, t1-t0);

  // Should use pthread_barrier, but MacOS doesn't support it ...
  __sync_fetch_and_add(&done, 1);
  while (done < nthread) ;

  t0 = now();
  for (i = 0; i < NKEYS; i++) {
    struct entry *e = get(keys[i]);
    if (e == 0) k++;
  }
  t1 = now();
  printf("%ld: lookup time = %f\n", n, t1-t0);
  printf("%ld: %d keys missing\n", n, k);
  return NULL;
}

int
main(int argc, char *argv[])
{
  pthread_mutex_init(&lock, NULL);   // initialize the lock

  pthread_t *tha;
  void *value;
  long i;
  double t1, t0;

  if (argc < 2) {
    fprintf(stderr, "%s: %s nthread\n", argv[0], argv[0]);
    exit(-1);
  }
  nthread = atoi(argv[1]);
  tha = malloc(sizeof(pthread_t) * nthread);
  srandom(0);
  assert(NKEYS % nthread == 0);
  for (i = 0; i < NKEYS; i++) {
    keys[i] = random();
  }
  t0 = now();
  for(i = 0; i < nthread; i++) {
    assert(pthread_create(&tha[i], NULL, thread, (void *) i) == 0);
  }
  for(i = 0; i < nthread; i++) {
    assert(pthread_join(tha[i], &value) == 0);
  }
  t1 = now();
  printf("completion time = %f\n", t1-t0);
}

#include "types.h"
#include "stat.h"
#include "user.h"

void periodic();

int
main(int argc, char *argv[])
{
  int i;
  printf(1, "alarmtest starting\n");
  alarm(10, periodic);
  for(i = 0; i < 50*500000; i++){
    if((i++ % 500000) == 0)
      write(2, ".", 1);
  }
  exit();
}

void
periodic()
{
  printf(1, "alarm!\n");
}

int
sys_alarm(void)
{
   int ticks;
   void (*handler)();

   if(argint(0, &ticks) < 0)
      return -1;
   if(argptr(1, (char**)&handler, 1) < 0)
      return -1;
    proc->alarmticks = ticks;
    proc->alarmhandler = handler;
    return 0;
}

$ alarmtest
alarmtest starting
.....alarm!
....alarm!
.....alarm!
......alarm!
.....alarm!
....alarm!
....alarm!
......alarm!
.....alarm!
...alarm!
...$

// Per-process state
struct proc {
  uint sz;                     // Size of process memory (bytes)
  pde_t* pgdir;                // Page table
  char *kstack;                // Bottom of kernel stack for this process
  enum procstate state;        // Process state
  int pid;                     // Process ID
  struct proc *parent;         // Parent process
  struct trapframe *tf;        // Trap frame for current syscall
  struct context *context;     // swtch() here to run process
  void *chan;                  // If non-zero, sleeping on chan
  int killed;                  // If non-zero, have been killed
  struct file *ofile[NOFILE];  // Open files
  struct inode *cwd;           // Current directory
  char name[16];               // Process name (debugging)

  //add by jianzzz, for alarm...
  int alarmticks;
  int alarmticked;
  void (*alarmhandler)();
};

//在进程表中寻找slot，成功的话更改进程状态embryo和pid，并初始化进程的内核栈
static struct proc*
allocproc(void)
{
  ...
found:
  ...
  //add by jianzzz,for alarm
  p->alarmticks = 0;
  p->alarmticked = 0;
  p->alarmhandler = 0;
  return p;
}

//see in trap.c
void
trap(struct trapframe *tf)
{
  ...
  switch(tf->trapno){
  case T_IRQ0 + IRQ_TIMER:
    if(cpunum() == 0){
      acquire(&tickslock);
      ticks++;
      wakeup(&ticks);
      release(&tickslock);
    }
    lapiceoi();

    if(proc && (tf->cs & 3) == 3){ 
      //(*proc->alarmhandler)();  
      proc->alarmticked += 1;
      if(proc->alarmticked == proc->alarmticks) {
        proc->alarmticked = 0;
        tf->esp -= 4;
        *(uint *) tf->esp = tf->eip;
        tf->eip = (uint) proc->alarmhandler;
      } 
    }

    break;
  ...
}

//kern/env.c
struct Env *envs = NULL;		// All environments
struct Env *curenv = NULL;		// The current env
static struct Env *env_free_list;	// Free environment list

//inc/env.h
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

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

ENV_FREE：表明Env数据结构不活跃，位于env_free_list中。
ENV_RUNNABLE：表明Env数据结构所代表的环境正等待处理器执行。
ENV_RUNNING：表明Env数据结构所代表的环境正被执行。
ENV_NOT_RUNNABLE：表明Env数据结构所代表的环境是活跃的，但还不能执行，比如它正在等待其他环境的interprocess communication (IPC)。
ENV_DYING：表明Env数据结构所代表的环境是一个zombie。下一次trap到内核的时候，zombie环境将被释放。

Exercise 1.修改kern/pmap.c中mem_init()函数，分配并映射envs数组（NENV instances），参考pages数组的分配和映射。pages数组基址映射到UPAGES虚拟地址，envs数组基址映射到UENVS虚拟地址，两者的二级页表项权限都是用户只读，用户环境不能修改数组本身。顺利完成的话将通过check_kern_pgdir()检查。

//pmap.c
                                   ...
	//////////////////////////////////////////////////////////////////////
	// Make 'envs' point to an array of size 'NENV' of 'struct Env'.
	// LAB 3: Your code here.
	envs = (struct Env*)boot_alloc(NENV*sizeof(struct Env));
	memset(envs,0,NENV*sizeof(struct Env)); 
                                   ...
	//////////////////////////////////////////////////////////////////////
	// Map the 'envs' array read-only by the user at linear address UENVS
	// (ie. perm = PTE_U | PTE_P).
	// Permissions:
	//    - the new image at UENVS  -- kernel R, user R
	//    - envs itself -- kernel RW, user NONE
	// LAB 3: Your code here.
	boot_map_region(kern_pgdir,UENVS,PTSIZE,PADDR(envs),PTE_U | PTE_P);
                                   ...

Exercise 2.在kern/env.c中完成以下函数：
env_init()：初始化进程数据结构数组，将所有数据结构加到env_free_list上。调用env_init_percpu函数为特权级别0(内核)和特权级别3(用户)将段式硬件配以单独的段。
env_setup_vm()：分配页目录，初始化进程的内核部分地址空间。
region_alloc()：分配和映射物理空间。
load_icode()：解析ELF二进制镜像，加载进新进程的地址空间。
env_create()：通过env_alloc分配一个新进程，调用load_icode加载ELF二进制镜像。
env_run()：在用户模式下执行新进程。

//env.c
void
env_init(void)
{
	// Set up envs array
	// LAB 3: Your code here.
	env_free_list = NULL;  
    int i;  
    for( i = NENV -1; i>=0; i--){  
		envs[i].env_status = ENV_FREE;
        envs[i].env_id = 0;  
        envs[i].env_link = env_free_list;  
        env_free_list = &envs[i];  
    }  
	// Per-CPU part of the initialization
	env_init_percpu();
}

//init.c
ENV_CREATE(user_hello, ENV_TYPE_USER);

//env.h
#define ENV_PASTE3(x, y, z) x ## y ## z

#define ENV_CREATE(x, type)						\
	do {								\
		extern uint8_t ENV_PASTE3(_binary_obj_, x, _start)[];	\
		env_create(ENV_PASTE3(_binary_obj_, x, _start),		\
			   type);					\
	} while (0)


//env.c
void
env_create(uint8_t *binary, enum EnvType type)
{
	// LAB 3: Your code here.
	struct Env *newEnv;
	//Allocates a new env 
	int i = env_alloc(&newEnv,0);
	if(i<0) panic("env_create");
	//loads the named elf binary into
	load_icode(newEnv,binary);
	//set env_type
	newEnv->env_type = type;
}