//
// Check that the pages on the page_free_list are reasonable.
//
static void
check_page_free_list(bool only_low_memory)
{
	struct Page *pp;
	unsigned pdx_limit = only_low_memory ? 4 : NPDENTRIES;
	int nfree_basemem = 0, nfree_extmem = 0;
	char *first_free_page;

	if (!page_free_list)
		panic("'page_free_list' is a null pointer!");

	// if there's a page that shouldn't be on the free list,
	// try to make sure it eventually causes trouble.
	for (pp = page_free_list; pp; pp = pp->pp_link)
		if (PDX(page2pa(pp)) < pdx_limit)
			memset(page2kva(pp), 0x97, 128);

	first_free_page = (char *) boot_alloc(0);
	for (pp = page_free_list; pp; pp = pp->pp_link) {
		// check that we didn't corrupt the free list itself
		assert(pp >= pages);
		assert(pp < pages + npages);
		assert(((char *) pp - (char *) pages) % sizeof(*pp) == 0);

		// check a few pages that shouldn't be on the free list
		assert(page2pa(pp) != 0);
		assert(page2pa(pp) != IOPHYSMEM);
		assert(page2pa(pp) != EXTPHYSMEM - PGSIZE);
		assert(page2pa(pp) != EXTPHYSMEM);
		assert(page2pa(pp) < EXTPHYSMEM || page2kva(pp) >= first_free_page);

		if (page2pa(pp) < EXTPHYSMEM)
			++nfree_basemem;
		else
			++nfree_extmem;
	}

	assert(nfree_basemem > 0);
	assert(nfree_extmem > 0);
}

// check page_insert, page_remove, &c, with an installed kern_pgdir
static void
check_page_installed_pgdir(void)
{
    struct PageInfo *pp, *pp0, *pp1, *pp2;
    struct PageInfo *fl;
    pte_t *ptep, *ptep1;
    uintptr_t va;
    int i;

    // check that we can read and write installed pages
    pp1 = pp2 = 0;
    assert((pp0 = page_alloc(0)));
    assert((pp1 = page_alloc(0)));
    assert((pp2 = page_alloc(0)));
    page_free(pp0);
    memset(page2kva(pp1), 1, PGSIZE);
    memset(page2kva(pp2), 2, PGSIZE);
    page_insert(kern_pgdir, pp1, (void*) PGSIZE, PTE_W);
    assert(pp1->pp_ref == 1);
    assert(*(uint32_t *)PGSIZE == 0x01010101U);
    page_insert(kern_pgdir, pp2, (void*) PGSIZE, PTE_W);
    assert(*(uint32_t *)PGSIZE == 0x02020202U);
    assert(pp2->pp_ref == 1);
    assert(pp1->pp_ref == 0);
    *(uint32_t *)PGSIZE = 0x03030303U;
    assert(*(uint32_t *)page2kva(pp2) == 0x03030303U);
    page_remove(kern_pgdir, (void*) PGSIZE);
    assert(pp2->pp_ref == 0);

    // forcibly take pp0 back
    assert(PTE_ADDR(kern_pgdir[0]) == page2pa(pp0));
    kern_pgdir[0] = 0;
    assert(pp0->pp_ref == 1);
    pp0->pp_ref = 0;

    // free the pages we took
    page_free(pp0);

    cprintf("check_page_installed_pgdir() succeeded!\n");
}

/**
 * pgdir_alloc_page - call alloc_page & page_insert functions to 
 *                  - allocate a page size memory & setup an addr map
 *                  - pa<->la with linear address la and the PDT pgdir
 * @param pgdir    page directory
 * @param la       logical address for the page to be allocated
 * @param perm     permission of the page
 * @return         the page descriptor of the allocated
 */
struct Page *
pgdir_alloc_page(pgd_t *pgdir, uintptr_t la, uint32_t perm) {
    struct Page *page = alloc_page();
    if (page != NULL) {
        //zero it!
        memset(page2kva(page), 0, PGSIZE);
        if (page_insert(pgdir, page, la, perm) != 0) {
            free_page(page);
            return NULL;
        }
    }
    return page;
}

//
// Allocates a physical page.  If (alloc_flags & ALLOC_ZERO), fills the entire
// returned physical page with '\0' bytes.  Does NOT increment the reference
// count of the page - the caller must do these if necessary (either explicitly
// or via page_insert).
//
// Returns NULL if out of free memory.
//
// Hint: use page2kva and memset
struct PageInfo *
page_alloc(int alloc_flags)
{
	// Fill this function in
	// SUNUS, 23, October, 2013
	struct PageInfo *pp = page_free_list;
	if (!pp)
		return NULL;
	page_free_list = page_free_list->pp_link;
	if (alloc_flags & ALLOC_ZERO)
		memset(page2kva(pp), '\0', PGSIZE);
	pp->pp_link = NULL;
	return pp;
}

static void
check_boot_pgdir(void) {
    pte_t *ptep;
    int i;
    for (i = 0; i < npage; i += PGSIZE) {
        assert((ptep = get_pte(boot_pgdir, (uintptr_t)KADDR(i), 0)) != NULL);
        assert(PTE_ADDR(*ptep) == i);
    }


    assert(PDE_ADDR(boot_pgdir[PDX(VPT)]) == PADDR(boot_pgdir));
    //cprintf("%08x\n",boot_pgdir[PDX(VPT)]);
    //cprintf("%08x\n",PADDR(boot_pgdir));

    assert(boot_pgdir[256] == 0);

    struct Page *p;

    p = alloc_page();

    assert(page_insert(boot_pgdir, p, 0x40000100, PTE_TYPE_SRW) == 0);
    assert(page_ref(p) == 1);
    assert(page_insert(boot_pgdir, p, 0x40000100 + PGSIZE, PTE_TYPE_SRW) == 0);
    assert(page_ref(p) == 2);

    const char *str = "ucore: Hello world!!";

    strcpy((void *)0x40000100, str);
    assert(strcmp((void *)0x40000100, (void *)(0x40000100 + PGSIZE)) == 0);
    cprintf("%s\n\n",(char*)0x40000100);
    //cprintf("mstatus=%08x\n",read_mstatus_field(MSTATUS_PRV));
//    cprintf("bageyalusilasiladi%s\n",((char*)0x40000100));
    *(char *)(page2kva(p) + 0x100) = '\0';
    //asm volatile("nop");
    //asm volatile("nop");
    //cprintf("\0\n");
 //   cprintf("%d\n",strlen((char *)0x40000100));
    assert(strlen((const char *)0x40000100) == 0);
    //assert(((const char *)0x30000100) == '\0');

    //asm volatile("nop");
//    asm volatile("nop");
    free_page(p);
    free_page(pde2page(boot_pgdir[256]));
    //cprintf("haah2\n");

    boot_pgdir[256] = 0;

    cprintf("check_boot_pgdir() succeeded!\n");
}

//
// Initialize the kernel virtual memory layout for environment e.
// Allocate a page directory, set e->env_pgdir and e->env_cr3 accordingly,
// and initialize the kernel portion of the new environment's address space.
// Do NOT (yet) map anything into the user portion
// of the environment's virtual address space.
//
// Returns 0 on success, < 0 on error.  Errors include:
//	-E_NO_MEM if page directory or table could not be allocated.
//
static int
env_setup_vm(struct Env *e)
{
	int i, r;
	struct Page *p = NULL;

	// Allocate a page for the page directory
	if ((r = page_alloc(&p)) < 0)
		return r;

	//    - Remember that page_alloc doesn't zero the page.
        pde_t *pgdir = page2kva(p);
        memset(pgdir, 0, PGSIZE);
        e->env_pgdir = page2kva(p);
        e->env_cr3 = PADDR(pgdir);
        
	//    - The VA space of all envs is identical above UTOP
	//	(except at VPT and UVPT, which we've set below).
	//	See inc/memlayout.h for permissions and layout.
	//	Can you use boot_pgdir as a template?  Hint: Yes.
	for (i = PDX(UTOP); i < NPDENTRIES; i++)
		e->env_pgdir[i] = boot_pgdir[i];
	//    - The initial VA below UTOP is empty.

        //    - Note: In general, pp_ref is not maintained for
	//	physical pages mapped only above UTOP, but env_pgdir
	//	is an exception -- you need to increment env_pgdir's
	//	pp_ref for env_free to work correctly.
        p->pp_ref++;

	// VPT and UVPT map the env's own page table, with
	// different permissions.
	e->env_pgdir[PDX(VPT)]  = e->env_cr3 | PTE_P | PTE_W;
	e->env_pgdir[PDX(UVPT)] = e->env_cr3 | PTE_P | PTE_U;

	return 0;
}

//
// Allocates n continuous physical page. If (alloc_flags & ALLOC_ZERO), fills the n pages 
// returned physical page with '\0' bytes.  Does NOT increment the reference
// count of the page - the caller must do these if necessary (either explicitly
// or via page_insert). 
//
// In order to figure out the n pages when return it. 
// These n pages should be organized as a list.
//
// Returns NULL if out of free memory.
// Returns NULL if n <= 0
//
// Try to reuse the pages cached in the chuck list
//
// Hint: use page2kva and memset
struct Page *
page_alloc_npages(int alloc_flags, int n)
{
	// Fill this function
	/*stone's solution for lab2*/
	if (n <= 0)
		return NULL;
	size_t i = 0;
	size_t j;
	int flag = 0;
	while (i < npages){
		if (pages[i].pp_ref == 0){
			for (j = 0; j < n && i + j < npages; j++){
				if (pages[i+j].pp_ref != 0)
					break;
			}
			if (j == n) flag = 1;
			else i += j;
		}
		if (flag == 1) break;
		i++;
	}
	if (flag == 0) return NULL;

	struct Page* tmp = page_free_list;
	while (&pages[i+j] > tmp && tmp >= &pages[i])
		tmp = tmp->pp_link;
	page_free_list = tmp;
	struct Page* result = tmp;

	//stone:remove all n pages from page_free_list
	/*for (; tmp != NULL; tmp = tmp->pp_link){
		if (&pages[i+j] > tmp && tmp >= &pages[i]){
			while (&pages[i+j] > tmp->pp_link && tmp->pp_link >= &pages[i])
				tmp = tmp->pp_link;
			result->pp_link = tmp->pp_link;
		}
		result = tmp;
	}*/
	size_t k;
	for (k = 0; k < n - 1; k++){
		pages[k + i].pp_link = &pages[k + 1 + i];
	}
	result = &pages[i];
	
	if (alloc_flags & ALLOC_ZERO)
		memset(page2kva(result), '\0', n*PGSIZE);
	return result;
}

//
// Initializes the kernel virtual memory layout for environment e.
//
// Allocates a page directory and initializes it.  Sets
// e->env_cr3 and e->env_pgdir accordingly.
//
// RETURNS
//   0 -- on sucess
//   <0 -- otherwise 
//
static int
env_setup_vm(struct Env *e)
{
	// Hint:

	int i, r;
	struct Page *p = NULL;

	Pde *pgdir;
	// Allocate a page for the page directory
	if ((r = page_alloc(&p)) < 0)
	{
		panic("env_setup_vm - page_alloc error\n");
			return r;
	}
	p->pp_ref++;
	//printf("env.c:env_setup_vm:page_alloc:p\[email protected]:%x\[email protected]:%x\tcon:%x\n",page2pa(p),(int)&p,(int)p);
//printf("env_setup_vm :	1\n");
	// Hint:
	//    - The VA space of all envs is identical above UTOP
	//      (except at VPT and UVPT) 
	//    - Use boot_pgdir
	//    - Do not make any calls to page_alloc 
	//    - Note: pp_refcnt is not maintained for physical pages mapped above UTOP.
	pgdir = (Pde *)page2kva(p);
//	printf("env.c:env_setup_vm:\tpgdir\t:con:%x\n",(int)pgdir);
	for(i=0;i<UTOP; i+=BY2PG)
		pgdir[PDX(i)] = 0;
	for(i=PDX(UTOP); i<1024;i++)
	{
//printf("boot_pgdir[%d] = %x\n",i,boot_pgdir[PDX(i)]);
		pgdir[i] = boot_pgdir[i];
	}
//printf("env_setup_vm :	2\n");

	e->env_pgdir = pgdir;
//printf("env_setup_vm :	3\n");
	// ...except at VPT and UVPT.  These map the env's own page table

	//e->env_pgdir[PDX(UVPT)]  = e->env_cr3 | PTE_P | PTE_U;

	e->env_cr3 = PADDR(pgdir);

	boot_map_segment(e->env_pgdir,UVPT,PDMAP,PADDR(pgdir),PTE_R);
//	printf("env.c:env_setup_vm:\tboot_map_segment(%x,%x,%x,%x,PTE_R)\n",e->env_pgdir,UVPT,PDMAP,PADDR(pgdir));
	e->env_pgdir[PDX(UVPT)]  = e->env_cr3 | PTE_V | PTE_R;
//printf("env_setup_vm :  4\n");
	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_USER 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 = NULL;
	struct Page *pp = NULL;
	int allowed_perm = 0;
	
	// Check envid and get env
	if (envid2env(envid, &env, 1) != 0){
		return -E_BAD_ENV;
	}

	// Check va
	if ((uint32_t)va >= UTOP || (uint32_t)va % PGSIZE != 0){
		return -E_INVAL;
	}

	// Check perm
	allowed_perm = PTE_U | PTE_P;
	if ((perm & allowed_perm) != allowed_perm){
	}
	allowed_perm |= PTE_W | PTE_AVAIL;
	// Check if there are other permissions
	if ((perm ^ (perm & allowed_perm)) != 0){
		return -E_INVAL;
	}
	if (page_alloc(&pp) < 0){
		return -E_NO_MEM;
	}
	// cprintf("***************** alloc page no.%d\n", page2ppn(pp));
	// insert into the page table of env
	if (page_insert(env->env_pgdir, pp, va, perm | PTE_P) != 0){
		page_free(pp);
		return -E_NO_MEM;
	}
	memset(page2kva(pp), 0, PGSIZE);

	return 0;
	// panic("sys_page_alloc not implemented");
}

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

	if(envid2env(envid, &env, 1) == -E_BAD_ENV)
	{
		//cprintf("bad environment envid in sys page alloc:%08x\n",envid);
		return -E_BAD_ENV;
	}
	else if((uintptr_t)va >= UTOP || (uint32_t)va % PGSIZE)
	       return -E_INVAL;
	else if((perm & PTE_U) && (perm & PTE_P))
	{
		if(perm & ((~(PTE_U|PTE_P|PTE_W|PTE_AVAIL) & 0xfff)))
			return -E_INVAL;		
	}
	if((vpd[PDX(va)] & PTE_P) && (vpt[VPN(va)] & PTE_P))
		page_remove(env->env_pgdir,va);

	//cprintf("env id:%08x\n",env->env_id);	
	struct Page * page;
	if(page_alloc(&page) == -E_NO_MEM)
		return -E_NO_MEM;
	//cprintf("page alloc kva:%08x\n",page2kva(page));
	// At this time, we use the page table of the kernel
	// so we clear the phsical page according to the kernel virtual address 
	memset(page2kva(page),0x0,PGSIZE);
	//cprintf("page insert,env_id:%08x,env_pgdir:%08x,page:%08x,va:%08x\n",
	//		env->env_id,env->env_pgdir,page,va);
	if(page_insert(env -> env_pgdir, page, va, perm) != 0)
	{
		page_free(page);
		return -E_NO_MEM;
	}
	//cprintf("page insert success\n");
	
	return 0;
	//panic("sys_page_alloc not implemented");
}

//
// Allocates a physical page.  If (alloc_flags & ALLOC_ZERO), fills the entire
// returned physical page with '\0' bytes.  Does NOT increment the reference
// count of the page - the caller must do these if necessary (either explicitly
// or via page_insert).
//
// Be sure to set the pp_link field of the allocated page to NULL so
// page_free can check for double-free bugs.
//
// Returns NULL if out of free memory.
//
// Hint: use page2kva and memset
struct PageInfo *
page_alloc(int alloc_flags)
{		// Fill this function in

	struct PageInfo *ppt=page_free_list;
	if (ppt ==0){
	//cprintf(" page_alloc returning null\n");
		return NULL;
	}
	page_free_list=ppt->pp_link;	
	ppt->pp_link=NULL;
	if(alloc_flags & ALLOC_ZERO){
		memset(page2kva(ppt),'\0',PGSIZE);
	}
	return ppt;
}

// Given 'pgdir', a pointer to a page directory, pgdir_walk returns
// a pointer to the page table entry (PTE) for linear address 'va'.
// This requires walking the two-level page table structure.
//
// The relevant page table page might not exist yet.
// If this is true, and create == false, then pgdir_walk returns NULL.
// Otherwise, pgdir_walk allocates a new page table page with page_alloc. 
//    - If the allocation fails, pgdir_walk returns NULL.
//    - Otherwise, the new page's reference count is incremented,
//	the page is cleared,
//	and pgdir_walk returns a pointer into the new page table page.
//
// Hint 1: you can turn a Page * into the physical address of the
// page it refers to with page2pa() from kern/pmap.h.
//
// Hint 2: the x86 MMU checks permission bits in both the page directory
// and the page table, so it's safe to leave permissions in the page
// directory more permissive than strictly necessary.
//
// Hint 3: look at inc/mmu.h for useful macros that mainipulate page
// table and page directory entries.
//
pte_t *
pgdir_walk(pde_t *pgdir, const void *va, int create)
{
	// Fill this function in
    pde_t* pd = pgdir + (unsigned int) PDX(va);
    //PTE_ADDR used for both pte and pde
    if (*pd & PTE_P)
            return (pte_t*) KADDR(PTE_ADDR(*pd)) + (unsigned)PTX(va);
    // if page doesn't exist
    if (create == 0) return NULL;
    struct PageInfo* newpt = page_alloc(1);
    if (newpt == NULL) return NULL;
    newpt -> pp_ref = 1;
    *pd = page2pa(newpt) | PTE_P | PTE_U | PTE_W;
    return (pte_t*)page2kva(newpt) + (unsigned) PTX(va);
}

//
// Allocates a physical page.  If (alloc_flags & ALLOC_ZERO), fills the entire
// returned physical page with '\0' bytes.  Does NOT increment the reference
// count of the page - the caller must do these if necessary (either explicitly
// or via page_insert).
//
// Returns NULL if out of free memory.
//
// Hint: use page2kva and memset
struct Page *
page_alloc(int alloc_flags)
{
	struct Page* allocPage;
	if(page_free_list==NULL)
		return NULL;
	allocPage=page_free_list;
	page_free_list=page_free_list->pp_link;
	allocPage->pp_link=NULL;
	if(alloc_flags&&ALLOC_ZERO)
	{
		void* kvirAddr=page2kva(allocPage);
		memset(kvirAddr,0,PGSIZE);
	}
	return allocPage;
}

//
// Allocates a physical page.  If (alloc_flags & ALLOC_ZERO), fills the entire
// returned physical page with '\0' bytes.  Does NOT increment the reference
// count of the page - the caller must do these if necessary (either explicitly
// or via page_insert).
//
// Returns NULL if out of free memory.
//
// Hint: use page2kva and memset
struct Page *
page_alloc(int alloc_flags)
{
	// Fill this function in
	/*stone's solution for lab2*/
	struct Page* alloc_page;
	if (page_free_list != NULL){
		alloc_page = page_free_list;
		page_free_list = page_free_list->pp_link;
		alloc_page->pp_link = NULL;
		if (alloc_flags & ALLOC_ZERO)
			memset(page2kva(alloc_page), '\0', PGSIZE);
		return alloc_page;
	}
	return NULL;
}

//
// Allocates a physical page.  If (alloc_flags & ALLOC_ZERO), fills the entire
// returned physical page with '\0' bytes.  Does NOT increment the reference
// count of the page - the caller must do these if necessary (either explicitly
// or via page_insert).
//
// Be sure to set the pp_link field of the allocated page to NULL so
// page_free can check for double-free bugs.
//
// Returns NULL if out of free memory.
//
// Hint: use page2kva and memset
struct PageInfo *
page_alloc(int alloc_flags)
{
	if(!page_free_list)	
		return NULL;

	struct PageInfo *ret = page_free_list;
	page_free_list = page_free_list->pp_link;

	ret->pp_link = NULL;
	assert(ret->pp_ref == 0);
	if(alloc_flags & ALLOC_ZERO){
		memset(page2kva(ret), '\0', PGSIZE);
	}

	return ret;
}

static int
setup_pgdir(struct mm_struct *mm) {
    struct Page *page;
    /* 4 * 4K = 16K */
#warning dirty hack
    if ((page = alloc_pages(8)) == NULL) {
        return -E_NO_MEM;
    }
    pgd_t *pgdir_start = page2kva(page);
    pgd_t *pgdir = ROUNDUP(pgdir_start , 4*PGSIZE);
    memcpy(pgdir, init_pgdir_get(), 4*PGSIZE);

	  map_pgdir (pgdir);
    mm->pgdir = pgdir;
    mm->pgdir_alloc_addr = pgdir_start;
    return 0;
}

//
// Allocates a physical page.  If (alloc_flags & ALLOC_ZERO), fills the entire
// returned physical page with '\0' bytes.  Does NOT increment the reference
// count of the page - the caller must do these if necessary (either explicitly
// or via page_insert).
//
// Be sure to set the pp_link field of the allocated page to NULL so
// page_free can check for double-free bugs.
//
// Returns NULL if out of free memory.
struct PageInfo *
page_alloc(int alloc_flags)
{
    // Only perform these operations if we have enough memory.
    struct PageInfo *result = page_free_list;
    if (result != NULL) {
        // Increment free list pointer and mark result as used.
        page_free_list = page_free_list->pp_link;
        result->pp_link = NULL;

        // Zero memory if specified by alloc_flags.
        if (alloc_flags & ALLOC_ZERO) {
            memset(page2kva(result), 0, PGSIZE);
        }
    }
    return result;
}

static void
check_n_pages(void)
{
	struct Page* pp, *pp0;
	char* addr;
	int i;
	pp = pp0 = 0;
	
	// Allocate two single pages
	pp =  page_alloc(0);
	pp0 = page_alloc(0);
	assert(pp != 0);
	assert(pp0 != 0);
	assert(pp != pp0);

	
	// Free pp and assign four continuous pages
	page_free(pp);
	pp = page_alloc_npages(0, 4);
	assert(check_continuous(pp, 4));

	// Free four continuous pages
	assert(!page_free_npages(pp, 4));

	// Free pp and assign eight continuous pages
	pp = page_alloc_npages(0, 8);
	assert(check_continuous(pp, 8));

	// Free four continuous pages
	assert(!page_free_npages(pp, 8));


	// Free pp0 and assign four continuous zero pages
	page_free(pp0);
	pp0 = page_alloc_npages(ALLOC_ZERO, 4);
	addr = (char*)page2kva(pp0);
	
	// Check Zero
	for( i = 0; i < 4 * PGSIZE; i++ ){
		assert(addr[i] == 0);
	}

	// Free pages
	assert(!page_free_npages(pp0, 4));
	cprintf("check_n_pages() succeeded!\n");
}

// Given 'pgdir', a pointer to a page directory, pgdir_walk returns
// a pointer to the page table entry (PTE) for linear address 'va'.
// This requires walking the two-level page table structure.
//
// The relevant page table page might not exist yet.
// If this is true, and create == false, then pgdir_walk returns NULL.
// Otherwise, pgdir_walk allocates a new page table page with page_alloc.
//    - If the allocation fails, pgdir_walk returns NULL.
//    - Otherwise, the new page's reference count is incremented,
//	the page is cleared,
//	and pgdir_walk returns a pointer into the new page table page.
//
// Hint 1: you can turn a Page * into the physical address of the
// page it refers to with page2pa() from kern/pmap.h.
//
// Hint 2: the x86 MMU checks permission bits in both the page directory
// and the page table, so it's safe to leave permissions in the page
// more permissive than strictly necessary.
//
// Hint 3: look at inc/mmu.h for useful macros that mainipulate page
// table and page directory entries.
//
pte_t *
pgdir_walk(pde_t *pgdir, const void *va, int create)
{
//	cprintf("pgdir_walk: va:%x pgdir[PDX(va)]:%x\n",va,pgdir[PDX(va)]);
	if (pgdir[PDX(va)] & PTE_P)
	{
		return PTX(va)+(pte_t*)(KADDR(PTE_ADDR(pgdir[PDX(va)])));
	}else{
		if (create == 0) return NULL;
		struct Page *newp = page_alloc(ALLOC_ZERO);
		if (newp == NULL) return NULL;
		newp->pp_ref++;
		pgdir[PDX(va)] = page2pa(newp) | PTE_P | PTE_W | PTE_U;
		return PTX(va)+(pte_t*)page2kva(newp);
	}
	return NULL;
}

//
// Allocates a physical page.  If (alloc_flags & ALLOC_ZERO), fills the entire
// returned physical page with '\0' bytes.  Does NOT increment the reference
// count of the page - the caller must do these if necessary (either explicitly
// or via page_insert).
//
// Returns NULL if out of free memory.
//
// Hint: use page2kva and memset
struct Page *
page_alloc(int alloc_flags)
{
	// Fill this function in
	struct Page* alloc_page = NULL;

	if (page_free_list) {
		alloc_page = page_free_list;
		page_free_list = page_free_list->pp_link;
		alloc_page->pp_link = NULL;
		// if ALLOC_ZERO flag true, set all empty 
		if (alloc_flags & ALLOC_ZERO)
			memset(page2kva(alloc_page), 0, PGSIZE);
	}

	return alloc_page;
}