MIT6.828 Lab2 part1 Physical Pag

环境

Ubuntu 20.04 64 位系统
Lab的地址:点击这里去Lab2

准备工作

因为在Lab1当中代码我写了很多注释在里面，并且还有修改了一些代码。所以我重新clone一份lab1。然后执行下面的命令就行:

git checkout -b lab2 origin/lab2
git merge lab1

这样一来应该就看到lab2新的一些文件出现了。接下来直接开始做lab2吧，虽然mit6.828要求学生做至少一个challenge,但是觉challenge都挺难的。我就没做。

Part1

这次不像Lab1一样对lab介绍的非常仔细。一上来就直接说把下面几个函数补充完整还是有被吓到。不过认真看代码里面的注释还是能知道实现的函数时干嘛的。在正式开始写代码之前，先看一下实际上内存的结构:

内存结构

在8086的时候，寻址范围时0-1MB。所以在32bit机器里面我们将大于1MB的内存叫extended memory。看具体的硬件，在32bit机器中extended memory最大可以到4GB。上面这幅图对page_init()的实现很重要。待会可以重新回来看。

另外一个很重要的结构就是PageInfo,每一个页都有自己对应的一个PageInfo。他有两个变量

struct PageInfo {
    struct PageInfo* pp_link;
    uint16_t pp_ref;
}

这个结构其实有点像链表的node，链表的node有一个变量next，这里的pp_link就是和next的作用差不多。因为系统当中所有科用的页我们使用一个链表来管理。暂时不了解也没关系，看接下来的代码实现应该可以理解的。

第一题 实现boot_alloc()
注释里说了他不是真正的physical memory alloctor。此时我们还没有初始化将所有的可用内存用链表串起来。因为我们在entry.S里面已经开启了paging，对照一下上图，有些地址是不能使用的，比如IO hole。所以他不是真正的allocator,只是在这里临时用一下。page_alloc()才是真正的内存分配函数。
先上答案在解释。

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.
    result = nextfree;
    nextfree = ROUNDUP(nextfree+n,PGSIZE);  //n决定了是直接返回可用的地址还是分配后再返回。

    if((uint32_t) nextfree - KERNBASE > (npages*PGSIZE)) {
        panic("next free memory address is out of memory");
    }

    //返回当前空闲的地址
    return result;
}

那个if判断是初始化了nextfree，这里一个比较取巧的写法就是end points to end of bss segment。然后第一次运行boot_alloc的时候条件成立，nextfree指向内核代码尾端4kb对齐的第一个字节。后面的内存都是空的，可以随便使用。要求完成的代码按照注释应该可以理解，不再过多解释。注意，如果申请的内存大于物理内存大小，应该panic，所以要加一个判断。哦对了,npages是系统所有的页的数量，在i386_detect_memory中计算好的。所以系统可用的内存大小:npages*PGSIZE。

第二题 补充mem_init()中的代码
现在我们分配内存的函数已经实现了，接下来就是存放pages这个数组。所以思路很简单，只要计算出所有的PageInfo一共需要多少内存(一个page对应一个PageInfo)，然后把boot_alloc()的返回的地址赋值给pages就好

    pages = (struct PageInfo*) boot_alloc(npages * sizeof (struct PageInfo));
    memset(pages,0, npages* sizeof (struct PageInfo));

第三题 补充page_init() 的代码
这题的关键就是看一下上面的图，还有就是注释里面的内容。前面说过,用链表来管理所有空闲的页，指针page_free_list就是链表的表头。指针的内容是某个PageInfo的地址。下图帮助理解:

示意图

画的很难看，不过大概意思应该是明确了。page_free_list将所有的空闲PageInfo串起来。PageInfo中，1表示被用，0表示空闲。关于链表的插入，我们的代码实现的使用头插法。
EXPTHSNEN这个就是IO hole顶部的地址0x10000。在extended memory当中，有一部分内存已经被内核使用了，那么我们如何知道内核使用了到哪里了？答案就是用boot_alloc(0)，当参数为0的时候boot_alloc会返回当前的空闲地址。0x10000(IO hole的顶部) 到 boot_alloc(0)这一块都被内存使用了。另外，因为我们现在已经开启了paging，现在都是地址都是虚拟地址，所以还需要将boot_alloc(0)得到的虚拟地址用PADRR（）转为物理地址。本题的代码实现如下，注意结合注释来理解:

void page_init(void)
{

    pages[0].pp_ref = 1;

    // IO hole之前的内存都是free的
    size_t i ;
    for ( i = 1; i < npages_basemem; i++) {
        pages[i].pp_ref = 0;

        //这里设想一下链表的头插法就理解了！
        pages[i].pp_link = page_free_list;

        //&pages[i]并不是真正的空闲页的地址，这是Pages这个数组中的元素的地址
        //page2pa这个函数才是得到真正的地址的。
        page_free_list = &pages[i];
    }

    //IO hole
    for(; i < EXTPHYSMEM/PGSIZE; i++) {
        pages[i].pp_ref = 1;
    }

    //Kernel占据了从0x0010_0000 - 0x0fff_ffff，这一部分是kernel的 
    //所以第一个空闲的页就紧跟在内核之后，所以 end of IO hole ~ first free page 就是内核占据的内存
    ///PADDR是将虚拟地址转为实际的物理地址
    physaddr_t first_free_addr = PADDR(boot_alloc(0));
    size_t first_free_page = first_free_addr/PGSIZE;

    for(; i < first_free_page; i++) {
        pages[i].pp_ref = 1;
    }

    //内核之后的所有内存都是free的
    for(; i < npages; i++ ) {
        pages[i].pp_ref = 0;
        pages[i].pp_link = page_free_list;
        page_free_list = &pages[i];
    }

}

第四题 实现page_alloc()
在上一题我们已经将所有空闲的页表的PageInfo用page_free_list串起来。所以新分配一个页只需要从pagr_free_list空闲的第一个取出即可。注释里面还要我们去完成if(alloc & ALLOC_ZERO)条件成立，将对应页内的内容都改为0。Hint:使用page2kva（）这个函数来获得对应页的虚拟地址，用memset()来设置内存的值。还有一点就是注释里说了不要增加pp_ref，让caller去做这件事。注释说的还是比较清楚的。直接给代码实现；

struct PageInfo * page_alloc(int alloc_flags)
{
    // Fill this function in
    if( page_free_list == NULL) {
        return NULL;
    }
    struct PageInfo* next = page_free_list;
    page_free_list = page_free_list->pp_link;
    next->pp_link = NULL;

    if(alloc_flags & ALLOC_ZERO) {
        /*
        static inline void*
        page2kva(struct PageInfo *pp)
        {
            return KADDR(page2pa(pp));
        }

        */
        //获得下一个可用的地址的虚拟地址，然后设置一个PGSIZE大小的都为0
        void* va = page2kva(next);
        memset(va,'\0',PGSIZE);
    }
    //新分配的页在pages
    return next;
}

第五题 实现page free
这题就比较简单了。如果前面都理解了，free一个page只需要将它放回到page_free_list当中就行，还是使用我们熟悉的头插法就行。如果pp_ref > 0或者pp_link != null说明这个PageInfo要么是还在被使用，要么就是本来就在page_free_list当中(因为只有在page_free_list中pp_link才会不为NULL)。被使用的是时候显然不能放回到page_free_list当中。如果本来就在page_free_list中，就没意义了还会出错。代码实现如下:

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("This page is still inused or already in page free list, fail to free it ");
    }

    //头插法
    pp->pp_link = page_free_list;
    page_free_list = pp;
}

所有的工作完成后，make一下，然后在make qemu。正确了就会看到sucessed。我下面的截图是lab1,lab2,lab3都做完的结果。实际上的应该是输出check_page_free_list() succeeded! 和check_page_alloc() succeeded ! 即可

实验结果