MIT6828-Lab2-内存管理

计算机社会学基本公理：第一，内存是进程的第一需要；第二，进程不断增长和扩张，但计算机中的内存总量保持不变。

介绍

内存管理的组成

内存管理可以分为物理内存分配和虚拟内存映射。

内核的物理内存分配器

在内存管理中，我们需要为内核提供物理内存分配器，使内核能够分配和释放内存。分配的单元为页，大小一般为4KB。为了实现分配器，我们需要维护一个数据结构记录哪些内存是已经被分配的，哪些是空闲的，多少个进程在使用已经分配的内存。同时，我们还需要一套用于分配和释放的调度策略。

虚拟内存机制

为了将内核和用户软件的虚拟内存地址映射到实际物理地址，我们需要一个虚拟内存映射机制。当指令使用内存时，x86的内存管理单元（MMU）通过一个页表完成映射过程。为了实现JOS，我们需要去调整相应的页表。

开始

首先创建一个分支lab2，然后将我们在lab1中写的代码合并到lab2中，这一部分请参考lab2中的提示，不再赘述。需要注意的是可能会需要手动处理一些合并过程中的冲突。在本次实验中我们需要关注的新文件如下：

inc/memlayout.h         
kern/pmap.c            
kern/pmap.h
kern/kclock.h
kern/kclock.c

memlayout.h描述了虚拟地址空间的布局，你需要通过修改pmap.h实现。memlayout.h和pmap.h定义了PageInfo结构体，根据这个结构体可以查看内存的alloc/free情况。kclock用于操作PC的电池时钟以及RAM，RAM中保存了物理地址的容量及其他相关信息。pmap.c通过读取RAM来确定有多少物理内存可用。

这里重点注意memlayout.h和pmap.h，并复习一下inc/mmu.h

第一部分：物理页管理

操作系统必须跟踪物理内存的使用情况，包括哪些内存被分配了，哪些是空闲的。JOS使用页粒度对内存管理，从而可以使用MMU对已经分配的内存进行保护和映射。

在这一部分，我们需要实现一个物理页分配器，它使用一个链表连接的PageInfo对象对空闲页进行跟踪，每一个PageInfo代表一个物理页。在此基础上，我们会实现一个页表管理器分配物理内存，从而保存页表。（与xv6不同，xv6直接将PageInfo保存在指向的空闲页中）

练习1：一个物理页分配器

在kern/pmap.c中，你需要按顺序实现下列函数：

boot_alloc()
mem_init() //只做到check_page_free_list(1)之前
page_init()
page_alloc()
page_free()

check_page_free_list()和check_page_alloc()将会测试你的物理页分配器。

boot_alloc

lab2中给出的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;
    // 使用First Fit实现
    // 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.
    // Find the address which is the first one larger than end and can divide PGSIZE
    if (!nextfree) {
        extern char end[];
        nextfree = ROUNDUP((char *) end, PGSIZE);   //PGSIZE表示一个页大小为4096bytes
    }
    
    // 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.

    
    nextfree = ROUNDUP((char *) nextfree, PGSIZE);
    return nextfree;
    
}

函数功能

根据注释中的提示，我们可以得知这个函数功能如下：

• 当n > 0时，分配足以容纳nbytes的物理内存页，并返回内核虚拟地址，不需要初始化；如果不够了，系统调用panic打印错误信息。
• 当n == 0时，直接返回下一个空闲页的地址

实现准备

为了实现上面的功能，我们需要思考如下问题：

1. 如何确定nextfree的位置在哪里？
2. 如何确定是否有足够的内存用于分配

首先，我们来回顾一下我们的内存模型：忽略底部的用于BIOS、硬件以及bootloader的部分，内核实际是加载到0x00100000中的，linker会自动为内核镜像分配内存，所以内存的使用是从0x00100000这个地址向上增长的。那么最大内存是多少呢？这取决于硬件中实际内存的容量，在pmap.c中，我们有一个i386_detect_memory()函数，用于检测内存的大小，其中有一个npages全局变量保存了以页为单位的可用内存的数目。实际实验中npages为32768

+------------------+  <- 0xFFFFFFFF (4GB)：这个内存根据实际大小会发生变化
|      32-bit      |
|  memory mapped   |
|     devices      |
|                  |
/\/\/\/\/\/\/\/\/\/\

/\/\/\/\/\/\/\/\/\/\
|                  |
|      Unused      |
|                  |
+------------------+  <- depends on amount of RAM
|                  |
|                  |
| Extended Memory  |
|                  |
|                  |
+------------------+  <- 0x00100000 (1MB)

下面解决第一个问题，如何确定下一个空闲页的位置在哪里，这里我们先来回顾一下一个程序的虚拟内存模型：

我们需要注意的是：千万不要把操作系统想的太复杂，它就是一个比较特殊的可执行文件，这个可执行文件一定是符合一般的可执行文件的内存分布的，所以肯定也符合上面的虚拟内存模型。我们可以看到，bss段之后就是堆段，也就是我们需要分配的内存所在的位置，而栈段是从内存高地址开始的，并向下增长，所以最后堆段会和栈段发生碰撞，产生stackoverflow等问题，不过这里不是我们需要关注的，我们只需要知道bss段后是heap段即可。所以程序中nextfree第一次被创建并赋值时，其位置在bss段之后。而我们的程序也体现了这一点：

// 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.
// Find the address which is the first one larger than end and can divide PGSIZE
if (!nextfree) {
    extern char end[];
    nextfree = ROUNDUP((char *) end, PGSIZE);   //PGSIZE表示一个页大小为4096bytes
}

我们注意到nextfree是一个static类型的变量，其生命周期是整个内核的生命周期，而end为bss段的结束，这个是由linker决定的，寻找bss段后第一个nextfree的语句为

nextfree = ROUNDUP((char *) end, PGSIZE);

ROUNDUP根据注释的提示，可以知道是对齐的作用，所以实际上bss段和堆段之间有一小片（小于一个PGSIZE大小）的内存碎片被浪费掉了。

当我们再次进入boot_alloc，此时nextfree已经不再为空，那么该如何寻找呢？我们现在有需要分配的字节数n和当前地址nextfree，那么下一个空闲的地址的计算如下：

$$\textrm{nextfree} = \textrm{nextfree}+\textrm{size}$$

具体计算原理详见：关于内存计算的讲解。所以我们计算nextfree的代码如下：

nextfree = ROUNDUP((char*)(nextfree + n), PGSIZE);

可以看到，如果nextfree+n不能整除PGSIZE，就会产生内存碎片。

下面我们解决第二个问题，如何确定是否有足够的内存空间。我们现在有npages代表最大可用内存页数，那么npages*PGSIZE就是最大内存容量。而我们现在知道nextfree，由于内存是向上增长的，所以我们只需要用nextfree减去内存起始地址，即可判断是否超过最大可用内存。那么现在的问题是，如何找到起始内存地址。根据i386_detect_memory()我们知道，npages代表的是总内存大小，即从地址0x0开始，到最大的物理内存地址。所以起始地址即为0x0。另外nextfree是虚拟地址，我们还需要转换为物理地址。现在我们可以写出计算是否超过内存容量的代码：

if(PADDR(nextfree) > npages*PGSIZE)  // 分配后的内存地址超过了总内存地址
        panic("boot_alloc: Run out of memory! Total memory: %u, needed memory: %u", npages * PGSIZE, PADDR(nextfree));

具体实现

boot_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.
    // Find the address which is the first one larger than end and can divide PGSIZE
    if (!nextfree) {
        extern char end[];   // end 是指向内核bss段的末尾的指针
        nextfree = ROUNDUP((char *) end, PGSIZE);   //PGSIZE表示一个页大小为4096bytes
    }
    
    // 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.
    // 情况1: n为0
    if(n == 0) return (void *)nextfree;
    
    // 计算下一个内存地址位置
    result = nextfree;
    nextfree = ROUNDUP((char *) (n + nextfree), PGSIZE); //对齐操作
    
    // 情况2.1：超过内存大小
    if(PADDR(nextfree) > npages*PGSIZE)
        panic("boot_alloc: Run out of memory! Total memory: %u, needed memory: %u", npages * PGSIZE, PADDR(nextfree));
    
    // 情况2.2：正常分配
    return (void *)result;

}

mem_init()的第一部分

lab2中给出的mem_init（）如下：

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 (Page Dictionary) 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 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:
    // 第一件事情，分配能够容纳npages的struct PageInfo的空间，然后保存在pages中，内核利用
    // 这个pages跟踪每一个物理页
    
    //////////////////////////////////////////////////////////////////////
    // 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 boot_map_region
    // or page_insert
    page_init();

    check_page_free_list(1);

函数功能

mem_init()第一部分功能如下：

1. 检测物理内存大小
2. 创建一个用于保存页表的页
3. 分配能容纳npages * struct PageInfo的空间
4. 将分配的PageInfo根据内存实际使用情况进行初始化

其中需要我们完成的是第三部分

具体实现

首先我们计算所需的空间大小，为npages * sizeof(struct PageInfo);，然后利用boot_alloc函数分配空间，最后memset初始化，代码比较简单，如下所示：

// 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:
n = npages * sizeof(struct PageInfo);
pages = (struct PageInfo*) boot_alloc(n);
memset(pages, 0, n);

page_init()：形成物理内存链表

在分配好了物理内存页表后，我们需要根据内存的实际情况对这些页表进行初始化，标识出空闲的内存，该函数如下所示：

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?
    //
    // Change the code to reflect this.
    // NB: DO NOT actually touch the physical memory corresponding to
    // free pages! 不要使用空闲的物理内存
    size_t i;
    for (i = 0; i < npages; i++) {     // 此处注意i的范围是[0, npages-1]，所以要使用<号，
                                       // 一开始我写成了<=，导致内存越界，直观表现是系统一直重启
        pages[i].pp_ref = 0;
        pages[i].pp_link = page_free_list;
        page_free_list = &pages[i];
    }
}

函数功能

上面的函数将所有的物理内存页都初始化为了空闲，但实际上这是不对的，我们需要根据内存的实际使用情况，将其进行初始化，规则如下：

1. 将物理页0标注为正在使用
2. 将物理页1-npages_basemem标注为空闲
3. 物理页IOPHYSMEM/PGSIZE - EXTPHYSMEM/PGSIZE标注为正在使用
4. EXTPHYSMEM/PGSIZE之后有一些内存是空闲的，一些是正在使用的

其中，所以我们最后得到的内存页链表如下所示：

我们通过page_free_list，就可以以倒序的形式，遍历所有的空闲内存页。根据内存使用规则，我们可以得到page_init具体实现。

实现准备

为了实现上面的功能，我们需要思考如下问题：

1. 非空闲的内存如何处理？
2. 在extened memory中，从何处开始是空闲内存？

首先回答第一个问题，非空闲的内存页我们就不将其连接到链表当中了，这些内存有其特定作用，一般不用来作为free mem，所以我们采用一种冷处理的方式。

第二个问题，在扩展内存中，哪些是内核使用的内存？空闲内存是何处开始的？考虑我们写过的函数boot_alloc，当输入为0时，返回下一个空闲页的地址，所以我们可以利用这个函数找到空闲页地址，假设为$p_f$，那么$[p_f/\textrm{PGSIZE},\textrm{npages}]$这一段内存我们都需要进行初始化。这里还有一个问题，boot_alloc返回的是一个指针值，即对应的逻辑地址，我们还需要将这个逻辑地址转换为实际的物理地址。从mem_init中有一个宏函数PADDR，专门完成这个工作，至此，我们的两个任务已经完成。

具体实现

page_free_list实际是一个链表，所以page_init实际就是一个链表初始化的过程

// 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. 在这个函数完成后，不要在使用boot_alloc,
// 只是用下方提供的分配器对物理内存进行分配
// pages和物理内存是一一对应的
void
page_init(void)
{
    // Change the code to reflect this.
    // NB: DO NOT actually touch the physical memory corresponding to
    // free pages! 不要使用空闲的物理内存
    
    //  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.
    size_t i;
    for (i = 1; i < npages_basemem; ++i) {
        pages[i].pp_ref = 0;
        pages[i].pp_link = page_free_list;
        page_free_list = &pages[i];
    }
    
    //  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?
    //
    char *pf = boot_alloc(0);
    i = PADDR(pf)/PGSIZE;
    for(i; i < npages; ++i){
        pages[i].pp_ref = 0;
        pages[i].pp_link = page_free_list;
        page_free_list = &pages[i];
    }
}

page_alloc：分配一个物理页

在对所有的可用pages进行初始化后，下一步是写一个分配和释放器，由于page_free_list是一个链表，所以我们的分配和释放器也要有链表的行为。我们先来完成page_alloc，其定义如下：

// Allocates a physical page.  If (alloc_flags & ALLOC_ZERO), fills the entire
// returned physical page with '\0' bytes.  Does NOT increment the reference
// count of the page - the caller must do these if necessary (either explicitly
// or via page_insert).
//
// Be sure to set the pp_link field of the allocated page to NULL so
// page_free can check for double-free bugs.
//
// Returns NULL if out of free memory.
//
// Hint: use page2kva and memset
struct PageInfo *
page_alloc(int alloc_flags)
{
    return NULL;
}

函数功能

page_alloc的函数功能为分配一个物理页，并返回这个物理页对应PageInfo的地址。在page_alloc中我们将所有的空闲内存都用PageInfo一一对应，并构造了一个page_free_list，所以我们的分配操作是针对这个链表进行的。我们先具体定义page_alloc的流程：

• 如果内存耗尽，返回NULL
• 如果(alloc_flags & ALLOC_ZERO)，将PageInfo对应的物理页清空
• 返回的指针中的pp_link应当设置为NULL
• 不要修改pp_ref，这个工作交给调用者完成
• 调整page_free_list的值

针对上面几个功能我们逐一完成。首先第三个和第四个功能很好实现，我们先解决第一个，如何判断内存耗尽？既然page_free_list是一个链表，那么当链表为空时，代表所有的物理页均已分配，所以判断内存耗尽的代码为page_free_list == NULL。

第二个问题，如何将PageInfo对应的物理页清空？为了实现该功能，我们要利用到memset函数，问题是如何找到PageInfo对应的物理页的地址。根据提示，可以使用page2kva实现，清空的大小为一个物理页的大小，第二个问题也解决了。

最后一个问题，如何调整page_free_list的值，这个过程是一个链表删除头节点的过程，先用一个节点保存头节点，然后head指向head->next即可。

具体实现

根据我们总结的函数功能，可以得到page_alloc实现如下：

struct PageInfo *
page_alloc(int alloc_flags)
{
    if(page_free_list == NULL){
        cprintf("page_alloc: out of memory!\n");
        return (struct PageInfo*) NULL;
    }
    struct PageInfo* pp = page_free_list;
    page_free_list = pp->pp_link;
    if(alloc_flags & ALLOC_ZERO){
        memset(page2kva(pp), '\0', PGSIZE);  //将对应的物理页清空
    }
    pp->pp_link = NULL;
    return pp;
}

page_free：释放物理页

一旦一个物理页用完，我们应当重新将其添加至page_free_list中，所以page_free的过程本质上是一个在链表头插入节点的过程。物理页用完的标准是pp_ref == 0 && pp_link == NULL。如果pp_ref不为0，代表还有对象在使用这块内存，就不应该释放；如果pp_link != NULL，说明这个物理页后面还有其他页，一旦将这个页释放，后面的页也会连带着找不到，会造成内存泄漏。所以也不能释放。page_free比较简单，这里直接给出实现

// Return a page to the free list.
// (This function should only be called when pp->pp_ref reaches 0.)
//
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 ) {
        panic("page_free: page is still in use!\n");
    }
    if(pp->pp_link != NULL){
        panic("page_free: Try to free a page which has link to other page, may cause memory leak");
    }
    pp->pp_link = page_free_list;
    page_free_list = pp;
}

至此，我们完成了Part1的全部内容，运行make grade可以拿到10分。

第二部分：虚拟地址

虚拟、线性以及物理地址

这一部分的实验文档阅读总结详见关于地址的讲解

练习3：使用QEMU查看物理内存

GDB只能访问虚拟内存，如果我们想要访问物理内存，可以使用QEMU的monitor commands。进入和退出monitor的方法为在QEMU界面为在运行QEMU的shell中按下ctrl-a c。使用xp命令可以查看对应的物理内存。

(qemu) xp 0x0010000c
000000000010000c: 0x7205c766

使用gdb查看对应的虚拟内存

(gdb) x/x 0xf010000c
0xf010000c <entry>:    0x7205c766

课程提供的QEMU有一个info pg命令，可以打印当前页表的信息。但是我用的是原生的QEMU，没有此命令，有一个info mem命令能够查看当前物理地址到虚拟地址的映射情况以及读写权限

(qemu) info mem
0000000000000000-0000000000400000 0000000000400000 -r-   # 大小为0000000000400000
00000000f0000000-00000000f0400000 0000000000400000 -rw

地址类型

由于JOS经常需要将地址视为整数进行操作，为了区分物理和虚拟地址，JOS提供了两种类型，分别是uintptr_t和physaddr_t，实际都是uint32_t。JOS能够将uintptr_t转换为指针类型然后解引用，但是不能解引用一个物理地址，因为保护模式下只能访问虚拟地址。如果试图解引用一个物理地址，MMU也会把这个物理地址作为虚拟地址来处理。

在有些情况下，如果只知道物理地址，例如想要添加一个页表映射，此时需要分配一块物理内存存放页字典。但是kernel不能进行虚拟地址的转换，因此无法直接加载物理地址。JOS之所以将物理地址0x00000000映射至0xf0000000，就是为了解决内核只知道物理地址的情况。为了将物理地址转换为虚拟地址，内核需要将物理地址加上0xf0000000，然后对虚拟地址进行操作。JOS提供了函数KADDR(pa)实现转换过程。同样的，PADDR(va)实现了物理地址到虚拟地址的转换。

引用计数

在接下来的实验中，我们会遇到一个物理地址同时映射到多个虚拟地址的情况（或者说是一个物理地址处于多个不同环境的地址空间）。此时我们需要一个计数器记录一个物理页的被使用情况。这个计数器是PageInfo结构体下的pp_ref。当pp_ref为0时，这个内存可以释放。一般情况下，pp_ref应当等于低于UTOP的物理页出现在页表中的次数（高于UTOP的物理内存在boot期间被kernel设置，并且永不释放，所以不需要对其计数）。注意，page_alloc并不会修改引用计数，该函数返回的页引用总是0。

页表管理

现在写一些关于页表管理的函数：插入和移出线性地址到物理地址的映射，同时在需要的情况下创建页表页。

练习4

完成如下函数的代码，check_page()将会检查函数的正确性：

pgdir_walk()：页目录中查找
boot_map_region()：启动阶段建立映射
page_lookup()：查找页
page_remove()：移出页
page_insert()：插入页

pgdir_walk()

函数原型

函数功能

根据虚拟地址找到对应的pte的指针，用图来描述就是下面这张

具体实现

pte_t *
pgdir_walk(pde_t *pgdir, const void *va, int create)
{
    // Fill this function in
    pde_t *pde = &pgdir[PDX(va)];
    pte_t *pgtable = NULL;

    if( !(*pde & PTE_P) ){
        if( !create ) return NULL;

        struct PageInfo *pp = page_alloc(ALLOC_ZERO);
        if(pp == NULL) return NULL;

        ++pp->pp_ref;
        *pde = page2pa(pp) | PTE_P | PTE_W | PTE_U;
    }
    pgtable = (pte_t*)P2V(PTE_ADDR(*pde));   //物理地址 -> 虚拟地址
    return &pgtable[PTX(va)];
}

boot_map_region()

函数原型

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

函数功能

这个函数的功能是将虚拟地址[va, va+size)映射至物理地址[pa, pa+size)，pte的权限设置为perm|PTE_P。本质上是多叉树的范围赋值。

函数实现

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 i = 0;
    for(; i < (size>>PGSHIFT); ++i){
        pte_t *pte = pgdir_walk(pgdir, (void *)va, 1);
        
        if(pte == NULL) panic("boot_map_region: allocation failure");
        
        *pte = pa | perm | PTE_P;
        va += PGSIZE;
        pa += PGSIZE;
    }
}

page_lookup()

函数原型

//
// 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
    return NULL;
}

函数功能

返回va对应的物理页

函数实现

struct PageInfo *
page_lookup(pde_t *pgdir, void *va, pte_t **pte_store)
{
    pte_t *pte = pgdir_walk(pgdir, (void *)va, 0);    
    if(pte == NULL) return NULL;
    if(pte_store != NULL) *pte_store = pte;
    struct PageInfo* pp = pa2page(PTE_ADDR(*pte));
    return pp;
}

修改

上面的函数有两个问题：

• 仅判断pte为空是不行的，还要判断*pte是否为0
• 要判断pte是否在合适的范围之内，即PPN(*pte) <= npage

struct PageInfo *
page_lookup(pde_t *pgdir, void *va, pte_t **pte_store)
{
    pte_t *pte = pgdir_walk(pgdir, (void *)va, 0);    
    if(pte == NULL || *pte == 0) return NULL;
    if(PPN(*pte) > npage) return NULL;
    else{
        if(pte_store != NULL) *pte_store = pte;
    	return pa2page(PTE_ADDR(*pte));
    }
}

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
}

函数功能

解除物理页和虚拟地址的映射关系

函数实现

void
page_remove(pde_t *pgdir, void *va){
    pte_t *pte = NULL;
    struct PageInfo *pp = page_lookup(pgdir, va, &pte);
    if(pp == NULL) return;
    page_decref(pp);
    *pte = 0;
    tlb_invalidate(pgdir, va);
    return;
}

page_insert()

函数原型

//
// 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
    return 0;
}

函数功能

将物理页pp映射至虚拟地址va，实际上是在多叉树中插入

函数实现

int
page_insert(pde_t *pgdir, struct PageInfo *pp, void *va, int perm)
{
    // Fill this function in
    pte_t *pte = pgdir_walk(pgdir, va, 1);
    if(pte == NULL) return -E_NO_MEM;
    pp->pp_ref++;   // 这一句需要特别注意其位置
    if(*pte & PTE_P) page_remove(pgdir, va);
    *pte = page2pa(pp) | prem | PTE_P;
    return 0;
}

细节：关于边界条件的处理

当同一个pp被重新插入至相同pgdir的相同pte，会发生什么事情？按照上面的代码，首先，pp会被remove，当被remove之后，pp会被回收，而下面的代码又回去利用被回收的pp，因此会造成访问非法内存的问题。正确的方法是将pp->pp_ref++放置在回收语句之前，这样一增一减正好抵消，pp不会被回收掉。而如果是不同的pp，则不受影响。

第三部分：内核地址空间

JOS对内存进行了划分，虚拟地址低部分为用户空间，高部分为内核（约256MB），分界线是ULIM: 0xef800000，给操作系统留下了大约256MB的空间。在ULIM往上，用户没有访问权限。

权限和错误处理

由于内核和用户代码都在地址空间中，因此我们需要权限管理，使用户只能访问自己的地址空间。首先，我们先进行一个划分：

• 高于ULIM：用户无权访问
• [UTOP, ULIM)：用户和内核只能读，这一段用于保存向用户开放的内核只读数据
• 低于UTOP：用户可用空间

内核地址空间初始化

练习5：完成mem_init()中check_page()之前的代码

在这个练习中，我们需要建立内核代码中相关的物理地址和虚拟地址之间的映射，建立过程使用上一节实现的boot_map_region函数即可。映射过程已经由注释给出了提示，相关代码如下：

//////////////////////////////////////////////////////////////////////
// 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, PTSIZE, PADDR(pages), PTE_U);

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

//////////////////////////////////////////////////////////////////////
// Map all of physical memory at KERNBASE.
// Ie.  the VA range [KERNBASE, 2^32) should map to
//      the PA range [0, 2^32 - KERNBASE)   //这里需要注意一下 2^32 相当于1<<32，已经超过了32位系统，结果是0
// 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, -KERNBASE, 0, PTE_W);

上述三行分别完成了页表、内核栈和内核的映射，可以看到低物理地址的内核被映射至了高虚拟地址上。需要注意的是，在建立内核栈时，创建了一段未映射的缓冲区，大小是PTSIZE-KSTKSIZE，内核栈如果访问了这段区域，会导致错误。完成之后本次实验的基础部分已经完成，make grade命令会显示全部通过。

问题

整理内存映射表

我们已经在内核中部分建立起虚拟地址到物理地址的映射，现在，根据已经建立的映射关系尽可能填写下面的表格

Entry	Base Virtual Address	Points to (logically):
1023	?	Page table for top 4MB of phys memory
1022	?	?
.	0xf0000000(KERNBASE)
958	0xef800000(ULIM)	limit between user and kernel
957		?
956	0xef000000(UPAGES)	Read Only pages
2	0x00800000	?
1	0x00400000	?
0	0x00000000	[see next question]

内存保护机制

Q：我们将内核和用户进程放在同一个地址空间中，为何用户进程无法读写内核内存。为何用户无权访问

A：因为我们对虚拟内存也进行了划分，按照ULIM为分界线，向上为内核区域，用户无权限访问。这一机制是靠Current Privilege Level实现的，cs寄存器的两位描述了当前程序的权限，linux使用了两位，分别是内核态(0)和用户态(3)。

操作系统能支持的最大内存是多少？

这个问题问的有歧义，应该问内核占用的物理地址最大为多少。由于内核虚拟地址范围是[0xF0000000, 0xFFFFFFFF]，所以大小为0x0FFFFFFF，共256MB，操作系统理论上最大为256MB，超了的话32位地址无法映射。

用于管理内存的空间开销是多少？如何降低这个开销？

首先，我们有一个页目录，大小是一个页。

其次，我们使用了一个pages结构体数组，用于对页进行保存，这个数组的大小是npages * sizeof(struct PageInfo)，具体值为32768*8B /PGSIZE=64个页。总共65个页，当然在后续加入用户进程后，维护页表还需要额外的内存空间。

我能想到的降低开销的方法是加大页的空间，例如使用2MB或4MB的页，这样可以降低页表数量，节约一部分开销。

地址切换问题

再次查看kern/entry.S 和kern/entrypgdir.c两个文件，当我们开启页映射后，EIP仍处于低地址空间。那么什么时候开始EIP位于高地址空间呢？

为了解决这个问题，我们开启gdb对内核启动的初始阶段进行调试，设置断点br *0x0010000c，然后跳转到entry，这一段的汇编如下：

0x100015        mov    $0x118000,%eax         # 加载页目录，entrypgdir 位于0x11800，保存在了cr3寄存器中
0x10001a        mov    %eax,%cr3                                                       
0x10001d        mov    %cr0,%eax              # 开启分页                                           
0x100020        or     $0x80010001,%eax                                                   
0x100025        mov    %eax,%cr0                                                         
0x100028        mov    $0xf010002f,%eax            
0x10002d        jmp    *%eax                  # 跳转至0xf010002f，此时发生了地址切换，eip变成 $0xf0118000         
0x10002f        mov    $0x0,%ebp                                                         
0x100034        mov    $0xf0118000,%esp                                                   
0x100039        call   0x100040                                                            
0x10003e        jmp    0x10003e                                                            
0x100040        push   %ebp                                                               
0x100041        mov    %esp,%ebp                                                         
0x100043        sub    $0xc,%esp                                                          
0x100046        mov    $0xf017cb00,%eax

是什么机制使得我们在开启页映射到跳转至高地址这段区间内，仍然能够执行位于低地址的指令？

为了解决这个问题，我们需要查看CR0寄存器，开启分页后CR0寄存器的值为0x80010001，即

cr0 = 1000, 0000, 0000, 0001, 0000, 0000, 0000, 0001

翻译过来就是，使能页映射；使用CR3寄存器；不禁用cache，不禁用write-through cache；位于保护模式；开启写保护。没什么特别的，然后我们看下kern/entrypgdir.c。在这个文件中 ，我们找到了如下代码：

pde_t entry_pgdir[NPDENTRIES] = {
    // Map VA's [0, 4MB) to PA's [0, 4MB)
    [0]
        = ((uintptr_t)entry_pgtable - KERNBASE) + PTE_P,
    // Map VA's [KERNBASE, KERNBASE+4MB) to PA's [0, 4MB)
    [KERNBASE>>PDXSHIFT]
        = ((uintptr_t)entry_pgtable - KERNBASE) + PTE_P + PTE_W
};

看到这里应该就明白了，实际上我们是进行了一个双重映射，将虚拟地址的[0, 4MB)和[KERNBASE, KERNBASE+4MB)都映射到了物理地址的[0, 4MB)，所以我们能够在开启页映射后，依然在低地址空间执行，但是实际上这里的低地址空间是虚拟地址的低地址空间。VA’[0, 4MB) to PA [0, 4MB)这个映射只使用了这一次，算是做的一点小小的妥协吧。

附录

物理内存布局

在经过实验一和实验二后，我们对于操作系统物理内存的布局已经有了一些基本了解，现在我们总结一下已经确定的物理内存布局图：

绿色的就是几个比较关键部分的内存布局。

内存映射关系

现在我们来总结一下内存映射关系：

一些重要的函数及计算

i386_detect_memory

这个函数负责获取实际的内存大小，里面定义了totalmem、basemem两个变量分别表示总内存及基本内存，在实验中，这些变量的值如下：

totalmem = 131072(KB)      //0x08000000
basemem = 640(KB)

所以总的物理页计算为：

npages = totalmem/(PGSIZE/1024);    // npages = 32768

共有32768个物理页。

check_page_free_list(bool only_low_memory)

这个函数的作用是检查page_free_list所指向的页面都是有效的，进入后首先判断page_free_list是否为空，为空则无效，随后进入下面一段代码

if (only_low_memory) {
    // Move pages with lower addresses first in the free
    // list, since entry_pgdir does not map all pages.
    struct PageInfo *pp1, *pp2;
    struct PageInfo **tp[2] = { &pp1, &pp2 };
    for (pp = page_free_list; pp; pp = pp->pp_link) {
        int pagetype = PDX(page2pa(pp)) >= pdx_limit;
        *tp[pagetype] = pp;
        tp[pagetype] = &pp->pp_link;
    }						//执行该for循环后，pp1指向（0~4M）中地址最大的那个页的PageInfo结构。pp2指向所有页中地址最大的那个PageInfo结构
    *tp[1] = 0;
    *tp[0] = pp2;
    page_free_list = pp1;
}

这段代码比较迷惑，为了解释其功能，我们先要明确PDX以及page2pa的作用，先看page2pa，其函数原型为：

page2pa(struct PageInfo *pp){
    return (pp-pages) << PGSHIFT;  // PGSHIFT = log2(PGSIZE) = 12
}

这个函数的作用是找到pp所对应的PageInfo指向的具体的物理页，由于一个物理页的大小为4096，所以由页序号转到物理地址的计算公式为$(page1 - start_page)\times PGSIZE=(page1 - start_page)<<PGSHIFT$。

PDX的作用是获得线性地址的一部分，这里不展开说了。

调试过程

boot_alloc 调试过程

使用GDB进入boot_alloc后，得到nextfree的起始地址为0xf0115000，根据内存大小，可以知道内存最大物理地址为0x08000000，所以总可用空间为0x7EEB000。

TODO

参考文献

---

1. 1.xv6 book ↩
2. 2.Lab2 ↩
3. 3.内存计算问题 ↩