【施工完毕】MIT 6.828 lab 2: Memory Management

Posted by 111qqz on Thursday, February 14, 2019

TOC

2019年2月24:完成了除了"Challenge"以外的全部练习和问题. 总共花费15个小时.

2019年2月26:完成"Challenge 2”(应该是最简单的一个orz,只花了不到一个小时)

Part 1: Physical Page Management

操作系统必须时刻追踪哪些物理内存在使用,哪些物理内存没有在使用。

一个问题是,

Ex 1. In the file kern/pmap.c, you must implement code for the following functions (probably in the order given).

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

check_page_free_list() and check_page_alloc() test your physical page allocator. You should boot JOS and see whether check_page_alloc() reports success. Fix your code so that it passes. You may find it helpful to add your own assert()s to verify that your assumptions are correct.

练习1要求写一个physical page allocator。我们先看第一个函数boot_alloc()

// 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.
    //  ???
    // how to allocate a memoty chunk?
    // how to decide how many PA left?
    // LAB 2: Your code here.

    return NULL;
}

这个函数只有在JOS初始化虚拟内存之前会被调用一次。

通过查看 mem_init 函数可以知道,boot_alloc 是用来初始化页目录(page directory)

为什么我们需要一个单独的page allocator呢?原因是:

kernel启动时需要将物理地址映射到虚拟地址,而我们需要一个page table来记录这种映射关系。但是创建一个page table涉及到为page table所在的page分配空间…而为一个page分配空间需要在将物理地址映射到虚拟地址以后。。

解决办法是,使用一个单独的page allocator,在一个固定的位置allocate memory. 然后在这部分去做初始化的工作。

参考xv6-book:

There is a bootstrap problem: all of physical memory must be mapped in order for the allocator to initialize the free list, but creating a page table with those mappings involves allocating page-table pages. xv6 solves this problem by using a separate page allocator during entry, which allocates memory just after the end of the kernel’s data segment. This allocator does not support freeing and is limited by the 4 MB mapping in the entrypgdir, but that is sufficient to allocate the first kernel page table.

这个函数有两个难点,第一个是,如何才能"allocate memory”? 说到"allocate memory"总是想到malloc…但是现在我们什么都没有…

然而实际上很简单(虽然我卡了好一会。。。),我们只要计算出第一个虚拟地址就好了。根据注释, magic symbol ‘end’位于没有被任何kernel code或全局变量占用的虚拟地址的起始位置。

第二个是,如何确定何时空间不够? 我们观察函数i386_detect_memory

static void
i386_detect_memory(void)
{
    size_t basemem, extmem, ext16mem, totalmem;

    // Use CMOS calls to measure available base & extended memory.
    // (CMOS calls return results in kilobytes.)
    basemem = nvram_read(NVRAM_BASELO);
    extmem = nvram_read(NVRAM_EXTLO);
    ext16mem = nvram_read(NVRAM_EXT16LO) * 64;

    // Calculate the number of physical pages available in both base
    // and extended memory.
    if (ext16mem)
        totalmem = 16 * 1024 + ext16mem;
    else if (extmem)
        totalmem = 1 * 1024 + extmem;
    else
        totalmem = basemem;

    npages = totalmem / (PGSIZE / 1024);
    npages_basemem = basemem / (PGSIZE / 1024);

    cprintf("Physical memory: %uK available, base = %uK, extended = %uK\n",
        totalmem, basemem, totalmem - basemem);
}

发现这个函数的作用是得到剩余的物理内存。其中basemem就是0-640k之间的memory,extmem是1M以后的memory.

npages是剩余物理内存的页数,每页的大小是PGSIZE。因此一共能分配的空间大小为(npages*PGSIZE)

而虚拟地址的base为KERNBASE(定义在inc/memlayout.h中),因此最大能访问的虚拟地址为KERNBASE+(npages*PGSIZE)

最后的实现为:

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.
    // end 就是虚拟地址的初始位置
    if (!nextfree) {
        extern char end[];
        nextfree = ROUNDUP((char *) end, PGSIZE);
        cprintf("end:x nextfree:x\n",end,nextfree);
    }

    // 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.
    cprintf("boot_alloc!\n");
    if ( 0 == n) return nextfree;

    nextfree = ROUNDUP((char *)(nextfree+n),PGSIZE);
    //uint32_t x = (uint32_t)nextfree;
    // cprintf("nextfree :x\n",x);
    if ((uint32_t)nextfree>(KERNBASE+npages*PGSIZE))
    {
        panic("boot_alloc: there is no enough space\n");
    }

    return nextfree;
}

接下来的部分就相对简单了。首先是mem_init,初始化PageInfo,由于是在page_init之前,不能使用page_alloc,因此这部分allocate也是由boot_alloc完成的。这也是唯二的由boot_alloc来分配内存的部分。代码如下:

    pages = (struct PageInfo *)boot_alloc(sizeof(struct PageInfo)*npages);
    memset(pages,0,sizeof(struct PageInfo)*npages);
    cprintf("page_info_end_VA:x\n",pages+sizeof(struct PageInfo)*npages);

接下来是page_init.这部分主要是判断哪些page是free的,哪些不是,参考注释,主要是[EXTPHYSMEM,…)这部分。 我们知道,对于EXTPHYSMEM之上的内存空间,首先kernel占用的空间,kernel之后是分配给kern_pgdir的空间,再然后是分配给PageInfo的空间。这之后的空间,应该都是可用的。因此代码如下:

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?
    //
    //
    //   [EXTPHYSMEM,...)中,最开始是kernel,然后是分配给了page_dir,接着是npages个struct PageInfo.
    //   这之后的空间应该都是free的
    //
    // Change the code to reflect this.
    // NB: DO NOT actually touch the physical memory corresponding to
    // free pages!
    size_t i;
    cprintf("page_free_list:x\n",page_free_list);
    // 倒序的?
    //
    pages[0].pp_ref = 1;
    pages[0].pp_link = page_free_list; // null
    for (i = 1; i < npages_basemem; i++) {
        pages[i].pp_ref = 0;
        pages[i].pp_link = page_free_list;
        page_free_list = &pages[i];
    }
    int npages_extmem = EXTPHYSMEM/PGSIZE;
    int npages_freeextmem = ((uint32_t)(struct PageInfo *)(pages + npages)-KERNBASE)/PGSIZE;
    for ( int i = npages_freeextmem ; i < npages ; i++)
    {
        pages[i].pp_ref = 0 ;
        pages[i].pp_link = page_free_list;
        page_free_list = &pages[i];
    }
    // debug
    cprintf("EXTPHYSMEM:x\n",EXTPHYSMEM);
    cprintf("npages:%d\n",npages);
    cprintf("npages_IO:%d\n",IOPHYSMEM/PGSIZE);
    cprintf("npages_extmem:%d npages_freeextmem:%d \n",npages_extmem,npages_freeextmem);
    cprintf("npages_extmem_VA:x\n",page2kva(&pages[npages_extmem]));
}

再然后是page_alloc函数。其实就是取一个链表头的操作。

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;
    memset(page2kva(ret),0,PGSIZE);
    if (alloc_flags & ALLOC_ZERO)
    {
        memset(page2kva(ret),'\0',PGSIZE);
    }
    // cprintf("ret:x\n",ret);
    return ret;
}

再之后的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.
    if (pp->pp_ref!=0 || pp->pp_link)
    {
        panic("page_free: pp_ref is nonzero or pp_link is not NULL");
    }
    // how to return something in a void function?
    // 相当于在链表头插入一个节点
    pp->pp_link = page_free_list;
    page_free_list = pp ;
}

到现在,练习1就算完成了。怎么知道我们的实现是对的呢,启动JOS,断言应该挂在page_insert处,并且make grade显示Physical page allocator: OK  就应该是没问题了。

Part 2: Virtual Memory

首先明确一下virtual address,liner address, physical address

简单来说,virtual address就是应用程序使用的地址,包括指针之类的值.

liner address 是virtual address经过segment translation 得到的.

Physical addresses 是 linear addresses 经过paging得到的.

具体来说:

**_Virtual addresses_** are used by an application program. They consist of a 16-bit selector and a 32-bit offset. In the flat memory model, the selectors are preloaded into segment registers CS, DS, SS, and ES, which all refer to the same linear address. They need not be considered by the application. Addresses are simply 32-bit near pointers.

Linear addresses are calculated from virtual addresses by segment translation. The base of the segment referred to by the selector is added to the virtual offset, giving a 32-bit linear address.** Under RTTarget-32, virtual offsets are equal to linear addresses since the base of all code and data segments is 0.**

Physical addresses are calculated from linear addresses through paging. The linear address is used as an index into the Page Table where the CPU locates the corresponding physical address. If paging is not enabled, linear addresses are always equal to physical addresses. Under RTTarget-32, linear addresses are equal to physical addresses except for remapped RAM regions

放几张重要的图:

详细情况可以参考Intel 80386 Reference Programmer’s Manual Chapter 5 Memory Management  建议通读,非常短,却又把最重要的内容都讲清楚了.

练习3和question 1都比较水,不说了.

接下来说练习4

ex4 In the file kern/pmap.c, you must implement code for the following functions.
        pgdir_walk()
        boot_map_region()
        page_lookup()
        page_remove()
        page_insert()

check_page(), called from mem_init(), tests your page table management routines. You should make sure it reports success before proceeding.

比较重要的是mmu.h文件,里面有很多有用的宏.

由于要把所有函数都实现完成才能跑通…所以比之前的练习稍微困难了一点…

首先是pgdir_walk函数的实现. 实现的时候有几个地方需要考虑.

第一个是根据注释”The relevant page table page might not exist yet.”

那么如何判断一个page是否存在?答案是使用present bit,** (*pgdir_entry & PTE_P)为True则表示一个page存在.**

第二个是create一个page的时候,需要两部分. page frame address和各种权限位.  page_alloc返回的是PageInfo* ,可以用page2pa得到对应的物理地址.

权限位的设置可以参考6.4 Page-Level Protection  或者下图

然后第三点,返回的是一个pointer,必须是VA,需要做相应的转换.

// 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 PageInfo * 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 manipulate page
// table and page directory entries.
//
pte_t *
pgdir_walk(pde_t *pgdir, const void *va, int create)
{
    // Fill this function in
    //cprintf("*pgdir:x *va:x\n",*pgdir, va);
    pte_t * pgdir_entry = &pgdir[PDX(va)];
    bool page_exist = (*pgdir_entry & PTE_P);
    //cprintf("page_exist %d\n",page_exist);
    struct PageInfo * pginfo;
    if (!page_exist)
    {
        if (!create) return NULL;
        else
        {
            pginfo = page_alloc(1);
            //cprintf("pginfo in pgdir_walk:x\n",pginfo);
            if (!pginfo) return NULL;
            pginfo->pp_ref++;
            // 要添加的权限参考 https://pdos.csail.mit.edu/6.828/2018/readings/i386/s06_04.htm
            *pgdir_entry = (pte_t)page2pa(pginfo) | PTE_U | PTE_W | PTE_P;
            // return pgdir_entry;
        }
    }
    // what if pre_t present bit is 0?
    // 注意PTE_ADDR返回的是物理地址,而一个pointer应该指向一个虚拟地址。
    //
    pte_t * pgtable_entry = (pte_t *)KADDR(PTE_ADDR(*pgdir_entry))+PTX(va);
    page_exist = (*pgtable_entry &PTE_P);
	
    // 提示1有什么作用? 怎么判断page table page是否存在? 
    // 用present bhttps://pdos.csail.mit.edu/6.828/2018/readings/i386/s06_04.htmit 判断?
    return pgtable_entry;
}

接下里是boot_map_region.  由于各种参数已经保证了对齐PGSIZE…所以也没什么cornor case.

唯一值得强调的是,map一个VA到PA的含义,其实就是将VA对应的page entry的page frame address设置为PA.

//
// map一个VA到PA的含义,其实就是将VA对应的page entry的地址设置为PA.
// Map [va, va+size) of virtual address space to physical [pa, pa+size)
// in the page table rooted at pgdir.  Size is a multiple of PGSIZE, and
// va and pa are both page-aligned.
// Use permission bits perm|PTE_P for the entries.
//
// This function is only intended to set up the ``static'' mappings
// above UTOP. As such, it should *not* change the pp_ref field on the
// mapped pages.
//
// Hint: the TA solution uses pgdir_walk
static void
boot_map_region(pde_t *pgdir, uintptr_t va, size_t size, physaddr_t pa, int perm)
{
    // Fill this function in
    size_t  num = size/PGSIZE;
    for ( size_t i = 0 ; i < num ; i++)
    {
        uintptr_t cur_va = va + i*PGSIZE;
        pte_t * entry = pgdir_walk(pgdir,(const void*)cur_va,1);
        if (!entry)
        {
            panic("pgdir_walk return NULL!");
        }
        physaddr_t cur_pa = pa + i*PGSIZE;
        *entry = cur_pa | perm | PTE_P;
    }
}

接下来是page_lookup,作用是从va得到映射到该位置的page的信息.

一开始少判断了一种情况,就是忘记检查返回的*entry,导致一个assert(!page_alloc(0)); 一直过不去…调了蛮久orz

// Return 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.  This is used by page_remove and
// can be used to verify page permissions for syscall arguments,
// but should not be used by most callers.
//
// Return NULL if there is no page mapped at va.
//
// Hint: the TA solution uses pgdir_walk and pa2page.
//
struct PageInfo *
page_lookup(pde_t *pgdir, void *va, pte_t **pte_store)
{
    // Fill this function in
    pte_t * entry = pgdir_walk( pgdir, va, 0);
    if (!entry) return NULL;
    if (pte_store)
    {
        *pte_store =  entry;
    }
    bool exist = *entry & PTE_P;
    if (!exist) return NULL;

    physaddr_t pa = PTE_ADDR(*entry);
    cprintf("pa in lookup: x\n",pa);
    struct PageInfo* ret = pa2page(pa);
    return ret;
}

下来是page_remove.

// 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, void *va)
{
    // Fill this function in
    pte_t *entry;
    struct PageInfo * pginfo = page_lookup(pgdir,va,&entry);
    //cprintf("VA in page_remove:x\n",va);
    //cprintf("pginfo in page_remove:x\n",pginfo);
    if (!pginfo) return;
    page_decref(pginfo);
    //pte_t * entry = pgdir_walk(pgdir,va,0);
    //if (!entry) return;
    *entry = 0;
    tlb_invalidate(pgdir,va);
    //check
    //entry = pgdir_walk(pgdir,va,0);
    //cprintf(" va: x entry after page_remove: x\n",va, *entry);
}

接下来是page_insert.

被坑的一个点是…错误码是带负号的…滑稽

然后我的实现中用了page_lookup…其实不用也完全可以…但是觉得使用page_lookup检查某一个va是否有page存在的逻辑更加合理…

// 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.
// However, try not to distinguish this case in your code, as this
// frequently leads to subtle bugs; there's an elegant way to handle
// everything in one code path.
//
//
// RETURNS:
//   0 on success
//   -E_NO_MEM, if page table couldn't be allocated
//
// Hint: The TA solution is implemented using pgdir_walk, page_remove,
// and page2pa.
//
 
int
page_insert(pde_t *pgdir, struct PageInfo *pp, void *va, int perm)
{
    // Fill this function in
    physaddr_t pa = page2pa(pp);
    //pte_t *entry = pgdir_walk(pgdir,va,1);
    pte_t *entry;
    struct PageInfo * pginfo = page_lookup(pgdir,va,&entry);	
    bool exist = *entry & PTE_P;
    cprintf("*entry x exist %d pginfo x\n",*entry,exist,pginfo);
    if (pginfo!=NULL)
    {
        if (PTE_ADDR(*entry)== pa)
        {
            *entry = pa | perm | PTE_P;
            return 0;
        }
        else
        {
            page_remove(pgdir,va);
        }
    }
    entry = pgdir_walk(pgdir,va,1);
    if (!entry)
    {
        return -E_NO_MEM;
        // 我服了。。错误码还带符号的。。。
    }
    *entry = pa | perm | PTE_P;
    pp->pp_ref++;
    //cprintf("check_va2pa:x\n",check_va2pa(pgdir,PGSIZE));
    return 0;
}

Part 3: Kernel Address Space

JOS把地址空间整体分为两部分,用户环境和kernel. 这条分界线在ULIM. 具体可以参考memlayout.h中的图.

JOS会把物理地址[0x00000000 ,0x0fffffff] 的256MB空间映射到虚拟空间[0xf0000000 ,0xffffffff ]

做这个地址映射原因之一是"One reason JOS remaps all of physical memory starting from physical address 0 at virtual address 0xf0000000 is to help the kernel read and write memory for which it knows just the physical address”

/*
 * Virtual memory map:                                Permissions
 *                                                    kernel/user
 *
 *    4 Gig -------->  +------------------------------+
 *                     |                              | RW/--
 *                     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 *                     :              .               :
 *                     :              .               :
 *                     :              .               :
 *                     |~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~| RW/--
 *                     |                              | RW/--
 *                     |   Remapped Physical Memory   | RW/--
 *                     |                              | RW/--
 *    KERNBASE, ---->  +------------------------------+ 0xf0000000      --+
 *    KSTACKTOP        |     CPU0's Kernel Stack      | RW/--  KSTKSIZE   |
 *                     | - - - - - - - - - - - - - - -|                   |
 *                     |      Invalid Memory (*)      | --/--  KSTKGAP    |
 *                     +------------------------------+                   |
 *                     |     CPU1's Kernel Stack      | RW/--  KSTKSIZE   |
 *                     | - - - - - - - - - - - - - - -|                 PTSIZE
 *                     |      Invalid Memory (*)      | --/--  KSTKGAP    |
 *                     +------------------------------+                   |
 *                     :              .               :                   |
 *                     :              .               :                   |
 *    MMIOLIM ------>  +------------------------------+ 0xefc00000      --+
 *                     |       Memory-mapped I/O      | RW/--  PTSIZE
 * ULIM, MMIOBASE -->  +------------------------------+ 0xef800000
 *                     |  Cur. Page Table (User R-)   | R-/R-  PTSIZE
 *    UVPT      ---->  +------------------------------+ 0xef400000
 *                     |          RO PAGES            | R-/R-  PTSIZE
 *    UPAGES    ---->  +------------------------------+ 0xef000000
 *                     |           RO ENVS            | R-/R-  PTSIZE
 * UTOP,UENVS ------>  +------------------------------+ 0xeec00000
 * UXSTACKTOP -/       |     User Exception Stack     | RW/RW  PGSIZE
 *                     +------------------------------+ 0xeebff000
 *                     |       Empty Memory (*)       | --/--  PGSIZE
 *    USTACKTOP  --->  +------------------------------+ 0xeeb 
 *                     |      Normal User Stack       | RW/RW  PGSIZE
 *                     +------------------------------+ 0xeebfd000
 *                     |                              |
 *                     |                              |
 *                     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 *                     .                              .
 *                     .                              .
 *                     .                              .
 *                     |~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~|
 *                     |     Program Data & Heap      |
 *    UTEXT -------->  +------------------------------+ 0x00800000
 *    PFTEMP ------->  |       Empty Memory (*)       |        PTSIZE
 *                     |                              |
 *    UTEMP -------->  +------------------------------+ 0x00400000      --+
 *                     |       Empty Memory (*)       |                   |
 *                     | - - - - - - - - - - - - - - -|                   |
 *                     |  User STAB Data (optional)   |                 PTSIZE
 *    USTABDATA ---->  +------------------------------+ 0x00200000        |
 *                     |       Empty Memory (*)       |                   |
 *    0 ------------>  +------------------------------+                 --+
 *
 * (*) Note: The kernel ensures that "Invalid Memory" is *never* mapped.
 *     "Empty Memory" is normally unmapped, but user programs may map pages
 *     there if desired.  JOS user programs map pages temporarily at UTEMP.
 */

接下来看练习5,要求初始化kernel address space.

Ex 5. Fill in the missing code in `mem_init()` after the call to `check_page()`.

Your code should now pass the check_kern_pgdir() and check_page_installed_pgdir() checks.

根据注释实现即可,没有什么难度(虽然因为写错个常数调了半天2333

boot_map_region(kern_pgdir,UPAGES,sizeof(struct PageInfo)*npages,PADDR(pages),PTE_U|PTE_P);
boot_map_region(kern_pgdir,KSTACKTOP-KSTKSIZE,KSTKSIZE,PADDR(bootstack),PTE_W|PTE_P);
//大失误! VA最高是2^32-1,十六进制为0xffffffff,不小心写成了1<<31(2^31)....  
boot_map_region(kern_pgdir,KERNBASE,0xffffffff-KERNBASE,0,PTE_W | PTE_P);// kernel pgdir

接下来来填表格,可以部分参考上面的layout图.

  2. **What entries (rows) in the page directory have been filled in at this point? What addresses do they map and where do they point? In other words, fill out this table as much as possible:**
Entry Base Virtual Address Points to (logically):
1023 0xff000000 Page table for top 4MB of phys memory
1022 0xfc000000 Page table for top *  of phys memory
. ? ?
. ? ?
. ? ?
960 0xf0000000 kernel
959 0xefc00000 cpu0's kernel stack(0xefff8000),cpu1's kernel stack(0xeffe8000)
956

0xef000000

 npages of PageInfo(0xef000000)
952

0xee000000

 bootstack
. ? ?
2 0x00800000

Program Data & Heap

1 0x00400000

Empty Memory

0 0x00000000

Empty Memory

接下来回答几个问题:

3.We have placed the kernel and user environment in the same address space. Why will user programs not be able to read or write the kernel’s memory? What specific mechanisms protect the kernel memory?

对于JOS来说,主要就是"page-level protection"在起作用. 具体来说,就是PTE_W还有PTE_U两个bit.

4.What is the maximum amount of physical memory that this operating system can support? Why?

最大能支持256MB.因为KERNBASE到4GB之间只有这么大的空间.

如果需要支持更大的物理内存,至少需要先将KERNBASE设置为一个较低的值.

5.How much space overhead is there for managing memory, if we actually had the maximum amount of physical memory? How is this overhead broken down?

让我们来看看我们为了管理内存,我们都做了什么.

首先是一个page dir,大小为一个PGSIZE个字节,也就是4KB

然后是npages个PageInfo,大小为0x40000个字节,也就是256KB

然后是将物理地址的256MB映射到KERNBASE以上的地址,对应于page table [960,1024)共64个page table.每个page table需要PGSIZE个字节,所以一共是64*4096 byte,也就是256KB

6.Revisit the page table setup in kern/entry.S and kern/entrypgdir.c. Immediately after we turn on paging, EIP is still a low number (a little over 1MB). At what point do we transition to running at an EIP above KERNBASE? What makes it possible for us to continue executing at a low EIP between when we enable paging and when we begin running at an EIP above KERNBASE? Why is this transition necessary?

jmp    *x 之后EIP才在KERNBASE地址以上运行. 开了paging却还可以在地地址执行的原因是VA[0,4MB)也被映射到了PA[0,4MB)

这是必要的,原因参见Lab1 “Operating system kernels often like to be linked and run at very high virtual address, such as 0xf0100000, in order to leave the lower part of the processor’s virtual address space for user programs to use.”

那么到现在为止,挑战以外的题目就全部完成了.

Challenge! Extend the JOS kernel monitor with commands to:
  * Display in a useful and easy-to-read format all of the physical page mappings (or lack thereof) that apply to a particular range of virtual/linear addresses in the currently active address space. For example, you might enter 'showmappings 0x3000 0x5000' to display the physical page mappings and corresponding permission bits that apply to the pages at virtual addresses 0x3000, 0x4000, and 0x5000.
  * Explicitly set, clear, or change the permissions of any mapping in the current address space.
  * Dump the contents of a range of memory given either a virtual or physical address range. Be sure the dump code behaves correctly when the range extends across page boundaries!
  * Do anything else that you think might be useful later for debugging the kernel. (There's a good chance it will be!)

迫于太菜了。。。选了这个可能是最简单的题目。。。实现也很无脑。。。就是模拟

// Simple command-line kernel monitor useful for
// controlling the kernel and exploring the system interactively.

#include <inc/stdio.h>
#include <inc/string.h>
#include <inc/memlayout.h>
#include <inc/assert.h>
#include <inc/x86.h>

#include <kern/console.h>
#include <kern/monitor.h>
#include <kern/kdebug.h>

#include <kern/pmap.h>   // for challenge 2 in lab2
#define CMDBUF_SIZE	80	// enough for one VGA text line


struct Command {
    const char *name;
    const char *desc;
    // return -1 to force monitor to exit
    int (*func)(int argc, char** argv, struct Trapframe* tf);
};

static struct Command commands[] = {
    { "help", "Display this list of commands", mon_help },
    { "kerninfo", "Display information about the kernel", mon_kerninfo },
    {"backtrace","Display infomation about the call stack", mon_backtrace },
    {"map"," display the physical mappings that apply to a particular range of virtual addresses",mon_showmappings},
    {"setPTE_P","set the flag of PTE_P",mon_setPTE_P},
    {"clearPTE_P","clear the flag of PTE_P",mon_clearPTE_P},
    {"setPTE_W","set the flag of PTE_W",mon_setPTE_W},
    {"clearPTE_W","clear the flag of PTE_W",mon_clearPTE_W},
    {"setPTE_U","set the flag of PTE_U",mon_setPTE_U},
    {"clearPTE_U","clear the flag of PTE_U",mon_clearPTE_U},
    {"change_flags","change the permission",mon_change_flags},
    {"mem","dump the contents of a range VA/PA address range ",mon_mem}
};

/***** Implementations of basic kernel monitor commands *****/

int
mon_help(int argc, char **argv, struct Trapframe *tf)
{
    int i;

    for (i = 0; i < ARRAY_SIZE(commands); i++)
        cprintf("%s - %s\n", commands[i].name, commands[i].desc);
    return 0;
}

int
mon_kerninfo(int argc, char **argv, struct Trapframe *tf)
{
    extern char _start[], entry[], etext[], edata[], end[];

    cprintf("Special kernel symbols:\n");
    cprintf("  _start                  x (phys)\n", _start);
    cprintf("  entry  x (virt)  x (phys)\n", entry, entry - KERNBASE);
    cprintf("  etext  x (virt)  x (phys)\n", etext, etext - KERNBASE);
    cprintf("  edata  x (virt)  x (phys)\n", edata, edata - KERNBASE);
    cprintf("  end    x (virt)  x (phys)\n", end, end - KERNBASE);
    cprintf("Kernel executable memory footprint: %dKB\n",
        ROUNDUP(end - entry, 1024) / 1024);
    return 0;
}

int
mon_backtrace(int argc, char **argv, struct Trapframe *tf)
{
    // Your code here.
    uint32_t *ebp = (uint32_t*)read_ebp();
    cprintf("Stack backtrace:\n");
    int i ;
    struct Eipdebuginfo info;
    while (ebp)
    {	
        uint32_t eip = ebp[1];
        cprintf("ebp x  eip x  ",ebp,eip);
        cprintf("args");
        for ( i = 2 ; i < 7 ; i++)
        {
            cprintf(" x",*(ebp+i));
        }
        cprintf("\n");
        int status = debuginfo_eip(eip,&info);
        if (status == 0)
        {
 
          cprintf("%s:%d: ",info.eip_file,info.eip_line);
          cprintf("%.*s+%d\n",info.eip_fn_namelen,info.eip_fn_name,eip-info.eip_fn_addr);
        }	
        ebp = (uint32_t*)*ebp;
    }


    return 0;
}


int
mon_showmappings(int argc, char **argv, struct Trapframe *tf)
{
    if (argc<3)
    {
        cprintf("USAGE: map [startVA] [endVA] \n");
        return -1;
    }
    char * sstartVA = argv[1];
    char * sendVA = argv[2];
    //cprintf("[%s,%s]\n",sstartVA,sendVA);
    uintptr_t istartVA = strtol(sstartVA,NULL,16);
    uintptr_t iendVA = strtol(sendVA,NULL,16);
    //cprintf("int: [x,x]\n",istartVA,iendVA);
    int cnt = ((iendVA - istartVA)>>12)&0xFFFFFF;
    //cprintf("cnt %d\n",cnt);
    cprintf("virtual address   phycisal address  PTE_U  PTE_W  PTE_P\n");
    for ( int i = 0 ; i < cnt ; i++)
    {
        uintptr_t curVA = istartVA + i * 0x1000;
        cprintf("   x   ",curVA);
        pte_t * entry ;
        struct PageInfo *pginfo = page_lookup(kern_pgdir,(void *)curVA,&entry);
        if (!pginfo)
        {
            cprintf("       None     ");
            cprintf("       None ");
            cprintf("  None");
            cprintf("  None\n");
        }
        else
        {
            physaddr_t pa = PTE_ADDR(*entry);
            cprintf("       x    ",pa);
            cprintf("     %d      %d     %d\n",1-!(*entry&PTE_U),1-!(*entry&PTE_W),1-!(*entry&PTE_P));
        }
    }	
    return 0;
}

int
mon_setPTE_P(int argc, char **argv, struct Trapframe *tf)
{
    char *sVA = argv[1];
    uintptr_t VA = strtol(sVA,NULL,16);
    pte_t * entry = pgdir_walk(kern_pgdir,(void *)VA,0);
    if (!entry)
    {
        cprintf("Page table entry not exist!\n");
        return -1;
    }
    *entry = *entry | PTE_P;
    return 0;
}
int
mon_clearPTE_P(int argc, char **argv, struct Trapframe *tf)
{
    char *sVA = argv[1];
    uintptr_t VA = strtol(sVA,NULL,16);
    pte_t * entry = pgdir_walk(kern_pgdir,(void *)VA,0);
    if (!entry)
    {
        cprintf("Page table entry not exist!\n");
        return -1;
    }
    //cprintf("entry x\n",*entry);
    //cprintf(" PTE_p x\n",(~PTE_P));
     *entry = (*entry) & (~PTE_P);
    //cprintf("entry x\n",*entry);
    return 0;
}

	

int
mon_setPTE_W (int argc, char **argv, struct Trapframe *tf)
{
    char *sVA = argv[1];
    uintptr_t VA = strtol(sVA,NULL,16);
    pte_t * entry = pgdir_walk(kern_pgdir,(void *)VA,0);
    if (!entry)
    {
        cprintf("Page table entry not exist!\n");
        return -1;
    }
    *entry = *entry | PTE_W;
    return 0;

}

int
mon_clearPTE_W(int argc, char **argv, struct Trapframe *tf)
{
    char *sVA = argv[1];
    uintptr_t VA = strtol(sVA,NULL,16);
    pte_t * entry = pgdir_walk(kern_pgdir,(void *)VA,0);
    if (!entry)
    {
        cprintf("Page table entry not exist!\n");
        return -1;
    }
    *entry = (*entry) & (~PTE_W);
    return 0;

}

int
mon_setPTE_U(int argc, char **argv, struct Trapframe *tf)
{
    char *sVA = argv[1];
    uintptr_t VA = strtol(sVA,NULL,16);
    pte_t * entry = pgdir_walk(kern_pgdir,(void *)VA,0);
    if (!entry)
    {
        cprintf("Page table entry not exist!\n");
        return -1;
    }
    *entry = *entry | PTE_U;
    return 0;

}
int
mon_clearPTE_U(int argc, char **argv, struct Trapframe *tf)
{
    char *sVA = argv[1];
    uintptr_t VA = strtol(sVA,NULL,16);
    pte_t * entry = pgdir_walk(kern_pgdir,(void *)VA,0);
    if (!entry)
    {
        cprintf("Page table entry not exist!\n");
        return -1;
    }
    *entry = (*entry ) & (~PTE_U);
    return 0;

}

int
mon_change_flags(int argc, char **argv, struct Trapframe *tf)
{
    if (argc<3)
    {
        cprintf("USAGE: change_flags [VA] [permission] \n");
        return -1;
    }
    char *sVA = argv[1];
    char *sPer = argv[2];
    uintptr_t VA = strtol(sVA,NULL,16);
    int Per = strtol(sPer,NULL,10);
    //cprintf("Permission:%d\n",Per);
    pte_t *entry = pgdir_walk(kern_pgdir,(void *)VA,0);
    if (!entry)
    {
        cprintf("Page table entry not exist!\n");
        return -1;
    }
    *entry =( (*entry) & (~0x7) ) | Per;
    return 0;
}


int 
mon_mem(int argc, char **argv, struct Trapframe *tf)
{
    if (argc<4)
    {
        cprintf("usage: mem [VA/PA(start)]  [VA/PA(end)] P|V \n");
        return -1;
    }
    char *sstartA = argv[1];
    char *sendA = argv[2];
    char *type = argv[3];
    if (type[0]!='P'&&type[0]!='V')
    {
        cprintf("usage: mem [VA/PA(start)]  [VA/PA(end)] P|V \n");
        return -1;
    }


    uintptr_t startVA,endVA;
    if (type[0]=='P')
    {
        startVA = strtol(sstartA,NULL,16) + KERNBASE;
        endVA = strtol(sendA,NULL,16) + KERNBASE;
    }
    else 
    {
        startVA = strtol(sstartA,NULL,16);
        endVA = strtol(sendA,NULL,16);
    }
    startVA = ROUNDUP(startVA,4);
    endVA = ROUNDUP(endVA,4);
    int cnt = ((endVA - startVA)>>2);;
    cprintf("startVA: x endVA:x cnt:%d\n",startVA,endVA,cnt);
    for ( int i = 0 ; i < cnt ; i++)
    {
        void ** cur_VA = (void **)startVA + i;
        cprintf("[x]:x\n",cur_VA,*cur_VA);
    }

    return 0;
	
}


/***** Kernel monitor command interpreter *****/

#define WHITESPACE "\t\r\n "
#define MAXARGS 16

static int
runcmd(char *buf, struct Trapframe *tf)
{
    int argc;
    char *argv[MAXARGS];
    int i;

    // Parse the command buffer into whitespace-separated arguments
    argc = 0;
    argv[argc] = 0;
    while (1) {
        // gobble whitespace
        while (*buf && strchr(WHITESPACE, *buf))
            *buf++ = 0;
        if (*buf == 0)
            break;

        // save and scan past next arg
        if (argc == MAXARGS-1) {
            cprintf("Too many arguments (max %d)\n", MAXARGS);
            return 0;
        }
        argv[argc++] = buf;
        while (*buf && !strchr(WHITESPACE, *buf))
            buf++;
    }
    argv[argc] = 0;

    // Lookup and invoke the command
    if (argc == 0)
        return 0;
    for (i = 0; i < ARRAY_SIZE(commands); i++) {
        if (strcmp(argv[0], commands[i].name) == 0)
            return commands[i].func(argc, argv, tf);
    }
    cprintf("Unknown command '%s'\n", argv[0]);
    return 0;
}

void
monitor(struct Trapframe *tf)
{
    char *buf;

    cprintf("Welcome to the JOS kernel monitor!\n");
    cprintf("Type 'help' for a list of commands.\n");


    while (1) {
        buf = readline("K> ");
        if (buf != NULL)
            if (runcmd(buf, tf) < 0)
                break;
    }
}

有道词典

We have placed …

详细X

我们已经把内核和用户环境在同一地址空间。为什么将用户程序不能读或写内核的内存?具体机制保护内核内存?

「真诚赞赏,手留余香」

111qqz的小窝

真诚赞赏,手留余香

使用微信扫描二维码完成支付