MIT6.828操作系统工程Lab2-Memory Management实验报告

// In boot_alloc():
// 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 (n == 0) {
    // return the address of next free page
    return nextfree;
} else if (n > 0) {
    // round up size to a multiple of PGSIZE
    size_t size = ROUNDUP(n, PGSIZE);
    char * addr = nextfree;
    // update address of next free page(still multiple of PGSIZE)
    nextfree += size;
    // nextfree is a kernel virtual address, out out memory when it exceeds 4 MB
	if (nextfree >= (char *)KADDR(0x400000)) {
        panic("out of memory when booting!");
    }
    // return address
    return addr;
}

// In mem_init():
//////////////////////////////////////////////////////////////////////
// Allocate an array of npages 'struct PageInfo'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 PageInfo in this
// array.  'npages' is the number of physical pages in memory.  Use memset
// to initialize all fields of each struct PageInfo to 0.
// Your code goes here:
// get size of pages
uint32_t pages_size = sizeof(struct PageInfo) * npages;
// use boot_alloc to allocate memory
pages = (struct PageInfo *) boot_alloc(pages_size);
// initialization
memset(pages, 0, pages_size);

// In page_init():
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
for(i = 1 ; i < npages_basemem ; i++) {
    pages[i].pp_ref = 0;
    pages[i].pp_link = page_free_list;
    page_free_list = &pages[i];
}

// calculate next free page and initialize corresponding pages entry
// convert from kernel virtual address to physical address
size_t next_free_page = PADDR(boot_alloc(0)) / PGSIZE;
pages[next_free_page].pp_link = &pages[npages_basemem - 1];
page_free_list = &pages[next_free_page];

// initialize remaining pages entry
for (i = next_free_page + 1 ; i < npages ; i++) {
    pages[i].pp_ref = 0;
    pages[i].pp_link = page_free_list;
    page_free_list = &pages[i];
}

// In page_alloc():
struct PageInfo *
page_alloc(int alloc_flags)
{
	// get first element in free list
	struct PageInfo * page_ptr = page_free_list;
	if (page_ptr != NULL) {
		// NOT out of memory
		// update free list
		page_free_list = page_free_list->pp_link;
		// get kernal virtual address from given page
		char * addr = page2kva(page_ptr);
		// set pp_link to NULL to allow double-free bugs check
		page_ptr->pp_link = NULL;
		// ALLOC_ZERO set, use memset to initialze physical page
		if (alloc_flags & ALLOC_ZERO) {
			memset(addr, 0, PGSIZE);
		}

		// return page
		return page_ptr;
	}

	return NULL;
}

// In page_free():
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.

	//check pp_ref and pp_link
	if (pp->pp_ref != 0) {
		panic("page's reference count is non-zero!");
	}
	if (pp->pp_link != NULL) {
		panic("double free error when free page!");
	}

	// return page to free list
	pp->pp_link = page_free_list;
	page_free_list = pp;
}

// In pgdir_walk():
pte_t *pgdir_walk(pde_t *pgdir, const void *va, int create) {
    // get page directory index and page directory entry
    size_t pgdir_index = PDX(va);
    pde_t  pgdir_entry = pgdir[pgdir_index];
    // get page table index
    size_t pgtable_index = PTX(va);
    if ((pgdir_entry & PTE_P) == 1) {
        // page table page exists
        // get address of page table
        pte_t *pgtable = KADDR(PTE_ADDR(pgdir_entry));
        return (pte_t *)(pgtable + pgtable_index);
    } else {
        // page table page doesn't exist
        if (create == false) {
            // create flag is false, returns NULL
            return NULL;
        } else {
            // allocate a new page table page
            struct PageInfo *page = page_alloc(ALLOC_ZERO);
            if (page == NULL) {
                // allocation fails
                return NULL;
            } else {
                // increase physical page's reference count
                page->pp_ref++;
                // get physical address of physical page
                physaddr_t page_pa = page2pa(page);
                // insert page table into page directory
                pgdir[pgdir_index] = page_pa | PTE_W | PTE_U | PTE_P;
                // NB: returns KERNEL VIRTUAL ADDRESS here, for 0-4M is NOT
                // writable
                return (pte_t *)page2kva(page) + pgtable_index;
            }
        }
    }
    return NULL;
}

// In boot_map_region():
static void boot_map_region(pde_t *pgdir, uintptr_t va, size_t size,
                            physaddr_t pa, int perm) {
    // round up size
    size = ROUNDUP(size, PGSIZE);
    // get the number of pages to be mapped
    size_t page_num = PGNUM(size);

    size_t i;
    for (i = 0; i < page_num; i++) {
        // iterate through to get each pte_t * through pgdir_walk given virtual
        // address
        pte_t *pgtable_entry_ptr =
            pgdir_walk(pgdir, (char *)(va + i * PGSIZE), true);
        // set pte_t according to physical address and permission flags
        *pgtable_entry_ptr = (pa + i * PGSIZE) | perm | PTE_P;
    }
}

// In page_lookup():
struct PageInfo *page_lookup(pde_t *pgdir, void *va, pte_t **pte_store) {
    // Fill this function in
    pte_t *pgtable_entry_ptr = pgdir_walk(pgdir, va, false);
    if (pgtable_entry_ptr && ((*pgtable_entry_ptr) & PTE_P) == 1) {
        if (pte_store != NULL) {
            // pte_store not zero, store the address of pte of the page in it
            *pte_store = pgtable_entry_ptr;
        }
        // converts from pa to page and returns
        physaddr_t pa = PTE_ADDR(*pgtable_entry_ptr);
        return pa2page(pa);
    } else {
        // no page mapped at va
        return NULL;
    }
    return NULL;
}

// In page_remove():
void page_remove(pde_t *pgdir, void *va) {
    // Fill this function in
    pte_t *pgtable_entry_ptr = NULL;
    // use page_lookup to get struct PageInfo
    struct PageInfo *page = page_lookup(pgdir, va, &pgtable_entry_ptr);
    if (page && pgtable_entry_ptr) {
        // if page mapped at va
        // decrease and try to free page
        page_decref(page);
        // set page table entry to 0
        *pgtable_entry_ptr = 0;
        // invalidate tlb
        tlb_invalidate(pgdir, va);
    }
}

// In page_insert():
int page_insert(pde_t *pgdir, struct PageInfo *pp, void *va, int perm) {
    // Fill this function in
    // try to get pointer to page table entry, created if needed
    pte_t *pgtable_entry_ptr = pgdir_walk(pgdir, va, true);
    if (!pgtable_entry_ptr) {
        // page table cannot be allocated
        return -E_NO_MEM;
    }

    // increase reference ahead of insertion to process CORNER CASE
    pp->pp_ref++;

    if (((*pgtable_entry_ptr) & PTE_P) != 0) {
        // exists page mapped at va
        // remove page and invalidate tlb
        page_remove(pgdir, va);
    }

    // get physical address of page
    physaddr_t pa = page2pa(pp);
    // insert page into page table
    *pgtable_entry_ptr = pa | perm | PTE_P;

    // update permission flags of corresponding page directory
    pgdir[PDX(va)] = pgdir[PDX(va)] | perm;

    return 0;
}

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

//////////////////////////////////////////////////////////////////////
// Map 'pages' read-only by the user at linear address UPAGES
// Permissions:
//    - the new image at UPAGES -- kernel R, user R
//      (ie. perm = PTE_U | PTE_P)
//    - pages itself -- kernel RW, user NONE
// Your code goes here:
boot_map_region(kern_pgdir, UPAGES, pages_size, PADDR(pages), PTE_U | PTE_P);

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

//////////////////////////////////////////////////////////////////////
// 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:
boot_map_region(kern_pgdir, KERNBASE, 0xffffffff - KERNBASE, 0, PTE_W | PTE_P);