// In kern/pmap.c, mmio_map_region():
// Your code here:
size = ROUNDUP(size, PGSIZE);
if (base + size > MMIOLIM) {
    // reservation overflog MMIOLIM
    panic("reservation bytes overflows!");
}

// use boot_map_region to map [pa, pa + size) to [base, base + size)
boot_map_region(kern_pgdir, base, size, pa, PTE_W | PTE_PCD | PTE_PWT);

// update base and return
uintptr_t saved_base = base;
base += size;
return (char *)saved_base;

// panic("mmio_map_region not implemented");

// In kern/pmap.c, page_init():
// code MODIFIED
size_t i;

// initialize from page 1 to page npages_basemem - 1
// set pp_ref to 0, set pp_link to last page_free_list
// and then update page_free_list

// Lab 4: remove page at MPENTRY_PADDR
size_t mp_entry_page = PGNUM(MPENTRY_PADDR);

for(i = 1 ; i < npages_basemem ; i++) {
    if (i == mp_entry_page) {
        continue;
    }
    pages[i].pp_ref = 0;
    pages[i].pp_link = page_free_list;
    page_free_list = &pages[i];
}

// LAB 4: Your code here:
size_t i;

for (i = 0; i < NCPU; i++) {
    // traverser through 0 to NCPU to use boot_map_region to map
    // per-CPU's kernel stack to corresponding va
    uintptr_t kstacktop_i = KSTACKTOP - i * (KSTKSIZE + KSTKGAP);
    boot_map_region(kern_pgdir, kstacktop_i - KSTKSIZE, KSTKSIZE,
                    PADDR(percpu_kstacks[i]), PTE_W | PTE_P);
}

// LAB 4: Your code here:
// trap_init_percpu() is called by all CPUs
// set esp0 and ss0 of task state segment to provide
// per-CPU's kernel stack access
thiscpu->cpu_ts.ts_esp0 = (uintptr_t)percpu_kstacks[cpunum()];
thiscpu->cpu_ts.ts_ss0  = GD_KD;
// set IO map base address to prevent unauthorized environments
// this line works together as we'll set TSS segment limit later
// so all ports in address space have no corresponding IOPB
thiscpu->cpu_ts.ts_iomb = sizeof(struct Taskstate);

// set TSS in gdt
// 0 means RPL and sd_s = 0 means system segment
gdt[(GD_TSS0 >> 3) + cpunum()] = SEG16(STS_T32A, (uint32_t)(&(thiscpu->cpu_ts)),
                                       sizeof(struct Taskstate) - 1, 0);
gdt[(GD_TSS0 >> 3) + cpunum()].sd_s = 0;

// Load TSS selector
ltr(GD_TSS0 + (cpunum() << 3));

// load the IDT
lidt(&idt_pd);

// In i386_init():
// Acquire the big kernel lock before waking up APs
// Your code here:
lock_kernel();

// In 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 the kernel and start running enviroments
lock_kernel();
sched_yield();

// In trap():
// Trapped from user mode.
// Acquire the big kernel lock before doing any
// serious kernel work.
// LAB 4: Your code here.
lock_kernel();

// In env_run():
// address space switch
// reference from inc/x86.h
lcr3(PADDR(e->env_pgdir));
// release kernel lock here
unlock_kernel(); // newly added code
// drop into user mode
env_pop_tf(&(e->env_tf));

// In kern/sched.c, sched_yield():
// LAB 4: Your code here.
// get index from current CPU's env
size_t env_index;
// set curenv_flag to default true
int curenv_flag = true;

size_t i;
if (thiscpu->cpu_env == NULL) {
    // no previous running environment
    // start at beginning of envs array
    i         = 0;
    env_index = NENV - 1;
    // mark curenv_flag as true
    curenv_flag = false;
} else {
    // start at previous running environment
    env_index = ENVX(thiscpu->cpu_env->env_id);
    // NB: don't mess with code order here, must first retrieve
    // env_index then increment
    i = (env_index == NENV - 1) ? 0 : env_index + 1;
}
// traverse through envs list to find first ENV_RUNNABLE
// env
for (; i != env_index; i = ((i == NENV - 1) ? 0 : i + 1)) {
    if (envs[i].env_status == ENV_RUNNABLE) {
        // found, set idle and break from loop
        idle = &envs[i];
        break;
    }
}

// if idle is NULL and curenv_flag is true,
// means no envs are runnable and last previous running env is ENV_RUNNING
// check if last previous environment is ENV_RUNNING,
// if so, choose it.
if (!idle && curenv_flag && envs[env_index].env_status == ENV_RUNNING) {
    idle = &envs[env_index];
}

if (idle) {
    // idle env choosed, run it directly
    env_run(idle);
} else {
    // failed to choose idle env, halt CPU
    // sched_halt never returns
    sched_halt();
}

// In kern/syscall.c, syscall():
// code added:
case SYS_yield:
    // call sys_yield
    sys_yield();
    break;

// In kern/init.c, i386_init():
// code modified:
#if defined(TEST)
    // Don't touch -- used by grading script!
    ENV_CREATE(TEST, ENV_TYPE_USER);
#else
    // Touch all you want.
    // create three user_yield
    // code MODIFIED here
    ENV_CREATE(user_yield, ENV_TYPE_USER);
    ENV_CREATE(user_yield, ENV_TYPE_USER);
    ENV_CREATE(user_yield, ENV_TYPE_USER);
#endif    // TEST*

// In sys_exofork():
// 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.
    // get env_id of current environment
    envid_t parent_id = thiscpu->cpu_env->env_id;

    // use env_alloc to create new environment and
    // do some basic setup(status and register set)
    struct Env *env = NULL;
    if (env_alloc(&env, parent_id) < 0) { panic("sys_exofork failed!"); }
    env->env_status = ENV_NOT_RUNNABLE;
    env->env_tf     = thiscpu->cpu_env->env_tf;

    // do the trick to set eax register of newly
    // alloc environment to 0
    env->env_tf.tf_regs.reg_eax = 0;

    // return new environment's ID
    return env->env_id;

    // panic("sys_exofork not implemented");
}

// In sys_env_set_status():
// 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: Use the 'envid2env' function from kern/env.c to translate an
    // envid to a struct Env.
    // You should set envid2env's third argument to 1, which will
    // check whether the current environment has permission to set
    // envid's status.

    // LAB 4: Your code here.
    // check status passed in
    if (status != ENV_RUNNABLE && status != ENV_NOT_RUNNABLE) {
        // invalid status
        return -E_INVAL;
    }

    struct Env *env;
    // call envid2env to translate envid passed in
    if (envid2env(envid, &env, true) < 0) {
        // bad environment
        return -E_BAD_ENV;
    }
    // set status
    env->env_status = status;

    // panic("sys_env_set_status not implemented");

    return 0;
}

// In sys_page_alloc():
// 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) {
    // Hint: This function is a wrapper around page_alloc() and
    //   page_insert() from kern/pmap.c.
    //   Most of the new code you write should be to check the
    //   parameters for correctness.
    //   If page_insert() fails, remember to free the page you
    //   allocated!

    // LAB 4: Your code here.
    struct Env *env;
    // check and get env
    if (envid2env(envid, &env, true) < 0) {
        // envid not exist or permission error
        return -E_BAD_ENV;
    }

    // check va
    if ((uintptr_t)va >= UTOP || PGOFF(va) != 0) {
        // va above UTOP or va is not page-aligned
        return -E_INVAL;
    }

    // check perm
    if ((perm & (~PTE_SYSCALL)) || !(perm & PTE_U) || !(perm & PTE_P)) {
        // invalid perm
        return -E_INVAL;
    }

    // allocate page and then insert it
    // check if out of memory
    struct PageInfo *page;
    if ((page = page_alloc(ALLOC_ZERO)) == NULL) {
        // failed to allocate page
        return -E_NO_MEM;
    }
    if (page_insert(env->env_pgdir, page, va, perm) < 0) {
        // page table couldn't be allocated
        // free ununsed page
        page_free(page);
        return -E_NO_MEM;
    }

    // panic("sys_page_alloc not implemented");

    // page successfully allocated
    return 0;
}

// In sys_page_map():
// 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) {
    // Hint: This function is a wrapper around page_lookup() and
    //   page_insert() from kern/pmap.c.
    //   Again, most of the new code you write should be to check the
    //   parameters for correctness.
    //   Use the third argument to page_lookup() to
    //   check the current permissions on the page.

    // LAB 4: Your code here.
    struct Env *srcenv, *dstenv;
    // check environment
    if ((envid2env(srcenvid, &srcenv, true) < 0) ||
        (envid2env(dstenvid, &dstenv, true) < 0)) {
        // srcenvid or dstenvid doesn't exist or
        // caller doesn't have permissions
        return -E_BAD_ENV;
    }

    // check srcva and dstva about address and page-aligned
    // get srcenv and dstenv
    if (((uintptr_t)srcva >= UTOP) || ((uintptr_t)dstva >= UTOP) ||
        (PGOFF(srcva) != 0) || (PGOFF(dstva) != 0)) {
        // addresses above UTOP or addresses not page_aligned
        return -E_INVAL;
    }

    struct PageInfo *srcpage;
    pte_t *          scrpte_ptr;
    // use page look up to get source page and corresponding pte_t *
    if ((srcpage = page_lookup(srcenv->env_pgdir, srcva, &scrpte_ptr)) ==
        NULL) {
        // srcva not mapped in srcenvid's address space
        return -E_INVAL;
    }

    // check perm passed in
    if ((perm & (~PTE_SYSCALL)) || !(perm & PTE_U) || !(perm & PTE_P)) {
        // invalid perm
        return -E_INVAL;
    }

    // check if srcva is writable if perm has PTE_W
    if ((perm & PTE_W) && (!((*scrpte_ptr) & PTE_W))) {
        // perm has PTE_W while srcva ISN'T writable
        return -E_INVAL;
    }

    // insert source page into dstenv's pgdir with perm
    // check if out of memory
    if (page_insert(dstenv->env_pgdir, srcpage, dstva, perm) < 0) {
        // out of memory to allocate page table
        return -E_NO_MEM;
    }

    // panic("sys_page_map not implemented");

    // page successfully mapped
    return 0;
}

// In sys_page_unmap():
// 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) {
    // Hint: This function is a wrapper around page_remove().

    // LAB 4: Your code here.
    struct Env *env;
    // check and get env
    if (envid2env(envid, &env, true) < 0) {
        // envid not exist or permission error
        return -E_BAD_ENV;
    }

    // check va
    if ((uintptr_t)va >= UTOP || PGOFF(va) != 0) {
        // va above UTOP or va is not page-aligned
        return -E_INVAL;
    }

    // call page_remove to unmap page
    page_remove(env->env_pgdir, va);

    // panic("sys_page_unmap not implemented");

    // page successfully unmapped
    return 0;
}

// In syscall():
// new code added
case SYS_exofork:
    // call sys_exofork
    return sys_exofork();
    break;
case SYS_env_set_status:
    // call sys_env_set_status
    return sys_env_set_status((envid_t)a1, (int)a2);
    break;
case SYS_page_alloc:
    // call sys_page_alloc
    return sys_page_alloc((envid_t)a1, (void *)a2, (int)a3);
    break;
case SYS_page_map:
    // call sys_page_map
    return sys_page_map((envid_t)a1, (void *)a2, (envid_t)a3, (void *)a4,
                        (int)a5);
    break;
case SYS_page_unmap:
    // call sys_page_unmap
    return sys_page_unmap((envid_t)a1, (void *)a2);
    break;

// In 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.
    struct Env *env;
    // check and translate the envid
    if (envid2env(envid, &env, true) < 0) {
        // envid not exist or permission error
        return -E_BAD_ENV;
    }

    // set func
    env->env_pgfault_upcall = func;

    // panic("sys_env_set_pgfault_upcall not implemented");

    return 0;
}

// In syscall():
// new code added
case SYS_env_set_pgfault_upcall:
    // call sys_env_set_pgfault_upcall
    return sys_env_set_pgfault_upcall((envid_t)a1, (void *)a2);
    break;

// In trap.c, page_fault_handler():
// LAB 4: Your code here.
struct UTrapframe *utf;
uintptr_t          utf_addr;

// check tf->tf_esp's location to calculate utf's address
if ((tf->tf_esp >= UXSTACKTOP - PGSIZE) && (tf->tf_esp < UXSTACKTOP)) {
    // recursive case
    // reason why here needs to substract a 4-byte word
    // is to reserve space for reset eip/esp
    utf_addr = tf->tf_esp - sizeof(struct UTrapframe) - 4;
} else {
    // non-recursive case, set utf_addr to the top of
    // user exception stack
    utf_addr = UXSTACKTOP - sizeof(struct UTrapframe);
}

if (curenv->env_pgfault_upcall) {
    // page fault upcall exist

    // use mem assert to check environment allocates the exception
    // stack and has write permission to it, and stack ISN'T overflow
    // combine three case with only one user_mem_assert to check utf_addr
    // NB: curenv HAS been redefined as thiscpu->cpu_env
    user_mem_assert(curenv, (void *)utf_addr, sizeof(struct UTrapframe),
                    PTE_U | PTE_W | PTE_P);

    // set user stack frame
    utf               = (struct UTrapframe *)utf_addr;
    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;

    // modify stack frame to set entry for env_pgfault_upcall
    // and set address for user exception stack
    tf->tf_eip = (uintptr_t)curenv->env_pgfault_upcall;
    tf->tf_esp = utf_addr;

    env_run(curenv);
}

// In set_pgfault_handler():
if (_pgfault_handler == 0) {
    // First time through!
    // LAB 4: Your code here.
    // alloc one page for user exception stack
    // and register user-level page fault upcall
    if (sys_page_alloc(thisenv->env_id, (void *)(UXSTACKTOP - PGSIZE),
                       PTE_U | PTE_W | PTE_P) < 0) {
        panic("failed to alloc page for user exception stack!");
    }
    if (sys_env_set_pgfault_upcall(thisenv->env_id, _pgfault_upcall) < 0) {
        panic("failed to register page fault upcall!");
    }

    // panic("set_pgfault_handler not implemented");
}

// In lib/fork.c, fork():
//
// 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.
    int r;

    // use set_pgfault_handler to install pgfault() as page fault handler
    set_pgfault_handler(pgfault);

    // use system call to create new blank child environment
    envid_t child_env_id = sys_exofork();
    if (child_env_id == 0) {
        // must update thisenv to make sure user program behave
        // normally
        thisenv = envs + ENVX(sys_getenvid());
    }
    if (child_env_id < 0) {
        // error when create new environment, simply return
        return child_env_id;
    }

    // traverse through parent's address space and use duppage
    // to copy address mappings
    uintptr_t addr;
    for (addr = 0; addr < UTOP; addr += PGSIZE) {
        if ((((pde_t *)uvpd)[PDX(addr)] & PTE_P) &&
            (((pte_t *)uvpt)[PGNUM(addr)] & PTE_P)) {
            // if both page directory entry and page table entry
            // exist for one address(page-aligned), then call duppage
            if (addr == (UXSTACKTOP - PGSIZE)) {
                // ignore user exception stack
                // for we will map a page for user exception later
                continue;
            }
            if ((r = duppage(child_env_id, PGNUM(addr))) < 0) {
                // duppage failed
                // destroy child environment and return
                goto error_handle;
            }
        }
    }

    // child must have its own exception stack
    // so alloc page and map it for child here
    if ((r = sys_page_alloc(child_env_id, (void *)(UXSTACKTOP - PGSIZE),
                            PTE_P | PTE_U | PTE_W)) < 0) {
        // failed to set child environment's exception stack
        // destroy child environment and return
        goto error_handle;
    }

    // set child's page fault handler so that parent
    // and child looks the same
    // use sys_env_set_pgfault_upcall system call
    extern void _pgfault_upcall(void);
    if ((r = sys_env_set_pgfault_upcall(child_env_id, _pgfault_upcall)) < 0) {
        // failed to set child's page fault upcall
        // destroy child environment and return
        goto error_handle;
    }

    // now child is ready to run, set child to ENV_RUNNABLE
    // use sys_env_set_status system call
    if ((r = sys_env_set_status(child_env_id, ENV_RUNNABLE)) < 0) {
        // failed to change child environment's running status
        // destroy child environment and return
        goto error_handle;
    }

    // panic("fork not implemented");

    return child_env_id;

// use goto to avoid meaningless error_handle code
// copy and paste everywhere
error_handle:
    if (sys_env_destroy(child_env_id) < 0) {
        // failed either, panic then
        panic("failed to destroy child environment!");
    }
    return r;
}

// In lib/fork.c, duppage():
//
// 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.
    int perm = PTE_P | PTE_U;
    if ((((pte_t *)uvpt)[pn] & (PTE_W | PTE_COW))) {
        // check for writable or copy-on-write page
        // and add perm with PTE_COW
        perm |= PTE_COW;
        // NB: we also use 0 to replace thisenv->env_id
        // for in unix-like fork() implementation, we will copy
        // address space from parent process to child process
        // at current time, thisenv->env_id IS ABSOLUTELY WRONG

        // map from parent environment to child environment
        if (sys_page_map(0, (void *)(pn * PGSIZE), envid, (void *)(pn * PGSIZE),
                         perm) < 0) {
            panic("failed to map page from parent to child!");
        }
        // remap parent's environment
        if (sys_page_map(0, (void *)(pn * PGSIZE), 0, (void *)(pn * PGSIZE),
                         perm) < 0) {
            panic("failed to remap page in parent!");
        }
    } else {
        // for other pages, simply map from
        // parent environment to child environment
        if (sys_page_map(0, (void *)(pn * PGSIZE), envid, (void *)(pn * PGSIZE),
                         perm) < 0) {
            panic("failed to map page from parent to child!");
        }
    }

    // panic("duppage not implemented");

    return 0;
}

// In lib/fork.c, pgfault():
//
// 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.
    // use uvpt to get PTE and check premissions
    if (!(err & FEC_WR) || !(((pte_t *)uvpt)[PGNUM(addr)] & PTE_COW)) {
        panic("fault isn't write or PTE is not marked as PTE_COW or both!");
    }

    // 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.
    // allocate a page and map it at PFTEMP
    // use sys_page_alloc system call
    // NB: use 0 instead of thisenv->env_id
    // for normally when child environment scheduled by JOS
    // first it tries to store 0(return value of fork()) to
    // local variable child_env_id on the stack
    // which will take a page fault and kernel will trasfer control
    // to pgfault here
    // thisenv->env_id IS ABSOLUTELY WRONG here, so use 0
    // and let kernel convert from 0 to correct env_id
    if ((r = sys_page_alloc(0, (void *)PFTEMP, PTE_P | PTE_U | PTE_W)) < 0) {
        panic("failed to allocate page at temp location - %e, %x!", r,
              thisenv->env_id);
    }

    addr = ROUNDDOWN(addr, PGSIZE);
    // use memcpy to copy from fault address's page to PFTEMP's newly
    // allocated page
    memcpy((void *)PFTEMP, addr, PGSIZE);

    // use sys_page_map system call to map newly allocated
    // page at PFTEMP at addr with read/write permissions
    if ((r = sys_page_map(0, (void *)PFTEMP, 0, addr, PTE_P | PTE_U | PTE_W)) <
        0) {
        panic("failed to map new page - %e!", r);
    }
    // use sys_page_unmap system call to unmap page at
    // temp location PFTEMP
    if ((r = sys_page_unmap(0, (void *)PFTEMP)) < 0) {
        panic("failed to unmap page at PFTEMP - %e!", r);
    }

    // panic("pgfault not implemented");
}

// in kern/trap.c, trap_dispatch():
// new code added
if (tf->tf_trapno == IRQ_OFFSET + IRQ_TIMER) {
    // dispatch clock interupts
    // call sched_yield() to find and run a different environment
    // NB: should first call lapic_eoi() to ACKNOWLEDGE interupt
    lapic_eoi();
    sched_yield();
    // sched_yield() might not return
}

// In kern/syscall.c, sys_ipc_recv():
// Block until a value is ready.  Record that you want to receive
// using the env_ipc_recving and env_ipc_dstva fields of struct Env,
// mark yourself not runnable, and then give up the CPU.
//
// If 'dstva' is < UTOP, then you are willing to receive a page of data.
// 'dstva' is the virtual address at which the sent page should be mapped.
//
// This function only returns on error, but the system call will eventually
// return 0 on success.
// Return < 0 on error.  Errors are:
//  -E_INVAL if dstva < UTOP but dstva is not page-aligned.
static int sys_ipc_recv(void *dstva) {
    // LAB 4: Your code here.
    // similar to sys_ipc_try_send, will not mark an error
    // if dstva >= UTOP
    if ((uintptr_t)dstva < UTOP && PGOFF(dstva) != 0) {
        // if dstva < UTOP but dstva is not page-aligned
        // NB: && rather than ||, we won't report error
        // when dstva >= UTOP
        return -E_INVAL;
    }

    // mark calling environment as not runnable
    curenv->env_status = ENV_NOT_RUNNABLE;
    // update status to mark receiver is willing to receive message
    curenv->env_ipc_recving = true;
    curenv->env_ipc_dstva   = dstva;

    // give up cpu
    sys_yield();

    // panic("sys_ipc_recv not implemented");

    // ipc succeeds
    return 0;
}

// In kern/syscall.c, sys_ipc_try_send():
// Try to send 'value' to the target env 'envid'.
// If srcva < UTOP, then also send page currently mapped at 'srcva',
// so that receiver gets a duplicate mapping of the same page.
//
// The send fails with a return value of -E_IPC_NOT_RECV if the
// target is not blocked, waiting for an IPC.
//
// The send also can fail for the other reasons listed below.
//
// Otherwise, the send succeeds, and the target's ipc fields are
// updated as follows:
//    env_ipc_recving is set to 0 to block future sends;
//    env_ipc_from is set to the sending envid;
//    env_ipc_value is set to the 'value' parameter;
//    env_ipc_perm is set to 'perm' if a page was transferred, 0 otherwise.
// The target environment is marked runnable again, returning 0
// from the paused sys_ipc_recv system call.  (Hint: does the
// sys_ipc_recv function ever actually return?)
//
// If the sender wants to send a page but the receiver isn't asking for one,
// then no page mapping is transferred, but no error occurs.
// The ipc only happens when no errors occur.
//
// Returns 0 on success, < 0 on error.
// Errors are:
//  -E_BAD_ENV if environment envid doesn't currently exist.
//      (No need to check permissions.)
//  -E_IPC_NOT_RECV if envid is not currently blocked in sys_ipc_recv,
//      or another environment managed to send first.
//  -E_INVAL if srcva < UTOP but srcva is not page-aligned.
//  -E_INVAL if srcva < UTOP and perm is inappropriate
//      (see sys_page_alloc).
//  -E_INVAL if srcva < UTOP but srcva is not mapped in the caller's
//      address space.
//  -E_INVAL if (perm & PTE_W), but srcva is read-only in the
//      current environment's address space.
//  -E_NO_MEM if there's not enough memory to map srcva in envid's
//      address space.
static int sys_ipc_try_send(envid_t envid, uint32_t value, void *srcva,
                            unsigned perm) {
    // LAB 4: Your code here.
    // check for existence of env with envid
    struct Env *env;
    if (envid2env(envid, &env, false) < 0) {
        // environment envid doesn't currently exist
        return -E_BAD_ENV;
    }

    // check receiver's status
    if (!env->env_ipc_recving) {
        // envid is not currently blocked in sys_ipc_recv
        // or another environment managed to send first
        return -E_IPC_NOT_RECV;
    }

    if ((uintptr_t)srcva < UTOP) {
        // srcva is valid
        // check srcva is page-aligned
        if (PGOFF(srcva) != 0) {
            // srcva is not page-aligned
            return -E_INVAL;
        }
        // check perm passed in
        if ((perm & (~PTE_SYSCALL)) || !(perm & PTE_U) || !(perm & PTE_P)) {
            // invalid perm
            return -E_INVAL;
        }
        // check srcva actually be mapped
        pte_t *          pgtable_entry;
        struct PageInfo *page;
        if ((page = page_lookup(curenv->env_pgdir, srcva, &pgtable_entry)) ==
            NULL) {
            // NB: check for SRCVA here, so use curenv->env_pgdir
            // srcva is not mapped at caller's address space
            return -E_INVAL;
        }
        // check PTE_W between sender and receiver
        if ((perm & PTE_W) && (!((*pgtable_entry) & PTE_W))) {
            // if perm has PTE_W while srcva is read-only in
            // current environment's address space
            return -E_INVAL;
        }

        if ((uintptr_t)(env->env_ipc_dstva) < UTOP) {
            // receiver also expects page to be transferred
            // call page_insert to actually transer the page
            if (page_insert(env->env_pgdir, page, env->env_ipc_dstva, perm) <
                0) {
                // out of memory when try to insert page
                return -E_NO_MEM;
            }
            // page successfully transferred
            env->env_ipc_perm = perm;
        }
    } else {
        // srcva >= UTOP
        // invalid srcva, but we won't return error here
        // ipc_send will panic if we do so
    }

    // update receiver's information
    env->env_ipc_recving = false;
    env->env_ipc_from    = curenv->env_id;
    env->env_ipc_value   = value;
    // mark receiver to be runnable to match what we do in sys_ipc_recv
    env->env_status = ENV_RUNNABLE;
    // modify trapframe's eax register to `update' return value
    env->env_tf.tf_regs.reg_eax = 0;

    // panic("sys_ipc_try_send not implemented");

    // ipc succeeds
    return 0;
}

// In lib/ipc.c, ipc_recv():
// Receive a value via IPC and return it.
// If 'pg' is nonnull, then any page sent by the sender will be mapped at
//	that address.
// If 'from_env_store' is nonnull, then store the IPC sender's envid in
//	*from_env_store.
// If 'perm_store' is nonnull, then store the IPC sender's page permission
//	in *perm_store (this is nonzero if a page was successfully
//	transferred to 'pg').
// If the system call fails, then store 0 in *fromenv and *perm (if
//	they're nonnull) and return the error.
// Otherwise, return the value sent by the sender
//
// Hint:
//   Use 'thisenv' to discover the value and who sent it.
//   If 'pg' is null, pass sys_ipc_recv a value that it will understand
//   as meaning "no page".  (Zero is not the right value, since that's
//   a perfectly valid place to map a page.)
int32_t ipc_recv(envid_t *from_env_store, void *pg, int *perm_store) {
    // LAB 4: Your code here.
    // check pg, if pg is null, then should set it to UTOP,
    // for only if dstva is below UTOP, sender knows that
    // receiver wants a page to be transferred
    if (!pg) { pg = (void *)UTOP; }
    int r;
    if ((r = sys_ipc_recv(pg)) < 0) {
        // system call fails
        // store from env and perm if corresponding pointer is not null
        if (from_env_store) { *from_env_store = 0; }
        if (perm_store) { *perm_store = 0; }
        // return the error
        return r;
    }

    // system call succeeds
    // extract information from thisenv's IPC fields
    if (from_env_store) {
        // store IPC sender's envid into *from_env_store
        *from_env_store = thisenv->env_ipc_from;
    }
    if (perm_store) {
        // store IPC sender's page permission
        *perm_store = thisenv->env_ipc_perm;
    }

    // panic("ipc_recv not implemented");

    // return the value send by the sender
    return thisenv->env_ipc_value;
}

// In kern/syscall.c, syscall():
// new code added
case SYS_ipc_recv:
    // call sys_ipc_recv
    return sys_ipc_recv((void *)a1);
    break;
case SYS_ipc_try_send:
    // call sys_ipc_try_send
    return sys_ipc_try_send((envid_t)a1, (uint32_t)a2, (void *)a3,
                            (unsigned)a4);

// In lib/ipc.c, ipc_send():
// Send 'val' (and 'pg' with 'perm', if 'pg' is nonnull) to 'toenv'.
// This function keeps trying until it succeeds.
// It should panic() on any error other than -E_IPC_NOT_RECV.
//
// Hint:
//   Use sys_yield() to be CPU-friendly.
//   If 'pg' is null, pass sys_ipc_try_send a value that it will understand
//   as meaning "no page".  (Zero is not the right value.)
void ipc_send(envid_t to_env, uint32_t val, void *pg, int perm) {
    // LAB 4: Your code here.
    // check pg, if pg is null, then should set it to UTOP(invalid value
    // but won't result in panic)
    if (!pg) { pg = (void *)UTOP; }
    int r;
    while (true) {
        // keeps trying until succeeds or panic
        r = sys_ipc_try_send(to_env, val, pg, perm);
        if (r == 0) {
            // message successfully sent, return
            return;
        }
        if (r != -E_IPC_NOT_RECV) {
            // error when sending, should panic
            panic("failed to send messages - %e!", r);
        }
        // use sys_yield to avoid waste on CPU
        sys_yield();
    }

    // panic("ipc_send not implemented");
}

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

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

//////////////////////////////////////////////////////////////////////
// Make 'envs' point to an array of size 'NENV' of 'struct Env'.
// LAB 3: Your code here.
// get size of envs
uint32_t envs_size = sizeof(struct Env) * NENV;
// use boot_alloc to allocate memory
envs = (struct Env *)boot_alloc(envs_size);
// initialization
memset(envs, 0, envs_size);

//////////////////////////////////////////////////////////////////////
// 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, envs_size, PADDR(envs), PTE_U | PTE_P);

// In env_init():
// LAB 3: Your code here.
ssize_t i;
// loop in reverse order to keep ascending order in env free list
for (i = NENV - 1; i >= 0; i--) {
    // set env_status, env_id
    envs[i].env_status = ENV_FREE;
    envs[i].env_id     = 0;
    // set env_link and insert into env_free_list
    envs[i].env_link = env_free_list;
    env_free_list    = &envs[i];
}

// In env_setup_vm():
// LAB 3: Your code here.
// set env_pgdir and generate page directory based on kern_pgdir
e->env_pgdir = (pde_t *)page2kva(p);
memcpy(e->env_pgdir, kern_pgdir, PGSIZE);
// increase pp_ref
p->pp_ref++;

// In region_alloc():
// LAB 3: Your code here.
// (But only if you need it for load_icode.)
//
// Hint: It is easier to use region_alloc if the caller can pass
//   'va' and 'len' values that are not page-aligned.
//   You should round va down, and round (va + len) up.
//   (Watch out for corner-cases!)

// round va and va + len
uintptr_t start = (uintptr_t)ROUNDDOWN(va, PGSIZE);
uintptr_t end   = (uintptr_t)ROUNDUP(va + len, PGSIZE);

for (; start < end; start += PGSIZE) {
    // alloc page
    struct PageInfo *p;
    p = page_alloc(ALLOC_ZERO);
    if (!p) { panic("out of memory when allocating region!"); }
    // insert page into environment's page directory
    if (page_insert(e->env_pgdir, p, (char *)start, PTE_W | PTE_U | PTE_P) <
        0) {
        panic("out of memory when allocating region!");
    }
}

// In load_icode():
// LAB 3: Your code here.
// switch address space for loading program segments
lcr3(PADDR(e->env_pgdir));

struct Elf *elf = (struct Elf *)binary;
// check elf magic
if (elf->e_magic != ELF_MAGIC) { panic("invalid elf format!"); }

// set the program entry for env
e->env_tf.tf_eip = elf->e_entry;

struct Proghdr *ph, *eph;

// get the start and end of program header entry
ph  = (struct Proghdr *)(binary + elf->e_phoff);
eph = ph + elf->e_phnum;
for (; ph < eph; ph++) {
    if (ph->p_type == ELF_PROG_LOAD) {    // if the segment is to be loaded
        // alloc corresponding region(clear zero)
        region_alloc(e, (char *)ph->p_va, ph->p_memsz);
        // copy from ELF header to virtual addresses directly
        memcpy((char *)ph->p_va, (char *)binary + ph->p_offset, ph->p_filesz);
    }
}
// switch back
lcr3(PADDR(kern_pgdir));

// Now map one page for the program's initial stack
// at virtual address USTACKTOP - PGSIZE.
// LAB 3: Your code here.
// allocate a page and insert it into env's page directory
// panic when page_alloc or page_insert failed
struct PageInfo *stack_page = page_alloc(ALLOC_ZERO);
if (!stack_page) { panic("out of memory when alloc program's stack!"); }
if (page_insert(e->env_pgdir, stack_page, (char *)(USTACKTOP - PGSIZE),
                PTE_W | PTE_U | PTE_P) < 0) {
    panic("failed to set program's stack!");
}

// In env_create():
// LAB 3: Your code here.
struct Env *env;
// allocate new env with parent ID 0
if (env_alloc(&env, 0) < 0) { panic("failed to allocate env!"); }
// load elf binary and set env_type
load_icode(env, binary);
env->env_type = type;

// In env_run():
// LAB 3: Your code here.
if (curenv != NULL) {    // context switch
    if (curenv->env_status == ENV_RUNNING) {
        // change to runnable if current status is running
        // for not runnable, is not necessary to do this
        curenv->env_status = ENV_RUNNABLE;
    }
}

// set new curenv, update status and counter
curenv        = e;
e->env_status = ENV_RUNNING;
e->env_runs++;
// address space switch
// reference from inc/x86.h
lcr3(PADDR(e->env_pgdir));
// drop into user mode
env_pop_tf(&(e->env_tf));

// panic("env_run not yet implemented");

// In trapentry.S:
/*
 * Lab 3: Your code here for generating entry points for the different traps.
 */

TRAPHANDLER_NOEC(divide_error_handler, T_DIVIDE)
TRAPHANDLER_NOEC(debug_exception_handler, T_DEBUG)
TRAPHANDLER_NOEC(non_maskable_interrupt_handler, T_NMI)
TRAPHANDLER_NOEC(breakpoint_handler, T_BRKPT)
TRAPHANDLER_NOEC(overflow_handler, T_OFLOW)
TRAPHANDLER_NOEC(bounds_check_handler, T_BOUND)
TRAPHANDLER_NOEC(invalid_opcode_handler, T_ILLOP)
TRAPHANDLER_NOEC(device_not_available_handler, T_DEVICE)
TRAPHANDLER(double_fault_handler, T_DBLFLT)
TRAPHANDLER(invalid_tss_handler, T_TSS)
TRAPHANDLER(segment_not_present_handler, T_SEGNP)
TRAPHANDLER(stack_exception_handler, T_STACK)
TRAPHANDLER(general_protection_fault_handler, T_GPFLT)
TRAPHANDLER(pagefault_handler, T_PGFLT)
TRAPHANDLER_NOEC(floating_point_error_handler, T_FPERR)
TRAPHANDLER(alignment_check_handler, T_ALIGN)
TRAPHANDLER_NOEC(machine_check_handler, T_MCHK)
TRAPHANDLER_NOEC(simd_floating_point_error_handler, T_SIMDERR)

/*
 * Lab 3: Your code here for _alltraps
 */

_alltraps:
// push ds and es and general registers
push %ds
push %es
pushal

// load ds and es with GD_KD, for kernel stack locates in data
mov $GD_KD, %ax
mov %ax, %ds
mov %ax, %es

// pass tf as an argument
pushl %esp

// call trap and no need to return
call trap

// In trap.c, trap_init():

// LAB 3: Your code here.
// declare of exception handler
void divide_error_handler();
void debug_exception_handler();
void non_maskable_interrupt_handler();
void breakpoint_handler();
void overflow_handler();
void bounds_check_handler();
void invalid_opcode_handler();
void device_not_available_handler();
void double_fault_handler();
void invalid_tss_handler();
void segment_not_present_handler();
void stack_exception_handler();
void general_protection_fault_handler();
void pagefault_handler();
void floating_point_error_handler();
void alignment_check_handler();
void machine_check_handler();
void simd_floating_point_error_handler();

// set up trap gate descriptor
SETGATE(idt[T_DIVIDE],	 1, GD_KT, divide_error_handler,           	   0);
SETGATE(idt[T_DEBUG],    1, GD_KT, debug_exception_handler,            0);
SETGATE(idt[T_NMI],      1, GD_KT, non_maskable_interrupt_handler,     0);
SETGATE(idt[T_BRKPT],    1, GD_KT, breakpoint_handler,                 3);
SETGATE(idt[T_OFLOW],    1, GD_KT, overflow_handler,                   0);
SETGATE(idt[T_BOUND],    1, GD_KT, bounds_check_handler,               0);
SETGATE(idt[T_ILLOP],    1, GD_KT, invalid_opcode_handler,             0);
SETGATE(idt[T_DEVICE],   1, GD_KT, device_not_available_handler,       0);
SETGATE(idt[T_DBLFLT],   1, GD_KT, double_fault_handler,               0);
SETGATE(idt[T_TSS],      1, GD_KT, invalid_tss_handler,                0);
SETGATE(idt[T_SEGNP],    1, GD_KT, segment_not_present_handler,        0);
SETGATE(idt[T_STACK],    1, GD_KT, stack_exception_handler,            0);
SETGATE(idt[T_GPFLT],    1, GD_KT, general_protection_fault_handler,   0);
SETGATE(idt[T_PGFLT],    1, GD_KT, pagefault_handler,                  0);
SETGATE(idt[T_FPERR],    1, GD_KT, floating_point_error_handler,       0);
SETGATE(idt[T_ALIGN],    1, GD_KT, alignment_check_handler,            0);
SETGATE(idt[T_MCHK],     1, GD_KT, machine_check_handler,              0);
SETGATE(idt[T_SIMDERR],  1, GD_KT, simd_floating_point_error_handler,  0);

// In trap_dispatch():
if (tf->tf_trapno == T_PGFLT) {
    // dispatch page fault exceptions
    page_fault_handler(tf);
}

if (tf->tf_trapno == T_BRKPT) {
    // dispatch breakpoint exceptions
    monitor(tf);
}