boot_alloc()
mem_init() (only up to the call to check_page_free_list(1))
page_init()
page_alloc()
page_free()

boot_alloc()
mem_init() // 只需要实现到check_page_free_list(1)这里。
page_init()
page_alloc()
page_free()

int *p = 0x3BD  << 22 | 0x3BD << 12 | 0;
for (int i = 0; i < 1024; i++) {
    p[i]; // 这里实际上就是在遍历kern_pgdir[i];    
}

int *p = 0x3BD  << 22 | 0x3BD << 12 | 0;
for (int i = 0; i < 1024; i++) {
    p[i]; // 这里实际上就是在遍历uint32_t kern_pgdir[i];    
}

int *p = 0x3BD  << 22 | 0x3BD << 12 | 0;
for (i = 0; i < 1024; i++) {
    if (*(p+i) & 0x01) {
        // 二级页表存在
    } else {
        // 二级页表不存在
    }
}

// This simple physical memory allocator is used only while JOS is setting
// up its virtual memory system.  page_alloc() is the real allocator.
//
// If n>0, allocates enough pages of contiguous physical memory to hold 'n'
// bytes.  Doesn't initialize the memory.  Returns a kernel virtual address.
//
// If n==0, returns the address of the next free page without allocating
// anything.
//
// If we're out of memory, boot_alloc should panic.
// This function may ONLY be used during initialization,
// before the page_free_list list has been set up.
static void *
boot_alloc(uint32_t n)
{
    static char *nextfree;    // virtual address of next byte of free memory
    char *result;
    // Initialize nextfree if this is the first time.
    // 'end' is a magic symbol automatically generated by the linker,
    // which points to the end of the kernel's bss segment:
    // the first virtual address that the linker did *not* assign
    // to any kernel code or global variables.
    if (!nextfree) {
        extern char end[];
        nextfree = ROUNDUP((char *) end, PGSIZE);
    }
    // Allocate a chunk large enough to hold 'n' bytes, then update
    // nextfree.  Make sure nextfree is kept aligned
    // to a multiple of PGSIZE.
    //
    // LAB 2: Your code here.
    if (0 == n) {
        return nextfree;
    }
    n = ROUNDUP(n, PGSIZE);
    result = nextfree;
    nextfree += n;
    return result;
}

// Your code goes here:
n = sizeof(struct PageInfo) * npages;
pages = (struct PageInfo*)boot_alloc(n);
memset(pagees, 0, n);

void
page_init(void)
{
    // 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...)
    //  2) The rest of base memory, [PGSIZE, npages_basemem * PGSIZE)
    //     is free.
    //  3) Then comes the IO hole [IOPHYSMEM, EXTPHYSMEM), which must
    //     never be allocated.
    //  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?
    //
    // Change the code to reflect this.
    // NB: DO NOT actually touch the physical memory corresponding to
    // free pages!
    size_t i;
    // 这里采用的思路是：凡是不能被分配的内存页，都不加到链表里面。
    // 只处理可以被使用的内存页。
    assert(!page_free_list);
    // 1. page 0是要被用来做实模式的IDT BIOS数据结构，尽管从来不会用，以后也不会用
    //    这不是浪费么。不管了。
    // 2. 接下来的[PGSIZE, npages_basemem * PGSIZE)是可用的。
    for (i = 1; i < npages_basemem; i++) {
        pages[i].pp_ref = 0;
        pages[i].pp_link = page_free_list;
        page_free_list = &pages[i];
    }
    // 3. IO空洞，绝对不能使用。
    //    链表直接跳过。不管。
    // 4. 直接找到kernel内存的尾巴
    //    注意这里取了PADDR之后要除PGSIZE.
    for (i = PADDR(boot_alloc(0))/PGSIZE; i < npages; i++) {        
        pages[i].pp_ref = 0;
        pages[i].pp_link = page_free_list;
        page_free_list = &pages[i];
    }
}

struct PageInfo *
page_alloc(int alloc_flags)
{
    // Fill this function in
    struct PageInfo *ret = page_free_list;
    if (!page_free_list) {
        return NULL;
    }
    page_free_list = ret->pp_link;
    ret->pp_link = NULL;
    if (alloc_flags & ALLOC_ZERO) {
        memset(page2kva(ret), 0, PGSIZE);
    }
    return ret;
}

void
page_free(struct PageInfo *pp)
{
    // Fill this function in
    // Hint: You may want to panic if pp->pp_ref is nonzero or
    // pp->pp_link is not NULL.
    assert(!pp->pp_ref);
    assert(!pp->pp_link);
    pp->pp_link = page_free_list;
    page_free_list = pp;
}

pte_t *
pgdir_walk(pde_t *pgdir, const void *va, int create)
{
    // Fill this function in
    assert(pgdir);
    pde_t *pde = &pgdir[PDX(va)];
    if (!(*pde & PTE_P)) {
        if (!create) return NULL;
        struct PageInfo *page = page_alloc(ALLOC_ZERO);
        if (!page) return NULL;
        page->pp_ref++;
        assert(page->pp_ref == 1);
        assert(page->pp_link == NULL);
        *pde = page2pa(page) | PTE_P | PTE_U | PTE_W;
    }
    // 获取页表项
    return (pte_t*)(KADDR(PTE_ADDR(*pde))) + PTX(va);
}

static void
boot_map_region(pde_t *pgdir, uintptr_t va, size_t size, physaddr_t pa, int perm)
{
    // Fill this function in
    for (uint32_t i = 0; i < size; i += PGSIZE) {
        pte_t *pte = pgdir_walk(pgdir, (const void *)va, true);
        *pte = pa | perm | PTE_P;
        va += PGSIZE;
        pa += PGSIZE;
    }
}

int
page_insert(pde_t *pgdir, struct PageInfo *pp, void *va, int perm)
{
    // Fill this function in
    pte_t *pte = pgdir_walk(pgdir, va, true);
    if (!pte)
        return -E_NO_MEM;
    pp->pp_ref++;
    if (*pte & PTE_P)
        page_remove(pgdir, va);
    *pte = page2pa(pp) | perm | PTE_P;
    tlb_invalidate(pgdir, va);
    return 0;
}

struct PageInfo *
page_lookup(pde_t *pgdir, void *va, pte_t **pte_store)
{
    // Fill this function in
    pte_t *pte = pgdir_walk(pgdir, va, false);
    if (!pte || !(*pte & PTE_P)) return NULL;
    if (pte_store) *pte_store = pte;
    return pa2page(PTE_ADDR(*pte));
}

void
page_remove(pde_t *pgdir, void *va)
{
    // Fill this function in
    pte_t *pte = NULL;
    struct PageInfo *pp = page_lookup(pgdir, va, &pte);
    if (!pp) return;
    *pte = 0;
    page_decref(pp);
    tlb_invalidate(pgdir, va);
}

// Your code goes here:
// 注意这里用的是PTSIZE
// 一种保守的作法是把pages align到页大小之后再进行映射。
boot_map_region(kern_pgdir, UPAGES, PTSIZE, PADDR(pages), PTE_U);
//////////////////////////////////////////////////////////////////////
// Use the physical memory that 'bootstack' refers to as the kernel
// stack.  The kernel stack grows down from virtual address KSTACKTOP.
// We consider the entire range from [KSTACKTOP-PTSIZE, KSTACKTOP)
// to be the kernel stack, but break this into two pieces:
//     * [KSTACKTOP-KSTKSIZE, KSTACKTOP) -- backed by physical memory
//     * [KSTACKTOP-PTSIZE, KSTACKTOP-KSTKSIZE) -- not backed; so if
//       the kernel overflows its stack, it will fault rather than
//       overwrite memory.  Known as a "guard page".
//     Permissions: kernel RW, user NONE
// Your code goes here:
boot_map_region(kern_pgdir, KSTACKTOP-KSTKSIZE, KSTKSIZE, PADDR(bootstack), PTE_W);    
//////////////////////////////////////////////////////////////////////
// Map all of physical memory at KERNBASE.
// Ie.  the VA range [KERNBASE, 2^32) should map to
//      the PA range [0, 2^32 - KERNBASE)
// We might not have 2^32 - KERNBASE bytes of physical memory, but
// we just set up the mapping anyway.
// Permissions: kernel RW, user NONE
// Your code goes here:
// KERNBASE    0x F0000000
// 2^32 =      0x 1000 0000
// 256MB
boot_map_region(kern_pgdir, KERNBASE, 0x10000000, 0, PTE_W);