ucore lab2_report

实验目的

• 理解基于段页式内存地址的转换机制
• 理解页表的建立和使用方法
• 理解物理内存的管理方法

实验内容

本次实验包含三个部分。首先了解如何发现系统中的物理内存；然后了解如何建立对物理内存的初步管理，即了解连续物理内存管理；最后了解页表相关的操作，即如何建立页表来实现虚拟内存到物理内存之间的映射，对段页式内存管理机制有一个比较全面的了解。本实验里面实现的内存管理还是非常基本的，并没有涉及到对实际机器的优化，比如针对 cache 的优化等。如果大家有余力，尝试完成扩展练习。

练习

为了实现lab2的目标，lab2提供了3个基本练习和2个扩展练习，要求完成实验报告。

对实验报告的要求：

• 基于markdown格式来完成，以文本方式为主
• 填写各个基本练习中要求完成的报告内容
• 完成实验后，请分析ucore_lab中提供的参考答案，并请在实验报告中说明你的实现与参考答案的区别
• 列出你认为本实验中重要的知识点，以及与对应的OS原理中的知识点，并简要说明你对二者的含义，关系，差异等方面的理解（也可能出现实验中的知识点没有对应的原理知识点）
• 列出你认为OS原理中很重要，但在实验中没有对应上的知识点

文件架构与执行流程

lab2的文件架构相对lab1产生了一些区别，在后面可以看到，这些区别的存在是必要的，都是为了操作系统可以正常地运行。下面简述一下lab2中各个文件执行的流程。

• 首先自然是bios的程序，在机器上电时被加载到0xffff0地址处，完成相关设备的初始化工作，并且到硬盘的主引导扇区读取bootloader到0x7c00地址处。
• 此后机器的控制权就交给了bootloader，首先是bootasm.S中的汇编代码开始执行，在其中完成CPU从实模式到保护模式的转换，为此需要首先使能A20地址线，初始化段表等，这些都是lab1里面就完成了的工作。与lab1不同的是，在bootasm.S中，还进行了对物理内存的探测工作，是通过bios系统调用来完成的。完成段表的建立与各个段寄存器的初始化后，就建立起了C语言的运行环境，程序转入bootmain.c中开始执行。
• bootmain.c::bootmain函数功能非常单一，即将存在于硬盘扇区中的操作系统内核读入内存中，并且通过分析elf格式文件找到内核的入口地址，从而转入内核开始运行。这里与lab1都是相同的，所不同的是这里并非直接转入kern/init/init.c中，而是转入kern/init/entry.S中运行。
• 在kern/init/entry.S中，更新了之前建立的段机制，从而可以将虚拟地址va映射到物理地址va - 0xC000000，保证了操作系统可以正常地运行。此后程序才进入kern/init/init.c::kern_init中运行。
• 在kern_init中进行各种设备的初始化工作，这里主要讨论pmm_init函数，即物理内存管理的初始化。
• 在pmm_init中，首先进行了物理内存管理器（physical memory manager）的初始化工作，利用之前对物理内存的探测工作，对所有的空闲物理内存通过一个free_area链表进行管理，这里对应了page_init函数。
• 此后就是完成了页表的建立（对应了boot_map_segment）函数，并且再次更新了段机制，完成了段页式的地址映射机制。这里的逻辑相对复杂，将在后面详细说明。

下面就将按照lab2中各个文件执行的步骤，来详细说明其中的具体操作，相关功能的实现，以及这样实现的原因。

物理内存的探测

lab2的实验目的，是要建立起对物理内存的管理机制，包括连续的内存分配算法（如first fit）以及非连续的段页式管理机制。但是在实现这些管理机制之前，首先需要知道当前的机器有多少的内存可用，它们的分布是怎么样的，从而将所有的空闲内存组织起来统一进行管理。所以就首先需要进行物理内存的探测工作。

探测物理内存是通过bios的中断调用实现的，由于bios中断调用只能在实模式下进行，所以相应的工作就需要在boot/bootasm.S中，完成实模式向保护模式的转换之前进行。具体探测的方法是调用参数为e820h的INT 15h的bios中断。bios通过系统内存映射地址描述符（Address Range Descriptor）格式来表示系统物理内存布局，该地址描述符分为三个字段，即内存的起始地址，连续内存的大小以及内存的状态或者类型（可用或者保留）。具体的细节其实查看INT 15系统调用的输入与输出来确定啊，这里就不详述了。下面是探测物理内存的汇编代码：

probe_memory:
    movl $0, 0x8000
    xorl %ebx, %ebx
    movw $0x8004, %di
start_probe:
    movl $0xE820, %eax
    movl $20, %ecx
    movl $SMAP, %edx
    int $0x15
    jnc cont
    movw $12345, 0x8000
    jmp finish_probe
cont:
    addw $20, %di
    incl 0x8000
    cmpl $0, %ebx
    jnz start_probe
finish_probe:

这段代码的功能就是利用bios系统调用INT 15来实现物理内存的探测，将返回的地址描述符放在es:di起始的内存处，这里即是0x8004处。此外可以看到，在地址0x8000处还存放了一个变量来保存探测到的物理内存块的数量，这样，在0x8000内存地址处，就存放了一个与下面结构体相对应的变量：

struct e820map {
    int nr_map;
    struct {
        uint64_t addr;
        uint64_t size;
        uint32_t type;
    } __attribute__((packed)) map[E820MAX];
};

在kern/mm/pmm.c::page_init函数中，即是通过这个结构体来建立起物理内存的页管理机制的。这个函数还将在后面详述。

第一次更新段映射机制

上面谈到，在lab2中，boot/bootmain.c::bootmain执行完后，并非是像lab1一样直接跳转到kern/init/init.c::kern_init函数执行，而是首先进入kern/init/entry.S，再转入init.c::kern_init函数。实际上，这样的操作是必要的，倘若没有经过这样的转换，操作系统内核将不能正常运行。

与lab1中一样，在lab2中操作系统内核也是被加载到物理地址为0x00100000的内存区段。所不同的是，lab2中的操作系统设定了虚拟地址空间，其中内核的起始地址为0xC0100000，这点在tools/kernel.ld文件中有所体现，该链接脚本文件是用于规定链接时的输出文件在程序地址空间的布局的，当然还有其他的功能。可以看到：

...
ENTRY(kern_entry)

SECTIONS {
    /* Load the kernel at this address: "." means the current address */
    . = 0xC0100000;

    .text : {
...

这里规定了内核的入口地址为kern_entry，即entry.S中的主函数，并且规定了操作系统是被加载到起始虚拟地址为0xC0100000的内存区段上。而操作系统被加载到的物理地址，则是由bootloader决定的。在boot/bootmain.c::bootmain中，可以看到：

...
	// load each program segment (ignores ph flags)
    ph = (struct proghdr *)((uintptr_t)ELFHDR + ELFHDR->e_phoff);
    eph = ph + ELFHDR->e_phnum;
    for (; ph < eph; ph ++) {
        readseg(ph->p_va & 0xFFFFFF, ph->p_memsz, ph->p_offset);
    }

    // call the entry point from the ELF header
    // note: does not return
    ((void (*)(void))(ELFHDR->e_entry & 0xFFFFFF))();
...

这里readseg函数的第一个参数，就是bootloader将内核加载到内存中的地址，由于此时建立的段表还是一对一对等映射，所以这里的加载地址就是物理地址。其中，ph->p_va就是在kernel.ld中设定的虚拟地址，所以操作系统内核实际上是被加载到起始物理地址为ph->p_va & 0xFFFFFF = 0x00100000的内存中。

从上面的讨论可以看出，lab2内核的物理地址与虚拟地址是不同的，它们之间的对应关系满足

virt addr - 0xC0000000 = phy addr

因此，如果直接从bootmain函数跳转进入内核的init.c::kern_init函数，由于此时的段机制还是对等映射，内核将不能正确得到要运行的代码与数据，此时显然是不可以运行的。所以在进入内核之前，我们首先需要在kern/entry.S中更新段机制，将虚拟地址映射到正确的与之对应的物理地址，此后才能进入内核。

需要注意的是，由于entry.S也是内核代码的一部分，因此其中涉及的内存地址都是虚拟地址，在访存时需要手动进行虚拟地址向物理地址的转化，才能访问到正确的内存空间，具体的代码如下：

#define REALLOC(x) (x - KERNBASE)

.text
.globl kern_entry
kern_entry:
    # reload temperate gdt (second time) to remap all physical memory
    # virtual_addr 0~4G=linear_addr&physical_addr -KERNBASE~4G-KERNBASE 
    lgdt REALLOC(__gdtdesc)
    movl $KERNEL_DS, %eax
    movw %ax, %ds
    movw %ax, %es
    movw %ax, %ss

    ljmp $KERNEL_CS, $relocated

relocated:

    # set ebp, esp
    movl $0x0, %ebp
    # the kernel stack region is from bootstack -- bootstacktop,
    # the kernel stack size is KSTACKSIZE (8KB)defined in memlayout.h
    movl $bootstacktop, %esp
    # now kernel stack is ready , call the first C function
    call kern_init
...
__gdt:
    SEG_NULL
    SEG_ASM(STA_X | STA_R, - KERNBASE, 0xFFFFFFFF)      # code segment
    SEG_ASM(STA_W, - KERNBASE, 0xFFFFFFFF)              # data segment
__gdtdesc:
    .word 0x17                                          # sizeof(__gdt) - 1
    .long REALLOC(__gdt)

实际上，这里的REALLOC(x)宏，就是实现虚拟地址向物理地址转换的工作的。可以看到，在entry.S中，重新更新了段表，使得虚拟地址能被映射到正确的物理地址。此后，就可以毫无禁忌地直接使用虚拟地址了。

练习1：实现 first-fit 连续物理内存分配算法（需要编程）

在实现first fit内存分配算法的回收函数时，要考虑地址连续的空闲块之间的合并操作。提示:在建立空闲页块链表时，需要按照空闲页块起始地址来排序，形成一个有序的链表。可能会修改default_pmm.c中的default_init，default_init_memmap，default_alloc_pages， default_free_pages等相关函数。请仔细查看和理解default_pmm.c中的注释。

请在实验报告中简要说明你的设计实现过程。请回答如下问题：

• 你的first fit算法是否有进一步的改进空间

空闲物理内存的页式管理

在进行对物理内存的分配与回收之前，肯定首先需要知道当前的空闲物理内存有哪些，从而才可以选择某一区段的内存进行分配啊。也就是说，首先我们是需要管理所有的空闲物理内存。通过之前的物理内存探测，我们已经可以知道哪些区域的物理内存是可用的，接下来，我们要建立页式物理内存管理机制，将物理内存组织成一个个固定大小的页帧来进行管理，并且建立起一个链表结构将这些空闲的内存块组织起来，进而实现内存的分配与回收工作。这部分的工作都是在kern/mm/pmm.c::page_init函数中实现的。

首先，需要将物理内存组织成一个个固定大小的页帧，这里页帧的大小固定为4K。为此，我们就需要知道物理内存的起始点与终止点，从而确定可以划分的页帧的数目，对于每一个物理页，都有一个与之对应的struct Page结构体与之对应，来表示该物理页的状态，如是否可用或者被操作系统保留。这部分的工作对应了page_init函数的前半部分：

/* *
 * struct Page - Page descriptor structures. Each Page describes one
 * physical page. In kern/mm/pmm.h, you can find lots of useful functions
 * that convert Page to other data types, such as phyical address.
 * */
struct Page {
    int ref;                        // page frame's reference counter
    uint32_t flags;                 // array of flags that describe the status of the page frame
    unsigned int property;          // the num of free block, used in first fit pm manager
    list_entry_t page_link;         // free list link
};

static void
page_init(void) {
    struct e820map *memmap = (struct e820map *)(0x8000 + KERNBASE);
    uint64_t maxpa = 0;

    cprintf("e820map:\n");
    int i;
    for (i = 0; i < memmap->nr_map; i ++) {
        uint64_t begin = memmap->map[i].addr, end = begin + memmap->map[i].size;
        cprintf("  memory: %08llx, [%08llx, %08llx], type = %d.\n",
                memmap->map[i].size, begin, end - 1, memmap->map[i].type);
        if (memmap->map[i].type == E820_ARM) {
            if (maxpa < end && begin < KMEMSIZE) {
                maxpa = end;
            }
        }
    }
    if (maxpa > KMEMSIZE) {
        maxpa = KMEMSIZE;
    }

    extern char end[];

    npage = maxpa / PGSIZE;
    pages = (struct Page *)ROUNDUP((void *)end, PGSIZE);

    for (i = 0; i < npage; i ++) {
        SetPageReserved(pages + i);
    }
    uintptr_t freemem = PADDR((uintptr_t)pages + sizeof(struct Page) * npage);
...
}

关于这段代码，有一些要说明的地方：

• 可以看到，函数一开始就是获得前面bios中断调用得到的地址描述符结构体，这里主要是利用它的信息来获得最大的物理地址maxpa，从而可以确定页面的数量。这里的KMEMSIZE宏是代表了当前机器的最大内存量。
• 程序的后半部分，就建立起了结构数组Struct Page* pages，对于每一个物理页面，pages数组都有一项的Struct Page与之对应，并且首先将所有的页面都初始化为[保留的]，对应于SetPageReserved(pages + i);。
• 这里的全局变量char end[]并非是在代码文件里面定义的，而是在kernel.ld中

...
/* The data segment */
    .data : {
        *(.data)
    }

    PROVIDE(edata = .);

    .bss : {
        *(.bss)
    }

    PROVIDE(end = .);
...

可见，这里的end变量是代表bss段的结束地址，也就是操作系统内核被加载到内存中的结束地址。通过设置pages = (struct Page *)ROUNDUP((void *)end, PGSIZE);，表示pages数组是被存放在内存中紧跟在操作系统内核后面，被圆整到一个页帧大小的整数倍的区域中，而后面的freemem变量则是表示存放完pages数组之后，内存中空闲的区域。这样，我们可以物理内存的结构分布图：

/* *
 * Physical memory map:                                                                                                       
 *
 *                            +---------------------------------+
 *                            |                                 |
 *                            |         Free Memory (*)         |
 *                            |                                 |
 *     freemem -------------> +---------------------------------+
 *                            |       Struct Page *pages        | 
 *     pages ---------------> +---------------------------------+ 
 *                            |        Invalid Memory (*)       | 
 *     end kern ------------> +---------------------------------+ 
 *                            |                                 |
 *                            |             KERNEL              | 
 *                            |                                 |
 *     load addr -----------> +---------------------------------+ 0x00100000
 *                            |                                 |
 *                            |                                 |
 *                            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~0x000000000
 *
 * */

在对物理内存进行分页之后，我们需要再次利用e820map的信息，找到所有空闲的页面，并将这些页面组织到一起集中进行管理，这也就是page_init后半部分进行的工作：

...
for (i = 0; i < memmap->nr_map; i ++) {
    uint64_t begin = memmap->map[i].addr, end = begin + memmap->map[i].size;
    cprintf("[begin, end]: [%08llx, %08llx]\n", begin, end);
    if (memmap->map[i].type == E820_ARM) {
        if (begin < freemem) {
            begin = freemem;
        }
        if (end > KMEMSIZE) {
            end = KMEMSIZE;
        }
        if (begin < end) {
            begin = ROUNDUP(begin, PGSIZE);
            end = ROUNDDOWN(end, PGSIZE);
            if (begin < end) {
                init_memmap(pa2page(begin), (end - begin) / PGSIZE);
            }
        }
    }
}

可以看到，这里的核心函数是init_memmap，它的作用是将起始地址为begin的若干个连续的页面，保存到kern/mm/default_pmm.c中定义的free_area变量中，表示该连续页面是空闲的，可用于后续的分配操作。这个free_area变量其实非常神奇，它是类似于一种链式数组，就是说它只保存各个连续的空闲页的起始页，通过pages数组就可以轻易地访问到该起始页后面连续的空闲页面，不连续的区段的起始页之间通过一个链表来互相连接。可见，free_area的组织方式与采用的页面分配算法息息相关，比如说，倘若采用best fit算法，就应该按空闲区段从小到大的顺序来组织起始页链表，worst fit算法则恰好相反，而倘若采用first fit分配算法，就应该按照起始页的地址顺序，由小到大组织。pmm_manager中的init_memmap, alloc_pages, free_pages实现的关键，都在于维护这种有序关系。

对于我们要实现的first fit算法而言，在调用init_memmap将新的空闲页加入到free_area当中时，就需要遍历当前的起始页链表，从而找到一个合适的位置插入新的空闲页，其实现如下：

/* search for a proper positon in free_list to place new memory block*/
static void 
insert2free_list(list_entry_t *elem){
    list_entry_t *le = &free_list;
    while((le = list_next(le)) != &free_list){
        if(elem < le){
            list_add_before(le, elem);
            break;
        }
    }
    if(le == &free_list) list_add_before(le, elem);
}

static void
default_init_memmap(struct Page *base, size_t n) {
    assert(n > 0);
    struct Page *p = base;
    for (; p != base + n; p ++) {
        assert(PageReserved(p));
        p->flags = p->property = 0;
        set_page_ref(p, 0);
    }
    base->property = n;
    SetPageProperty(base);
    nr_free += n;
    cprintf("current number of free pages: %d\n", nr_free);
    insert2free_list(&(base->page_link));
}

这里，我首先写了一个insert2free_list函数，来找到first fit算法中合适的插入位置，并且将新的空闲页插入其中。在default_init_memmap中，首先进行一些权限的设置，比如将当前页面设置为[可用的]，而非继续被操作系统[保留的]等，然后就调用insert2free_list将新的页面插入到合适的位置。对于参考答案给出的这个代码，是直接将新的页面插入到页表的末端，可能是老师清楚INT 15的中断调用返回的e820map地址顺序是有序的，但是我并不清楚这个事实，所以我觉得我的实现也许还更严谨？

first fit算法的实现

在建立好free_area来管理所有的空闲内存区块后，就可以着手实现first fit连续物理内存分配算法了。主要的工作其实就是实现两个函数，页面分配算法(alloc_pages)以及页面回收算法(free_pages)。

对于页面分配算法，应该按照空闲内存区块的起始地址从小到大的顺序，遍历这些内存区块，直到发现一个区块大于要分配的内存空间，则将这个区块切割，将要求的内存空间分配出去后，把剩下的空闲内存继续保存到free_area中，这其中涉及到一些标志位以及相关状态变量的修改。具体的代码如下：

static struct Page *
default_alloc_pages(size_t n) {
    assert(n > 0);
    if (n > nr_free) {
        return NULL;
    }
    struct Page *page = NULL, *p;
    list_entry_t *le = &free_list;
    while ((le = list_next(le)) != &free_list){
        p = le2page(le, page_link);
        if (p->property >= n) {
            page = p;
            break;
        }
    }
    if (page != NULL) {
        list_del(&(page->page_link));
        if (page->property > n) {
            p = page + n;
            p->property = page->property - n;
            insert2free_list(&(p->page_link));
        }
        nr_free -= n;
        ClearPageProperty(page);
    }
    return page;
}

我这里的这个实现其实是还可以改进的。可以看到，我在将剩下的空闲内存再次加入到free_area中时，调用了前面提到的insert2free_list函数，这个函数会遍历所有的空闲区块，直到发现插入的合适位置，其最坏情况与平均情况的时间复杂度都是O(n)。实际上，直接将该剩下的空闲区块插入到page后面不就可以了吗？为此只需要首先添加该剩余的空闲区块，之后再删除掉free_area中的page->page_link就可以了，实际复杂度仅为O(1)。实际上，老师给出的参考答案就是这样实现的。

对于页面回收算法，则要相对复杂。因为不仅需要将被回收的页面插入到free_area中的合适位置，还需要考虑该新加入的页面是否可以和其前后相邻的页面进行合并，从而组织成一个更大的空闲区块。我的回收算法就是这样实现的，先找到合适的位置插入新的页面，再分别检测是否可以与前后相邻的页面合并。具体的代码如下：

static void
default_free_pages(struct Page *base, size_t n) {
    assert(n > 0);
    struct Page *p = base, *front;
    for (; p != base + n; p ++) {
        assert(!PageReserved(p) && !PageProperty(p));
        p->flags = 0;
        set_page_ref(p, 0);
    }
    base->property = n;
    SetPageProperty(base);
    list_entry_t *le = &free_list;
    while ((le = list_next(le)) != &free_list) {
        p = le2page(le, page_link);
        if(base < p){
            list_add_before(&(p->page_link), &(base->page_link));
            if(base + base->property == p){
                base->property += p->property;
                ClearPageProperty(p);
                list_del(&(p->page_link));
            }
            if(list_prev(&(base->page_link)) != &free_list){
                front = le2page(list_prev(&(base->page_link)), page_link);
                if(front + front->property == base){
                    front->property += base->property;
                    ClearPageProperty(base);
                    list_del(&(base->page_link));
                }
            }
            break;
        }
    }
    if(le == &free_list){
        list_add_before(&free_list, &(base->page_link));
        if(list_prev(&(base->page_link)) != &free_list){
            front = le2page(list_prev(&(base->page_link)), page_link);
            if(front + front->property == base){
                front->property += base->property;
                ClearPageProperty(base);
                list_del(&(base->page_link));
            }
        }
    }
    nr_free += n;
}

在主循环里面，我是试图查找新加入的页面的后继页面，将新的页面插入到其后继页面之前，再进行合并的检测。但如果新加入页面是被插入到free_area链表的最后，则没有这样的后继页面，同时也只有可能与它的前驱进行合并了，while循环之后就是对于这种特殊情况的处理。相对于参考答案的代码，我的版本应该是更好的，因为参考答案用了两次循环，存在大量的冗余操作，当然老师的注释也写了应该对这个代码进行优化。但是不管怎么样，我的这个代码还是存在太多冗余了，存在改进的余地（但是我懒得改了），以下简单说明以下：首先定位待插入页面的前驱front，如果le2page(front) != free_list && front + front->property == base，则更新front的信息，并且令base = front；否则插入base页面。无论哪种情况，以下再以base为基，判断后面的页面是否也可以合并。这样写性能不会更快，但是代码会简练不少。

页表的建立

我们知道，页表的本质其实就是虚拟页与物理页帧之间的地址映射关系。因此，页表的建立其实就是将两者联系起来，填写相应的页表项，从而使得操作系统通过页表可以完成从线性地址到物理地址的转化工作。

为了建立两级页表，我们首先要为页目录表分配一个页的存储空间：

// create boot_pgdir, an initial page directory(Page Directory Table, PDT)
boot_pgdir = boot_alloc_page();

对于每一个线性地址，通过其高十位来索引页目录表，可以得到唯一的页目录表项，从而得到其对应的页表的起始地址；通过其中间十位索引页表，可以得到唯一的页表项，并且进而得到该页表项所对应的物理页帧。可以看出，建立页表的关键，就是要将物理页帧的地址，填入某个线性地址所对应的页表项中，并且设置相应的权限标志位。为此，我们需要首先找到任何一个线性地址所对应的页表项，这个工作被抽象为下面的get_pte函数。

练习2：实现寻找虚拟地址对应的页表项（需要编程）

通过设置页表和对应的页表项，可建立虚拟内存地址和物理内存地址的对应关系。其中的get_pte函数是设置页表项环节中的一个重要步骤。此函数找到一个虚地址对应的二级页表项的内核虚地址，如果此二级页表项不存在，则分配一个包含此项的二级页表。本练习需要补全get_pte函数inkern/mm/pmm.c，实现其功能。请仔细查看和理解get_pte函数中的注释。get_pte函数的调用关系图如下所示：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Wp7uCOnO-1574171371584)(images/get_pte.png)]

请在实验报告中简要说明你的设计实现过程。请回答如下问题：

• 请描述页目录项（Page Director Entry）和页表项（Page Table Entry）中每个组成部分的含义和以及对ucore而言的潜在用处。
• 如果ucore执行过程中访问内存，出现了页访问异常，请问硬件要做哪些事情？

页目录项与页表项的结构

由于一页的大小是4K，因此虚拟地址的页偏移量为12位，其余的20位就是逻辑页号。这里的20位逻辑页号又划分为页目录表的索引和页表的索引，分别是10位。这样可以保证一个页目录表或者页表中恰好有2^10 = 1024个表项，每个表项占四个字节，一个页目录表或者页表也就是4K大小，恰好可以容纳在一页之中。

页目录表与页表的功能是一致的，都是给出某个物理地址。页目录表是给出相应的页表的物理地址，页表则是给出某个物理页帧的起始物理地址。由于一个页表的大小也恰好是一个物理页帧的大小，因此这两个地址都是相对于4K对齐的，只需要20位就可以描述。这样，页表项或者页目录表项的其余12位就可以用来表示一些控制信息，比如访问的权限是否可读或是可执行，以及该页表项是否存在。实际上，页目录项与页表项的结构如下所示：

----------------------------------
|    20bits       | ... |  |  |  |
----------------------------------
 phy page number         U  W  P     (PTE_U  PTE_W   PTE_P)

这里的三个标志位PTE_U, PTE_W, PTE_P分别代表用户态是否可读，该物理内存也是否可写，以及该页表项是否存在。此外还有一些其他标识符，在lab2中没有出现，所以就不一一说明了。这里需要注意一下PTE_P标识位，若该标志位置一，则说明当前的表项是存在的，这意味着当前表项的各个字段都是有意义的，其前20位确实对应了某个物理页帧。这就是说，对应的物理页帧已经建立了与某个线性地址之间的映射关系；而该表项不存在则说明了索引到该表项的线性地址还没有对应到任何的物理页帧，可能等待后续的操作添加这种对应关系，特殊地，如果该表项还是一个页目录表项的话，就意味着该页目录表项还没有对应任何的页表，后续需要分配一页的存储空间来保存新建立的页表。

get_pte函数的实现

get_pte的功能是找到与一个线性地址相对应的页表项，因此get_pte的流程应该是模拟操作系统查询页目录表与页表的过程，即首先用线性地址的高10位索引页目录表，再用中间10位索引页表，如果顺利的话，就可以找到与之对应的页表项，返回其虚拟地址就可以了。但是这里我们还需要考虑特殊的情况，倘若索引页目录表得到的页目录项并非是有效的(PTE_P未设置)，就需要调用前面的物理内存分配的函数，为建立一个新的页表分配一页的空间，然后将页表的物理地址填入页目录项中，后续的操作再查这个新的页表就可以了。get_pte的具体实现如下：

pte_t *
get_pte(pde_t *pgdir, uintptr_t la, bool create) {
    pde_t *pde = pgdir + PDX(la);
    struct Page* p;
    if(!(*pde & PTE_P)){
        if(!create) return NULL;
        //else allocate a new page for page table
        *pde = PADDR(boot_alloc_page());
        *pde = *pde | PTE_P | PTE_U | PTE_W;
        p = pa2page(*pde);
        set_page_ref(p, 1);
        memset(page2kva(p), 0, PGSIZE);
    }
    return ((pte_t*)KADDR(PDE_ADDR(*pde))) + PTX(la);
}

需要注意这里的地址转换，还是有点复杂的，比如说查页目录表得到的是页表的物理地址，为了找到该页表，需要将物理地址转换成虚拟地址。此外这里的create参数，是表示页表不存在的时候，是否需要新建一个页表，只有在create = True时才新建页表。我这个代码的问题是安全性不足，因为即使create = 1，也仍然会出现内存不足，分配不出空间的情况，此时贸然调用boot_alloc_page()，可能会出现内核停止工作的情况。参考答案就比我优雅多了：

    ...
    if (!create || (page = alloc_page()) == NULL) {
        return NULL;
    }
    ...

实现了get_pte函数之后，就可以方便地设置页表项了，这个工作体现在page_insert函数当中。与设置映射关系相反，有时候也需要取消线性地址与物理地址的映射，这时就需要实现page_remove_pte函数。

如果ucore执行过程中访问内存，出现了页访问异常，请问硬件要做哪些事情？

不会…需要后面更强的我来完成。不知道这里的页访问异常是怎么出现的，难道是访问了未映射到物理地址的虚拟地址？我不清楚这种情况为什么会出现啊。

练习3：释放某虚地址所在的页并取消对应二级页表项的映射（需要编程）

当释放一个包含某虚地址的物理内存页时，需要让对应此物理内存页的管理数据结构Page做相关的清除处理，使得此物理内存页成为空闲；另外还需把表示虚地址与物理地址对应关系的二级页表项清除。请仔细查看和理解page_remove_pte函数中的注释。为此，需要补全在kern/mm/pmm.c中的page_remove_pte函数。page_remove_pte函数的调用关系图如下所示：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-NMfUrnp1-1574171371585)(images/page_remove_pte.png)]

请在实验报告中简要说明你的设计实现过程。请回答如下问题：

• 数据结构Page的全局变量（其实是一个数组）的每一项与页表中的页目录项和页表项有无对应关系？如果有，其对应关系是什么？
• 如果希望虚拟地址与物理地址相等，则需要如何修改lab2，完成此事？ 鼓励通过编程来具体完成这个问题

page_remove_pte函数的实现

page_remove_pte的功能其实恰好与page_insert相反啊，因为它要清除这种线性地址到物理地址的映射关系，按照前面的讨论，其实就是将PTE_P标志位清零，为此我们首先需要调用get_pte函数来获得与当前线性地址对应的页表项。此外，对于物理页帧，也需要修改某些属性，例如Page.ref属性是表示有多少个虚拟地址映射到当前的物理页帧，因此取消一个这样的对应关系后，应该使Page.ref--，如果Page.ref == 0，则表示已经没有任何虚拟页映射到当前物理页，因此就可以将物理页帧释放掉，以供后续的分配使用。

需要注意的是，取消了线性地址到物理地址的映射关系后，还需要invalidate TLB，即更新快表。否则如果快表里面仍然存储当前线性地址到物理地址无效的映射，在后续的内存访问中可能会访问到无效错误的区段，这是非常严重的问题。我实际实现的代码如下：

//page_remove_pte - free a Page sturct which is related to linear address la
//                - and clean(invalidate) pte which is related to linear address la
//note: PT is changed, so the TLB needs to be invalidated
static inline void
page_remove_pte(pde_t *pgdir, uintptr_t la, pte_t *ptep) {
    //assert(ptep == get_pte(la));
    if(ptep != NULL && (*ptep & PTE_P)){
        struct Page* page = pte2page(*ptep);
        page_ref_dec(page);
        if(page->ref == 0){
            free_page(page);
            *ptep = *ptep & ~PTE_P;
            tlb_invalidate(pgdir, la);
        }
    }
}

很容易可以看出，我这里的实现是错误的，最后两条语句应该放在if判断语句之外，即

...
if(page->ref == 0){
    free_page(page);
}
*ptep = *ptep & ~PTE_P;
tlb_invalidate(pgdir, la);
...

因为只要的确取消了la到ptep的映射关系，无论page->ref是否减到了零，都应该使当前页表项无效化，并且刷新快表TLB。然而最神奇的是，我这个错误的代码还通过了测试…

建立页表

实现了get_pte函数之后，就可以方便地建立页表了。这里ucore内核是建立了一个覆盖全部物理地址空间的页表，将从KERNBASE到KERNBASE + KMEMSIZE的虚拟地址空间，一一映射到从0x00000000开始的物理地址空间，该页表的映射关系满足

linear addr - 0xC0000000 = phy addr

这个过程可以用get_pte函数快捷地实现，简单说来就是对于这里的虚拟地址va，调用get_pte(pg_dir, va, create = 1)得到其对应的页表项，并且用与之对应的物理地址va - 0xC0000000来填写页表项的高20位，并且设置相应的标志位。具体的代码在boot_map_segment中实现：

//boot_map_segment - setup&enable the paging mechanism
// parameters
//  la:   linear address of this memory need to map (after x86 segment map)
//  size: memory size
//  pa:   physical address of this memory
//  perm: permission of this memory  
static void
boot_map_segment(pde_t *pgdir, uintptr_t la, size_t size, uintptr_t pa, uint32_t perm) {
    assert(PGOFF(la) == PGOFF(pa));
    size_t n = ROUNDUP(size + PGOFF(la), PGSIZE) / PGSIZE;
    la = ROUNDDOWN(la, PGSIZE);
    pa = ROUNDDOWN(pa, PGSIZE);
    for (; n > 0; n --, la += PGSIZE, pa += PGSIZE) {
        pte_t *ptep = get_pte(pgdir, la, 1);
        assert(ptep != NULL);
        *ptep = pa | PTE_P | perm;
    }
}

这样，只需要调用boot_map_segment(boot_pgdir, KERNBASE, KMEMSIZE, 0, PTE_W)就可以实现上述的全局页表。

但是需要注意的是，此时还不能使能页机制，因为此时的段机制的映射关系还是

virt addr - 0xC0000000 = linear addr

如果此时使能页机制，虚拟地址，线性地址与物理地址之间的关系将会是

virt addr - 0xC0000000 = linear addr = phy addr + 0xC0000000

此时又会出现虚拟地址不能正确映射到物理地址的情况。为了解决这个问题，我们只需要在使能页机制之后立即修改段机制为对等映射，这样就可以得到最终的地址映射关系：

virt addr = linear addr = phy addr + 0xC0000000

在修改段机制之前，我们只需要保证操作系统的代码可以正常运行，其实只需让index为0的页目录项的内容等于以索引值为KERNBASE>>22的目录表项的内容即可。目前内核大小不超过4M（实际上是3M，因为内核从0x000100000开始编址），这样就只需要让页表在0 ~ 4MB的线性地址与KERNBASE ~ KERNBASE + 4MB的线性地址获得相同的映射即可，都映射到0 ~ 4MB的物理地址空间，具体实现在pmm.c中pmm_init函数的语句：

boot_pgdir[0] = boot_pgdir[PDX(KERNBASE)];

这样，在更新了段表(gdt_init())以后，再将设置的临时映射关系解除(boot_pgdir[0] = 0)，就得到我们期望的物理地址，线性地址以及虚拟地址的映射关系了。

自映射机制

自映射机制的思想是为了使操作系统（和用户程序）方便快捷地查看当前的页目录表项以及页表项。为了查看页目录表和页表的全部内容，一种方法是从页目录表的起始地址，逐个遍历其中的表项，我是觉得这种方法挺好的，但是老师觉得不太行…

为了方便地查看页表中的所有页表项，可以人为设定一个虚拟地址VPT，其低20位为零，并且在页目录表中添加一项，将该虚拟地址对应的页表映射为页目录表本身。即

boot_pgdir[PDX(VPT)] = PADDR(boot_pgdir) | PTE_W | PTE_P;

这样，整个页目录表成为了该虚拟地址的页表，而全局的页表，则成为了该虚拟地址对应的页帧。这样，通过访问VPT[n]，就可以访问全局页表中的第n个页表项了。

同理，还可以设置vpd = PGADDR(PDX(VPT), PDX(VPT), 0)，这样整个页目录表就成为了虚拟地址vpd对应的物理页帧，通过访问vpd[n]就可以访问第n个页目录表项。

同样的机制也可以用于用户程序当中。比如某个用户程序希望知道自己当前页表的结构，但是页表是由操作系统维护的，此时设置用户虚拟地址UVPT，并且将它对应的页表映射到用户程序的页目录表，即

user_pgdir[PDX(UVPT)] = user_pgdir | PTE_P | PTE_U;    //no PTE_W

用户程序就可以通过虚拟地址UVPT访问到它自己的页表项了。需要注意的是，这里不能给写权限。