从ucore来总结操作系统(2)----物理内存、虚拟内存、转换

物理内存、虚拟内存、转换

这篇是lab2的内容，主要就是实操一下页表和段页式的虚拟内存管理机制。

0X00 环境准备

首先，lab2是基于lab1的，所以需要把lab1的内容合并到lab2中，这里就不赘述了。

在正式开始编程之前，还是有必要来了解下ucore中已有的代码和机制。

本lab中，我们需要修改defalult_pmm.c中的default_init,default_init_memmap,default_alloc_pages, default_free_pages这些函数来完成相应的功能。

当ucore被启动之后，最重要的事情就是知道还有多少内存可用，一般来说，获取内存大小的方法由BIOS中断调用和直接探测两种。BIOS中断调用方法是一般只能在实模式下完成，而直接探测方法必须在保护模式下完成。ucore是通过BIOS中断调用来帮助完成的，由于BIOS中断调用必须在实模式下进行，所以在bootloader进入保护模式前完成这部分工作相对比较合适。通过BIOS中断获取内存可调用参数为e820h的INT 15h BIOS中断，BIOS通过系统内存映射地址描述符（Address Range Descriptor）格式来表示系统物理内存布局。

探测功能在bootasm.S中实现，使用INT 15软中断来要求BIOS返回系统内存布局信息，然后把探查出来的信息存放在物理地址0x8000中，程序使用结构体struct e820map作为保存地址范围描述符结构的缓冲区来保存内存布局，e820map定义在kern/mm/memlayout.h：

// some constants for bios interrupt 15h AX = 0xE820
#define E820MAX             20      // number of entries in E820MAP
#define E820_ARM            1       // address range memory
#define E820_ARR            2       // address range reserved

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

完成物理内存页管理初始化工作后，其物理地址的分布空间如下

在获得可用物理内存范围后，系统需要建立相应的数据结构来管理以物理页（按4KB对齐，且大小为4KB的物理内存单元）为最小单位的整个物理内存，以配合后续涉及的分页管理机制。每个物理页可以用一个Page数据结构来表示。Page定义在kern/mm/memlayout.h中：

/* *
 * 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
    // 用两个bit表示两种属性
    // 1. PG_reserved位 此位为1时表示该页是内核保留的，不可分配
    // 2. PG_property位 此位为1时表示可分配，为0表示已分配
    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
};

0X01 实现 first-fit 连续物理内存分配算法

这里的first-fit算法就是从物理内存的起始地址开始，找到第一个满足要求的空闲块，然后分配给进程。这里的要求就是空闲块的大小要大于等于需要分配的大小。空闲链表需要按照地址从低到高的次序排序。实验一要求实验的函数是分配物理内存的。

其实，lab2自带的default_init_memmap、default_alloc_pages、default_free_pages实现了一个类似first fit的算法，只不过直接make qemu会发现报错，我们可以直接在这基础上进行修改。

同时，在libs/list.h已经定义好了双向链表；在kern/mm/memlayout.h中也定义了一个free_area_t的数据结构，包括空闲块双向链表的头和空闲块总数(以页为单位)；kern/mm/pmm.h中定义了一个通用的分配算法的函数列表，用pmm_manager表示，一个pmm_manager就是一个分配算法。其中init函数就是用来初始化free_area变量的, first_fit分配算法可直接重用default_init函数的实现。init_memmap函数需要根据现有的内存情况构建空闲块列表的初始状态。

而这些函数的调用栈如下

kern_init --> pmm_init-->page_init-->init_memmap--> pmm_manager->init_memmap

而kern_init(内核初始化)、pmm_init(内存初始化)、page_init(读取物理内存，并进行分页)都已经实现了，所以我们首先从init_memmap开始看。

init_memmap(在此处其实就是default_init_memmap)需要根据page_init传递的参数，来建立连续内存的空闲块双向链表。链表头是free_area.free_list，链表项是Page数据结构的base->page_link。这样我们就依靠Page数据结构中的成员变量page_link形成了连续内存空闲块列表。

// kern/mm/default_pmm.c

static void default_init_memmap(struct Page *base, size_t n)
{
    assert(n > 0);
    struct Page *p = base;
    for (; p != base + n; p++)
    { 
        // 在查找可用内存并分配struct Page数组时
        // 就已经将将全部Page设置为reserved(page_init里)
        // 这里确保之前的初始化正确
        assert(PageReserved(p));
        // 将Page标记为可用的:ref设为0,清除reserved,
        // 设置PG_property,并把property设置为0(不是空闲块的第一个物理页)
        p->flags = p->property = 0; 
        set_page_ref(p, 0);
    }
    // 空闲块第一个物理页,property设置为n
    base->property = n; 
    // 设置空闲块的标志位
    SetPageProperty(base);
    // 更新空闲块的总和
    nr_free += n;        
    //'p->page_link'将这个页面链接到'free_list'。 
               
    list_add_after(&free_list, &(base->page_link)); 
}

这是一个物理页初始化函数，其功能是将所有可用的Page的flags设置为PG_property，引用计数设置为0，property设置为0，初始化page_link空闲块的第一个物理块的property设置为该空闲块的大小，将其加入到空闲列表。每次调用会把一个实际的物理块加入到空闲区块中。由于需要保证升序，所以需要使用list_add_after函数(测试下来只有一个块，又因为是双向链表，其实不影响的)。

然后我们来考虑一下页面分配函数，即default_alloc_pages函数，它的作用是在空闲列表中搜索第一个空闲块(块大小>=n)，如果找到则把找到的page返回。

// kern/mm/default_pmm.c

static struct Page *default_alloc_pages(size_t n)
{
    // 确保能够分配
    assert(n > 0);
    if (n > nr_free)
    {
        return NULL;
    }
    // 从空闲链表中找到第一个能够分配的块
    struct Page *page = NULL;
    list_entry_t *le = &free_list;
    // 一直查找下去，直到回到头部
    while ((le = list_next(le)) != &free_list)
    {
        // 通过list_entry_t来获取page
        struct Page *p = le2page(le, page_link);
        // 检查p->property(记录这个块中空闲物理页的数量)是否>=n.
        if (p->property >= n)
        {
            page = p;
            break;
        }
    }
    // 如果找到符合要求的空闲块
    if (page != NULL)
    {

        // 如果空闲块非常大，就要切割
        if (page->property > n)
        {
            struct Page *p = page + n;
            p->property = page->property - n;
            // 然后把剩下的空闲块加入到空闲链表中
            /*
            但是此处要注意保证按照地址升序排列
            原始代码此处是不正确的，此处已修正
            */
            SetPageProperty(p);
            // 把切割的后半部分插入到原来的块后面
            list_add_after(&(page->page_link), &(p->page_link));
        }
        // 然后从空闲链表中删除这个块
        list_del(&(page->page_link));
        // 更新参数，并保证分配出去的块标志位正确
        nr_free -= n;
        ClearPageProperty(page);
    }
    return page;
}

其实就是遍历一下双向链表，注意一下对空闲块分割后同样需要按照升序插入即可。

还有一个函数是default_free_pages，其作用是将物理页释放，即将物理页加入到空闲链表中。这个函数会稍微麻烦一点，毕竟会涉及到空闲块的合并

static void default_free_pages(struct Page *base, size_t n)
{
    assert(n > 0);
    struct Page *p = base;
    // 清除每页的标志位和引用计数
    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 = list_next(&free_list);
    while (le != &free_list)
    {
        p = le2page(le, page_link);
        le = list_next(le);
        // 如果p页的地址刚好紧接在以base页开头的空闲块之后
        // 就把base页和p页合并
        if (base + base->property == p)
        {
            base->property += p->property;
            ClearPageProperty(p);
            list_del(&(p->page_link));
        }
        // 如果p页的地址刚好紧接在以base页开头的空闲块之前
        // 就把p页和base页合并
        else if (p + p->property == base)
        {
            p->property += base->property;
            ClearPageProperty(base);
            base = p;
            list_del(&(p->page_link));
        }
    }

    // 至此，就将所有与base开头的块合并完毕

    // 更新一下空闲页的数量
    nr_free += n;

    /*
    同样，这里原函数也是不正确的
    需要寻找到合适的位置插入base，而不能直接在前面插入
    */
    le = list_next(&free_list);
    while (le != &free_list)
    {
        p = le2page(le, page_link); // 将空闲列表条目转换为页面
        if (base + base->property <= p)
        { // 地址大小由空闲块大小来表示
            assert(base + base->property != p);
            break;
        }
        le = list_next(le);
    }

    list_add_before(le, &(base->page_link));
}

这个函数首先要清除页面的各种标志位和引用计数，从而保证每一页都可以直接被分配。随后将空闲页加入到空闲链表中，合并分两种情况进行，一种是base页的地址刚好紧接在以base页开头的空闲块之后，另一种是p页的地址刚好紧接在以base页开头的空闲块之前。最后更新空闲页的数量，然后寻找到合适的位置插入base，而不能直接在前面插入。

修改完成后，输入make qemu即可看到第一项测试通过。

0X02 实现寻找虚拟地址对应的页表项

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

本实验要求实现一个get_pte函数，此函数找到一个虚拟地址对应的二级页表项的内核虚地址，如果此二级页表项不存在，则分配一个包含此项的二级页表(要认识到页表二级页表也在内存中)。

就是给定一个虚拟地址，返回下图中红框(即PTE)在内存中地址(也是虚拟地址)。

Intel 80386采用了二级页表来建立线性地址与物理地址之间的映射关系。由于我们已经具有了一个物理内存页管理器default_pmm_manager，支持动态分配和释放内存页的功能，我们就可以用它来获得所需的空闲物理页。在二级页表结构中，页目录表占4KB空间，可通过alloc_page函数获得一个空闲物理页作为页目录表（Page Directory Table，PDT）。同理，ucore也通过这种类似方式获得一个页表（Page Table，PT）所需的4KB空间。

在保护模式中，x86 体系结构将内存地址分成三种：逻辑地址（也称虚拟地址）、线性地址和物理地址。

• 段式存储在内存保护方面有优势，页式存储在内存利用和优化转移到后备存储方面有优势。
• 在段式存储管理基础上，给每个段加一级页表。同时，通过指向相同的页表基址，实现进程间的段共享。
• 在段页式管理中，操作系统弱化了段式管理中的功能，实现以分页为主的内存管理。段式管理只起到了一个过滤的作用，它将地址不加转换直接映射成线性地址。将虚拟地址转换为物理地址的过程如下：
  • 根据段寄存器中的段选择子，获取GDT中的特定基址并加上目标偏移来确定线性地址。由于GDT中所有的基址全为0（因为弱化了段式管理的功能，对等映射），所以此时的逻辑地址和线性地址是相同的。
  • 根据该线性地址，获取对应页表项，并根据该页表项来获取对应的物理地址。

一级页表（页目录表PageDirectoryTable, PDT）的起始地址存储于%cr3寄存器中。

在一个简单的两级页表中，页目录为每页页表包含了一项。它由多个页目录项（Page Directory Entries，PDE）组成。PDE（至少）拥有有效位（valid bit）和页帧号（page frame number，PFN），类似于 PTE。但是，正如上面所暗示的，这个有效位的含义稍有不同：如果 PDE 项是有效的，则意味着该项指向的页表（通过PFN）中至少有一页是有效的，即在该 PDE 所指向的页中，至少一个PTE，其有效位被设置为1。如果 PDE 项无效（即等于零），则 PDE的其余部分没有定义。

一个线性地址对应的各个页表项如下

// A linear address 'la' has a three-part structure as follows:
//
// +--------10------+-------10-------+---------12----------+
// | Page Directory |   Page Table   | Offset within Page  |
// |      Index     |     Index      |                     |
// +----------------+----------------+---------------------+
//  \--- PDX(la) --/ \--- PTX(la) --/ \---- PGOFF(la) ----/
//  \----------- PPN(la) -----------/
//
// The PDX, PTX, PGOFF, and PPN macros decompose linear addresses as shown.
// To construct a linear address la from PDX(la), PTX(la), and PGOFF(la),
// use PGADDR(PDX(la), PTX(la), PGOFF(la)).

由于get_pte函数中给出了详细的步骤注释，我们直接给出代码

注意，PTE内容的设置是调用者的职责，get_pte只需要给调用者一个可访问的PTE(page table entry)即可。

// get_pte - get pte and return the kernel virtual address of this pte for la
//         - if the PT contians this pte didn't exist, alloc a page for PT
//  parameter:
//   pgdir:  the kernel virtual base address of PDT
//   la:     the linear address need to map
//   create: a logical value to decide if alloc a page for PT
//  return vaule: the kernel virtual address of this pte
// pgdir是页目录 la是线性地址(虚拟地址) create是是否新建
pte_t *get_pte(pde_t *pgdir, uintptr_t la, bool create)
{
    // 这部分懒得翻译了，就是说了几个有用的宏
    /* LAB2 EXERCISE 2: YOUR CODE
     *
     * If you need to visit a physical address, please use KADDR()
     * please read pmm.h for useful macros
     *
     * Maybe you want help comment, BELOW comments can help you finish the code
     *
     * Some Useful MACROs and DEFINEs, you can use them in below implementation.
     * MACROs or Functions:
     *   PDX(la) = the index of page directory entry of VIRTUAL ADDRESS la.
     *   KADDR(pa) : takes a physical address and returns the corresponding kernel virtual address.
     *   set_page_ref(page,1) : means the page be referenced by one time
     *   page2pa(page): get the physical address of memory which this (struct Page *) page  manages
     *   struct Page * alloc_page() : allocation a page
     *   memset(void *s, char c, size_t n) : sets the first n bytes of the memory area pointed by s
     *                                       to the specified value c.
     * DEFINEs:
     *   PTE_P           0x001                   // page table/directory entry flags bit : Present
     *   PTE_W           0x002                   // page table/directory entry flags bit : Writeable
     *   PTE_U           0x004                   // page table/directory entry flags bit : User can access
     */
#if 1
    // 1. 先在一级页表中查找二级页表的地址
    // 一级页表中每一项都是PDE(page directory entry)
    // 指向一个二级页表
    pde_t *pdep = pgdir[PDX(la)]; // (1) find page directory entry
    // 2. 如果获取到的二级页表无效，那么就要创建一个有效的出来
    if (!(*pdep & PTE_P))
    {
        struct Page *p;
        if (create) // (2) check if entry is not present
        {
            // 3. 调用物理分配器分配一个物理页
            p = alloc_pages(1); // (3) check if creating is needed, then alloc page for page table
            if (p == NULL)
                return NULL;
        }
        else
            return NULL;
        // CAUTION: this page is used for page table, not for common data page
        // 4. 设置页面的引用计数为1
        set_page_ref(p, 1); // (4) set page reference

        // 5. 获取物理页的物理地址
        uintptr_t pa = page2pa(p); // (5) get linear address of page

        // 6. 清空物理页的内容，需要注意的是使用虚拟地址
        memset(KADDR(pa), 0, PGSIZE); // (6) clear page content using memset

        // 7. 将新分配的页面设置为当前缺失的页目录条目中,之后该页面就是其中的一个二级页面
        *pdep = pa | PTE_U | PTE_W | PTE_P; // (7) set page directory entry's permission
    }
    // 8. 返回在pgdir中对应于la的二级页表项(pte)
    return &((pte_t *)KADDR(PDE_ADDR(*pdep)))[PTX(la)]; // (8) return page table entry
#endif
}

其实我一开始对这里的虚拟地址和物理地址交替出现感到挺奇怪的，后来查阅了一下《操作系统真象还原》，因此给出自己的理解。

首先，即使在保护模式下，CPU总线上放的地址也是32位的物理地址。

在打开保护模式后，CPU会将页表地址加载到cr3寄存器中，这个地址存储的是物理地址，目的是方便直接送入CPU的总线中。

虽然内存分页机制是将虚拟地址转换成物理地址，但是在转换过程中相当于在关闭分页机制下进行，所有的页表和页表项的寻址，他们的地址都会被CPU当成最终的物理地址，直接送上总线，不会再被分页机制转换(否则因此递归转换)

但是有的时候，需要修改页表，程序访问页表的时候需要使用页表的虚拟地址，这种是通过自映射的方式实现的。

这里涉及到三个类型pte_t、pde_t和uintptr_t。通过参见mm/mmlayout.h和libs/types.h，可知它们其实都是unsigned int类型。在此做区分，是为了分清概念。

pde_t全称为 page directory entry，也就是一级页表的表项（注意：pgdir实际不是表项，而是一级页表本身。实际上应该新定义一个类型pgd_t来表示一级页表本身）。pte_t全称为 page table entry，表示二级页表的表项。uintptr_t表示为线性地址，由于段式管理只做直接映射，所以它也是逻辑地址。

pgdir给出页表起始地址。通过查找这个页表，我们需要给出二级页表中对应项的地址。虽然目前我们只有boot_pgdir一个页表，但是引入进程的概念之后每个进程都会有自己的页表。

有可能根本就没有对应的二级页表的情况，所以二级页表不必要一开始就分配，而是等到需要的时候再添加对应的二级页表。如果在查找二级页表项时，发现对应的二级页表不存在，则需要根据create参数的值来处理是否创建新的二级页表。如果create参数为0，则get_pte返回NULL；如果create参数不为0，则get_pte需要申请一个新的物理页，再在一级页表中添加页目录项指向表示二级页表的新物理页。注意，新申请的页必须全部设定为零，因为这个页所代表的虚拟地址都没有被映射。

当建立从一级页表到二级页表的映射时，需要注意设置控制位。这里应该设置同时设置上PTE_U、PTE_W和PTE_P。如果原来就有二级页表，或者新建立了页表，则只需返回对应项的地址即可。

虚拟地址只有映射上了物理页才可以正常的读写。在完成映射物理页的过程中，除了要像上面那样在页表的对应表项上填上相应的物理地址外，还要设置正确的控制位。

0X03 实现释放某虚地址所在的页并取消对应二级页表项的映射

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

刚才的实验是为了创建一个PTE项，现在的任务是删除一个PTE项。

因为和之前的实验类似，而且注释非常全，难度很低，对着弄就可以了。

// page_remove_pte - free an Page sturct which is related linear address la
//                 - and clean(invalidate) pte which is related linear address la
// note: PT is changed, so the TLB need to be invalidate
static inline void
page_remove_pte(pde_t *pgdir, uintptr_t la, pte_t *ptep)
{
    /* LAB2 EXERCISE 3: YOUR CODE
     *
     * Please check if ptep is valid, and tlb must be manually updated if mapping is updated
     *
     * Maybe you want help comment, BELOW comments can help you finish the code
     *
     * Some Useful MACROs and DEFINEs, you can use them in below implementation.
     * MACROs or Functions:
     *   struct Page *page pte2page(*ptep): get the according page from the value of a ptep
     *   free_page : free a page
     *   page_ref_dec(page) : decrease page->ref. NOTICE: ff page->ref == 0 , then this page should be free.
     *   tlb_invalidate(pde_t *pgdir, uintptr_t la) : Invalidate a TLB entry, but only if the page tables being
     *                        edited are the ones currently in use by the processor.
     * DEFINEs:
     *   PTE_P           0x001                   // page table/directory entry flags bit : Present
     */
#if 1

    // 1. 先检查输入的pte是否有效
    if (!(*ptep & PTE_P)) //(1) check if this page table entry is present
        return;

    // 2. 通过对应pte找到对应的page
    struct Page *page = pte2page(*ptep); //(2) find corresponding page to pte

    // 3. 减少page的引用计数
    page_ref_dec(page); //(3) decrease page reference

    // 4. 如果引用计数为0 释放page
    if (page->ref == 0)
        free_page(page); //(4) and free this page when page reference reachs 0

    // 5. 清除pte
    *ptep = 0; //(5) clear second page table entry

    // 6. 刷新tlb
    tlb_invalidate(pgdir, la); //(6) flush tlb

#endif
}

页表自映射

由于页表本身也是一个物理内存块，所有页表可以有一个项指向自身，一级页表和二级页表都有。更具体的可以参考这篇文章页表自映射。

页表自映射(这是一种设计手段)主要是为了保证能通过虚拟地址来访问页表。

正常页表里放的都是物理地址(一级页表里放的都是二级页表物理地址，二级页表放的是页面的物理地址)。但是程序有时候需要通过虚拟地址来访问页表，比如在页表中查找某个虚拟地址对应的页表项，这时候就需要页表自映射。

通过虚拟地址访问一级页表：

• 首先程序使用一级页表的虚拟地址访问
• 由于CPU本身就有寄存器存放一级页表物理地址，但是为了保证访问页表和其他页面的过程一致性，所以还是会通过页部件进行转换
• 页部件尝试从虚拟地址的第一段找出目标页面的二级页表地址，但由于一级页表自映射，所以得到的"二级页表"仍然是一级页表本身
• 然后页部件把从虚拟地址第二段找出目标页面的在"二级页表"的位置，同样还是一级页表自映射，相当于重复了一下操作(保证过程一致性)

通过虚拟地址访问二级页表：

• 首先程序使用二级页表的虚拟地址访问
• 页部件从虚拟地址的第一段找出目标页面的二级页表地址，此时正常页面一样，会得到二级页表的物理地址(此时就已经得到了目标二级页表物理地址)
• 然后页部件把从虚拟地址第二段找出目标页面的在二级页表的位置，此时二级页表自映射，得到二级页表物理地址

0X04 总结

通过这个lab2，我们学习了以下内容:

• 探测可用物理内存，并组织成块，实现函数来分配和释放物理内存块
• 一二级页表、实现函数来寻找二级页表项
• 理解页表中的项均为物理地址，但是同时页表还需要虚拟地址用于修改
• 理解保护模式在硬件上的组织(32位地址线、页表寄存器、地址检查)和软件上的组织(虚拟地址、页表)，所有在总线上的地址都是物理地址
• 页表自映射、页表虚拟地址和物理地址对应关系