* same with xv6

[mascara-docs.git] / i386 / ucla / src / lab4 / kern / pmap.c

/* See COPYRIGHT for copyright information. */

#include <inc/x86.h>
#include <inc/mmu.h>
#include <inc/error.h>
#include <inc/string.h>
#include <inc/assert.h>

#include <kern/pmap.h>
#include <kern/kclock.h>
#include <kern/env.h>

// These variables are set by i386_detect_memory()
size_t npages;                  // Amount of physical memory (in pages)
static size_t npages_basemem;   // Amount of base memory (in pages)

// These variables are set in mem_init()
pde_t *kern_pgdir;              // Kernel's initial page directory
struct Page *pages;             // Physical page state array
static Page *page_free_list;    // Free list of physical pages

extern char bootstack[];        // Lowest addr in boot-time kernel stack
                                // (a virtual address in remapped physical mem)

// Global descriptor table.
//
// The kernel and user segments are identical (except for the DPL).
// To load the SS register, the CPL must equal the DPL.  Thus,
// we must duplicate the segments for the user and the kernel.
//
struct Segdesc gdt[] = {
        SEG_NULL,                               // 0x0 - unused (always faults)
        SEG(STA_X | STA_R, 0x0, 0xffffffff, 0), // 0x8 - kernel code segment
        SEG(STA_W, 0x0, 0xffffffff, 0),         // 0x10 - kernel data segment
        SEG(STA_X | STA_R, 0x0, 0xffffffff, 3), // 0x18 - user code segment
        SEG(STA_W, 0x0, 0xffffffff, 3),         // 0x20 - user data segment
        SEG_NULL                                // 0x28 - tss, initialized in
                                                // idt_init()
};

struct Pseudodesc gdt_pd = {
        sizeof(gdt) - 1, (unsigned long) gdt
};

static physaddr_t check_va2pa(pde_t *pgdir, uintptr_t va);


// --------------------------------------------------------------
// Detect machine's physical memory setup.
// --------------------------------------------------------------

static int
nvram_read(int r)
{
        return mc146818_read(r) | (mc146818_read(r + 1) << 8);
}

static void
i386_detect_memory(void)
{
        size_t npages_extendedmem;

        // Use CMOS calls to measure available base & extended memory.
        // (CMOS calls return results in kilobytes.)
        npages_basemem = (nvram_read(NVRAM_BASELO) * 1024) / PGSIZE;
        npages_extendedmem = (nvram_read(NVRAM_EXTLO) * 1024) / PGSIZE;

        // Calculate the number of physical pages available in both base
        // and extended memory.
        if (npages_extendedmem)
                npages = (EXTPHYSMEM / PGSIZE) + npages_extendedmem;
        else
                npages = npages_basemem;

        cprintf("Physical memory: %uK available, base = %uK, extended = %uK\n",
                npages * PGSIZE / 1024,
                npages_basemem * PGSIZE / 1024,
                npages_extendedmem * PGSIZE / 1024);
}


// --------------------------------------------------------------
// Set up initial memory mappings and turn on MMU.
// --------------------------------------------------------------

static void check_kern_pgdir(void);
static void check_page_alloc(void);
static void check_page(void);
static void page_map_segment(pde_t *pgdir, uintptr_t la, size_t size, physaddr_t pa, int perm);

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

        return NULL;
}

// Set up a two-level page table:
//    kern_pgdir is its linear (virtual) address of the root
//    boot_cr3 is the physical adresss of the root
// Then turn on paging.  Then effectively turn off segmentation.
// (i.e., the segment base addrs are set to zero).
//
// This function only sets up the kernel part of the address space
// (ie. addresses >= UTOP).  The user part of the address space
// will be setup later.
//
// From UTOP to ULIM, the user is allowed to read but not write.
// Above ULIM the user cannot read (or write).
void
mem_init(void)
{
        uint32_t cr0;
        size_t n;

        // Find out how much memory the machine has (npages & npages_basemem).
        i386_detect_memory();

        // Remove this line when you're ready to test this function.
        panic("mem_init: This function is not finished\n");

        //////////////////////////////////////////////////////////////////////
        // create initial page directory.
        kern_pgdir = (pde_t *) boot_alloc(PGSIZE);
        memset(kern_pgdir, 0, PGSIZE);

        //////////////////////////////////////////////////////////////////////
        // Recursively insert PD in itself as a page table, to form
        // a virtual page table at virtual address UVPT.
        // (For now, you don't have understand the greater purpose of the
        // following line.)
        // Permissions: kernel R, user R
        kern_pgdir[PDX(UVPT)] = PADDR(kern_pgdir) | PTE_U | PTE_P;

        //////////////////////////////////////////////////////////////////////
        // Allocate an array of npages 'struct Page's and store it in 'pages'.
        // The kernel uses this array to keep track of physical pages: for
        // each physical page, there is a corresponding struct Page in this
        // array.  'npages' is the number of physical pages in memory.
        // Your code goes here:


        //////////////////////////////////////////////////////////////////////
        // Make 'envs' point to an array of size 'NENV' of 'struct Env'.
        // LAB 3: Your code here.

        //////////////////////////////////////////////////////////////////////
        // Now that we've allocated the initial kernel data structures, we set
        // up the list of free physical pages. Once we've done so, all further
        // memory management will go through the page_* functions. In
        // particular, we can now map memory using page_map_segment
        // or page_insert
        page_init();

        check_page_alloc();

        check_page();

        //////////////////////////////////////////////////////////////////////
        // Now we set up virtual memory

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

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

        //////////////////////////////////////////////////////////////////////
        // Map the 'envs' array read-only by the user at linear address UENVS.
        // Permissions: kernel R, user R
        // (That's the UENVS version; 'envs' itself is kernel RW, user NONE.)
        // LAB 3: Your code here.

        //////////////////////////////////////////////////////////////////////
        // Map 'pages' read-only by the user at linear address UPAGES.
        // Permissions: kernel R, user R
        // (That's the UPAGES version; 'pages' itself is kernel RW, user NONE.)
        // LAB 3: Your code here.

        // Check that the initial page directory has been set up correctly.
        check_kern_pgdir();

        //////////////////////////////////////////////////////////////////////
        // On x86, segmentation maps a VA to a LA (linear addr) and
        // paging maps the LA to a PA.  I.e. VA => LA => PA.  If paging is
        // turned off the LA is used as the PA.  Note: there is no way to
        // turn off segmentation.  The closest thing is to set the base
        // address to 0, so the VA => LA mapping is the identity.

        // Current mapping: VA KERNBASE+x => PA x.
        //     (segmentation base=-KERNBASE and paging is off)

        // From here on down we must maintain this VA KERNBASE + x => PA x
        // mapping, even though we are turning on paging and reconfiguring
        // segmentation.

        // Map VA 0:4MB same as VA KERNBASE, i.e. to PA 0:4MB.
        // (Limits our kernel to <4MB)
        kern_pgdir[0] = kern_pgdir[PDX(KERNBASE)];

        // Install page table.
        lcr3(PADDR(kern_pgdir));

        // Turn on paging.
        cr0 = rcr0();
        cr0 |= CR0_PE|CR0_PG|CR0_AM|CR0_WP|CR0_NE|CR0_TS|CR0_EM|CR0_MP;
        cr0 &= ~(CR0_TS|CR0_EM);
        lcr0(cr0);

        // Current mapping: KERNBASE+x => x => x.
        // (x < 4MB so uses paging pgdir[0])

        // Reload all segment registers.
        asm volatile("lgdt gdt_pd");
        asm volatile("movw %%ax,%%gs" :: "a" (GD_UD|3));
        asm volatile("movw %%ax,%%fs" :: "a" (GD_UD|3));
        asm volatile("movw %%ax,%%es" :: "a" (GD_KD));
        asm volatile("movw %%ax,%%ds" :: "a" (GD_KD));
        asm volatile("movw %%ax,%%ss" :: "a" (GD_KD));
        asm volatile("ljmp %0,$1f\n 1:\n" :: "i" (GD_KT));  // reload cs
        asm volatile("lldt %%ax" :: "a" (0));

        // Final mapping: KERNBASE+x => KERNBASE+x => x.

        // This mapping was only used after paging was turned on but
        // before the segment registers were reloaded.
        kern_pgdir[0] = 0;

        // Flush the TLB for good measure, to kill the pgdir[0] mapping.
        lcr3(PADDR(kern_pgdir));
}


// --------------------------------------------------------------
// Tracking of physical pages.
// The 'pages' array has one 'struct Page' entry per physical page.
// Pages are reference counted, and free pages are kept on a linked list.
// --------------------------------------------------------------

//
// Initialize page structure and memory free list.
// After this is done, NEVER use boot_alloc again.  ONLY use the page
// allocator functions below to allocate and deallocate physical
// memory via the page_free_list.
//
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, basemem) 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.
        size_t i;
        page_free_list = 0;
        for (i = 0; i < npages; i++) {
                pages[i].pp_ref = 0;
                pages[i].pp_link = page_free_list;
                page_free_list = &pages[i];
        }
}

//
// Allocates a physical page.
// Does NOT set the contents of the physical page to zero, NOR does it
// increment the reference count of the page - the caller must do
// these if necessary.
// Returns NULL if out of free memory.
//
struct Page *
page_alloc(void)
{
        // Fill this function in
        return 0;
}

//
// Return a page to the free list.
// (This function should only be called when pp->pp_ref reaches 0.)
//
void
page_free(struct Page *pp)
{
        // Fill this function in
}


// --------------------------------------------------------------
// Looking up pages and adding them to page directories.
// --------------------------------------------------------------

// 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 == 0, 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: Check out page2pa() and page2kva() in 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.
pte_t *
pgdir_walk(pde_t *pgdir, uintptr_t va, int create)
{
        // Fill this function in
        return NULL;
}

//
// Map [la, la+size) of linear address space to physical [pa, pa+size)
// in the page table rooted at pgdir.  Size is a multiple of PGSIZE.
// Use permission bits perm|PTE_P for the entries.  Does not manipulate
// 'struct Page' structures.
//
// Hint: Try using pgdir_walk.
static void
page_map_segment(pde_t *pgdir, uintptr_t la, size_t size, physaddr_t pa, int perm)
{
        // Fill this function in
}

//
// Map the physical page 'pp' at virtual address 'va'.
// The permissions (the low 12 bits) of the page table entry
// should be set to 'perm|PTE_P'.
//
// Requirements
//   - If there is already a page mapped at 'va', it should be page_remove()d.
//   - If necessary, on demand, a page table should be allocated and inserted
//     into 'pgdir'.
//   - pp->pp_ref should be incremented if the insertion succeeds.
//   - The TLB must be invalidated if a page was formerly present at 'va'.
//
// Corner-case hint: Make sure to consider what happens when the same
// pp is re-inserted at the same virtual address in the same pgdir.
//
// RETURNS:
//   0 on success
//   -E_NO_MEM, if page table couldn't be allocated
//
// Hint: Check out pgdir_walk, page_remove, page2pa, and similar functions.
//
int
page_insert(pde_t *pgdir, struct Page *pp, uintptr_t va, pte_t perm)
{
        // Fill this function in
        return 0;
}

//
// Return the struct Page for the page mapped at virtual address 'va'.
// If pte_store is not zero, then we store in it the address
// of the pte for this page.
//
// Return NULL if there is no page mapped at va.
//
// Hint: the TA solution uses pgdir_walk and pa2page.
//
struct Page *
page_lookup(pde_t *pgdir, uintptr_t va, pte_t **pte_store)
{
        // Fill this function in
        return NULL;
}

//
// Decrement the reference count on a page,
// freeing it if there are no more refs.
//
void
page_decref(struct Page* pp)
{
        if (--pp->pp_ref == 0)
                page_free(pp);
}

//
// Unmaps the physical page at virtual address 'va'.
// If there is no physical page at that address, silently does nothing.
//
// Details:
//   - The ref count on the physical page should decrement.
//   - The physical page should be freed if the refcount reaches 0.
//   - The pg table entry corresponding to 'va' should be set to 0.
//     (if such a PTE exists)
//   - The TLB must be invalidated if you remove an entry from
//     the page table.
//
// Hint: The TA solution is implemented using page_lookup,
//      tlb_invalidate, and page_decref.
//
void
page_remove(pde_t *pgdir, uintptr_t va)
{
        // Fill this function in
}

//
// Invalidate a TLB entry, but only if the page tables being
// edited are the ones currently in use by the processor.
//
void
tlb_invalidate(pde_t *pgdir, uintptr_t va)
{
        // Flush the entry only if we're modifying the current address space.
        if (!curenv || curenv->env_pgdir == pgdir)
                invlpg(va);
}

static uintptr_t user_mem_check_addr;

//
// Check that an environment is allowed to access the range of memory
// [va, va+len) with permissions 'perm | PTE_P'.
// Normally 'perm' will contain PTE_U at least, but this is not required.
// 'va' and 'len' need not be page-aligned; you must test every page that
// contains any of that range.  You will test either 'len/PGSIZE',
// 'len/PGSIZE + 1', or 'len/PGSIZE + 2' pages.
//
// A user program can access a virtual address if (1) the address is below
// ULIM, and (2) the page table gives it permission.  These are exactly
// the tests you should implement here.
//
// If there is an error, set the 'user_mem_check_addr' variable to the first
// erroneous virtual address.
//
// Returns 0 if the user program can access this range of addresses,
// and -E_FAULT otherwise.
//
int
user_mem_check(struct Env *env, uintptr_t va, size_t len, pte_t perm)
{
        // LAB 3: Your code here.

        return 0;
}

//
// Checks that environment 'env' is allowed to access the range
// of memory [va, va+len) with permissions 'perm | PTE_U | PTE_P'.
// If it can, then the function simply returns.
// If it cannot, 'env' is destroyed and, if env is the current
// environment, this function will not return.
//
void
user_mem_assert(struct Env *env, uintptr_t va, size_t len, pte_t perm)
{
        if (user_mem_check(env, va, len, perm | PTE_U) < 0) {
                cprintf("[%08x] user_mem_check assertion failure for "
                        "va %08x\n", env->env_id, user_mem_check_addr);
                env_destroy(env);       // may not return
        }
}


// --------------------------------------------------------------
// Checking functions.
// --------------------------------------------------------------

//
// Check the physical page allocator (page_alloc(), page_free(),
// and page_init()).
//
static void
check_page_alloc()
{
        struct Page *pp, *pp0, *pp1, *pp2;
        struct Page *fl;
        char *first_free_page;

        if (!pages)
                panic("'pages' is still 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 (pp0 = page_free_list; pp0; pp0 = pp0->pp_link)
                memset(page2kva(pp0), 0x97, 128);

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

                // check a few pages that shouldn't be on the free list
                assert(page2pa(pp0) != 0);
                assert(page2pa(pp0) != IOPHYSMEM);
                assert(page2pa(pp0) != EXTPHYSMEM - PGSIZE);
                assert(page2pa(pp0) != EXTPHYSMEM);
                assert(page2kva(pp0) != ROUNDDOWN(first_free_page - 1, PGSIZE));
        }

        // should be able to allocate three pages
        pp0 = pp1 = pp2 = 0;
        assert((pp0 = page_alloc()));
        assert((pp1 = page_alloc()));
        assert((pp2 = page_alloc()));

        assert(pp0);
        assert(pp1 && pp1 != pp0);
        assert(pp2 && pp2 != pp1 && pp2 != pp0);
        assert(page2pa(pp0) < npages*PGSIZE);
        assert(page2pa(pp1) < npages*PGSIZE);
        assert(page2pa(pp2) < npages*PGSIZE);

        // temporarily steal the rest of the free pages
        fl = page_free_list;
        page_free_list = 0;

        // should be no free memory
        assert(!page_alloc());

        // free and re-allocate?
        page_free(pp0);
        page_free(pp1);
        page_free(pp2);
        pp0 = pp1 = pp2 = 0;
        assert((pp0 = page_alloc()));
        assert((pp1 = page_alloc()));
        assert((pp2 = page_alloc()));
        assert(pp0);
        assert(pp1 && pp1 != pp0);
        assert(pp2 && pp2 != pp1 && pp2 != pp0);
        assert(!page_alloc());

        // give free list back
        page_free_list = fl;

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

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

//
// Checks that the kernel part of virtual address space
// has been setup roughly correctly(by i386_vm_init()).
//
// This function doesn't test every corner case,
// in fact it doesn't test the permission bits at all,
// but it is a pretty good sanity check.
//

static void
check_kern_pgdir(void)
{
        uint32_t i, n;
        pde_t *pgdir;

        pgdir = kern_pgdir;

        // check phys mem
        for (i = 0; i < npages * PGSIZE; i += PGSIZE)
                assert(check_va2pa(pgdir, KERNBASE + i) == i);

        // check kernel stack
        for (i = 0; i < KSTKSIZE; i += PGSIZE)
                assert(check_va2pa(pgdir, KSTACKTOP - KSTKSIZE + i) == PADDR(bootstack) + i);
        assert(check_va2pa(pgdir, KSTACKTOP - PTSIZE) == (physaddr_t) ~0);

        // check for zero/non-zero in PDEs
        for (i = 0; i < NPDENTRIES; i++) {
                switch (i) {
                case PDX(UVPT):
                case PDX(KSTACKTOP-1):
                case PDX(UPAGES):
                case PDX(UENVS):
                        assert(pgdir[i]);
                        break;
                default:
                        if (i >= PDX(KERNBASE + npages * PGSIZE))
                                /* either way is OK */;
                        else if (i >= PDX(KERNBASE))
                                assert(pgdir[i]);
                        else
                                assert(pgdir[i] == 0);
                        break;
                }
        }

        // check pages array
        n = ROUNDUP(npages*sizeof(struct Page), PGSIZE);
        for (i = 0; i < n; i += PGSIZE)
                assert(check_va2pa(pgdir, UPAGES + i) == PADDR(pages) + i);

        // check envs array (new test for lab 3)
        n = ROUNDUP(NENV*sizeof(struct Env), PGSIZE);
        for (i = 0; i < n; i += PGSIZE)
                assert(check_va2pa(pgdir, UENVS + i) == PADDR(envs) + i);

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

// Return the physical address of the page containing 'va',
// defined by the page directory 'pgdir'.
// Returns the special value ~0 if 'va' is not mapped.
// The hardware normally performs this functionality for us!
// We define our own version to help check the check_kern_pgdir() function.
//
static physaddr_t
check_va2pa(pde_t *pgdir, uintptr_t va)
{
        pte_t *p;

        pgdir = &pgdir[PDX(va)];
        if (!(*pgdir & PTE_P))
                return ~0;
        p = (pte_t*) KADDR(PTE_ADDR(*pgdir));
        if (!(p[PTX(va)] & PTE_P))
                return ~0;
        return PTE_ADDR(p[PTX(va)]);
}

// check page_insert, page_remove, &c
static void
check_page(void)
{
        struct Page *pp, *pp0, *pp1, *pp2;
        struct Page *fl;
        pte_t *ptep, *ptep1;
        uintptr_t va;
        int i;

        // should be able to allocate three pages
        pp0 = pp1 = pp2 = 0;
        assert((pp0 = page_alloc()));
        assert((pp1 = page_alloc()));
        assert((pp2 = page_alloc()));

        assert(pp0);
        assert(pp1 && pp1 != pp0);
        assert(pp2 && pp2 != pp1 && pp2 != pp0);

        // temporarily steal the rest of the free pages
        fl = page_free_list;
        page_free_list = 0;

        // should be no free memory
        assert(!page_alloc());

        // there is no page allocated at address 0
        assert(page_lookup(kern_pgdir, 0x0, &ptep) == NULL);

        // there is no free memory, so we can't allocate a page table
        assert(page_insert(kern_pgdir, pp1, 0x0, 0) < 0);

        // free pp0 and try again: pp0 should be used for page table
        page_free(pp0);
        assert(page_insert(kern_pgdir, pp1, 0x0, 0) == 0);
        assert(PTE_ADDR(kern_pgdir[0]) == page2pa(pp0));
        assert(check_va2pa(kern_pgdir, 0x0) == page2pa(pp1));
        assert(pp1->pp_ref == 1);
        assert(pp0->pp_ref == 1);

        // should be able to map pp2 at PGSIZE because pp0 is already allocated for page table
        assert(page_insert(kern_pgdir, pp2, PGSIZE, 0) == 0);
        assert(check_va2pa(kern_pgdir, PGSIZE) == page2pa(pp2));
        assert(pp2->pp_ref == 1);

        // should be no free memory
        assert(!page_alloc());

        // should be able to map pp2 at PGSIZE because it's already there
        assert(page_insert(kern_pgdir, pp2, PGSIZE, 0) == 0);
        assert(check_va2pa(kern_pgdir, PGSIZE) == page2pa(pp2));
        assert(pp2->pp_ref == 1);

        // pp2 should NOT be on the free list
        // could happen in ref counts are handled sloppily in page_insert
        assert(!page_alloc());

        // check that pgdir_walk returns a pointer to the pte
        ptep = (pte_t *) KADDR(PTE_ADDR(kern_pgdir[PDX(PGSIZE)]));
        assert(pgdir_walk(kern_pgdir, PGSIZE, 0) == ptep+PTX(PGSIZE));

        // should be able to change permissions too.
        assert(page_insert(kern_pgdir, pp2, PGSIZE, PTE_U) == 0);
        assert(check_va2pa(kern_pgdir, PGSIZE) == page2pa(pp2));
        assert(pp2->pp_ref == 1);
        assert(*pgdir_walk(kern_pgdir, PGSIZE, 0) & PTE_U);
        assert(kern_pgdir[0] & PTE_U);

        // should not be able to map at PTSIZE because need free page for page table
        assert(page_insert(kern_pgdir, pp0, PTSIZE, 0) < 0);

        // insert pp1 at PGSIZE (replacing pp2)
        assert(page_insert(kern_pgdir, pp1, PGSIZE, 0) == 0);
        assert(!(*pgdir_walk(kern_pgdir, PGSIZE, 0) & PTE_U));

        // should have pp1 at both 0 and PGSIZE, pp2 nowhere, ...
        assert(check_va2pa(kern_pgdir, 0) == page2pa(pp1));
        assert(check_va2pa(kern_pgdir, PGSIZE) == page2pa(pp1));
        // ... and ref counts should reflect this
        assert(pp1->pp_ref == 2);
        assert(pp2->pp_ref == 0);

        // pp2 should be returned by page_alloc
        assert((pp = page_alloc()) && pp == pp2);

        // unmapping pp1 at 0 should keep pp1 at PGSIZE
        page_remove(kern_pgdir, 0x0);
        assert(check_va2pa(kern_pgdir, 0x0) == (physaddr_t) ~0);
        assert(check_va2pa(kern_pgdir, PGSIZE) == page2pa(pp1));
        assert(pp1->pp_ref == 1);
        assert(pp2->pp_ref == 0);

        // unmapping pp1 at PGSIZE should free it
        page_remove(kern_pgdir, PGSIZE);
        assert(check_va2pa(kern_pgdir, 0x0) == (physaddr_t) ~0);
        assert(check_va2pa(kern_pgdir, PGSIZE) == (physaddr_t) ~0);
        assert(pp1->pp_ref == 0);
        assert(pp2->pp_ref == 0);

        // so it should be returned by page_alloc
        assert((pp = page_alloc()) && pp == pp1);

        // should be no free memory
        assert(!page_alloc());

#if 0
        // should be able to page_insert to change a page
        // and see the new data immediately.
        memset(page2kva(pp1), 1, PGSIZE);
        memset(page2kva(pp2), 2, PGSIZE);
        page_insert(kern_pgdir, pp1, 0x0, 0);
        assert(pp1->pp_ref == 1);
        assert(*(int*)0 == 0x01010101);
        page_insert(kern_pgdir, pp2, 0x0, 0);
        assert(*(int*)0 == 0x02020202);
        assert(pp2->pp_ref == 1);
        assert(pp1->pp_ref == 0);
        page_remove(kern_pgdir, 0x0);
        assert(pp2->pp_ref == 0);
#endif

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

        // check pointer arithmetic in pgdir_walk
        page_free(pp0);
        va = PGSIZE * NPDENTRIES + PGSIZE;
        ptep = pgdir_walk(kern_pgdir, va, 1);
        ptep1 = (pte_t *) KADDR(PTE_ADDR(kern_pgdir[PDX(va)]));
        assert(ptep == ptep1 + PTX(va));
        kern_pgdir[PDX(va)] = 0;
        pp0->pp_ref = 0;

        // check that new page tables get cleared
        memset(page2kva(pp0), 0xFF, PGSIZE);
        page_free(pp0);
        pgdir_walk(kern_pgdir, 0x0, 1);
        ptep = (pte_t *) page2kva(pp0);
        for(i=0; i<NPTENTRIES; i++)
                assert((ptep[i] & PTE_P) == 0);
        kern_pgdir[0] = 0;
        pp0->pp_ref = 0;

        // give free list back
        page_free_list = fl;

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

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