Ucore_lab2

实验题目：Lab2

实验目的：

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

实验环境

操作系统： Ubuntu 20.04 LTS
虚拟机： Hyper-V
依赖： build-essential git qemu-system-x86 gdb make diffutils lib32z1

实验内容及操作步骤

本次实验包含三个部分。

首先了解如何发现系统中的物理内存；然后了解如何建立对物理内存的初步管理，即了解连续物理内存管理；最后了解页表相关的操作，即如何建立页表来实现虚拟内存到物理内存之间的映射，对段页式内存管理机制有一个比较全面的了解。

本实验里面实现的内存管理还是非常基本的，并没有涉及到对实际机器的优化，比如针对 cache 的优化等。如果大家有余力，尝试完成扩展练习。

练习 0 填写已有实验

涉及改动的文件如下，详见 >>这里<<：

kern/debug/kdebug.c
- print_stackframe
kern/trap/trap.c
- idt_init
- trap_dispatch

练习 1 实现 first-fit 连续物理内存分配算法

first-fit 算法

根据指导书^[1]中关于 first-fit 算法的介绍，阅读 Ucore kern/mm/default_pmm.c 代码，发现其几乎已经完全实现 first-fit 算法，但没有将空闲内存块按照地址从小到大的方式连接起来，所以我们加上相关实现即可。

`default_init_memmap`

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;
    list_add(&free_list, &(base->page_link));
}

由第 13 行可知，该函数将新页面插入链表时，没有按照地址顺序插入，我们需要修改代码，使其按照地址顺序插入：

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;
-   list_add(&free_list, &(base->page_link));
+   list_add_before(&free_list, &(base->page_link));
}

最后代码如下：

static void
default_init_memmap(struct Page *base, size_t n) {
    assert(n > 0); // 判断 n
    struct Page *p = base;
    for (; p != base + n; p ++) { // 初始化 n 块物理页
        assert(PageReserved(p)); // 检查是否为保留页
        p->flags = p->property = 0; // 标志位清 0
        set_page_ref(p, 0); // 清除引用此页的虚拟页的个数
    }
    base->property = n; // 修改 base 的连续空页值为 n
    SetPageProperty(base); // 设置内存区域第一页属性
    nr_free += n; // 计算空闲页总数
    list_add_before(&free_list, &(base->page_link)); //加入空闲链表
}

`default_alloc_pages`

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) {
        struct Page *p = le2page(le, page_link);
        if (p->property >= n) {
            page = p;
            break;
        }
    }
    if (page != NULL) {
        list_del(&(page->page_link));
        if (page->property > n) {
            struct Page *p = page + n;
            p->property = page->property - n;
            list_add(&free_list, &(p->page_link));
    }
    nr_free -= n;
    ClearPageProperty(page);
    }
    return page;
}

在原先的代码中，当获取到了一个大小足够大的页面地址时，程序会先将该页头从链表中断开，切割，并将剩余空间放回链表中。

但将剩余空间放回链表时，并没有按照地址顺序插入链表。

对代码进行如下修改：

  if (page != NULL) {
-   list_del(&(page->page_link));
    if (page->property > n) {
      struct Page *p = page + n;
      p->property = page->property - n;
+     SetPageProperty(p); 
-     list_add(&free_list, &(p->page_link));
+     list_add_after(&(page->page_link), &(p->page_link));
    }
+   list_del(&(page->page_link));
    nr_free -= n;
    ClearPageProperty(page);
  }

最终代码如下：

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) {
        struct Page *p = le2page(le, page_link);
        // 找到符合条件的
        if (p->property >= n) {
            page = p;
            break;
        }
    }
    if (page != NULL) {
        // 如果分配 n 个后还有 page 页，则后面的补上
        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);
        if (base + base->property == p) {
            base->property += p->property;
            ClearPageProperty(p);
            list_del(&(p->page_link));
        }
        else if (p + p->property == base) {
            p->property += base->property;
            ClearPageProperty(base);
            base = p;
            list_del(&(p->page_link));
        }
    }
    nr_free += n;
    list_add(&free_list, &(base->page_link));
}

由第 29 行可知，该函数默认在末尾处，将待释放的页头插入至链表的第一个节点。

所以我们需要修改，使其按照地址顺序插入对应链表结点：

-   nr_free += n;
-   list_add(&free_list, &(base->page_link));
+   for(le = list_next(&free_list); le != &free_list; le = list_next(le))
+   {
+       p = le2page(le, page_link);
+       if (base + base->property <= p) {
+           assert(base + base->property != p);
+           break;
+       }
+   }
+   list_add_before(le, &(base->page_link));

最终代码如下：

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);
        if (base + base->property == p) {
            base->property += p->property;
            ClearPageProperty(p);
            list_del(&(p->page_link));
        }
        else if (p + p->property == base) {
            p->property += base->property;
            ClearPageProperty(base);
            base = p;
            list_del(&(p->page_link));
        }
    }
    nr_free += n;
    for(le = list_next(&free_list); le != &free_list; le = list_next(le))
    {
        p = le2page(le, page_link);
        if (base + base->property <= p) {
            assert(base + base->property != p);
            break;
        }
    }
    list_add_before(le, &(base->page_link));
}

练习 2 实现寻找虚拟地址对应的页表项

通过设置页表和对应的页表项，可建立虚拟内存地址和物理内存地址的对应关系。

其中的get_pte函数是设置页表项环节中的一个重要步骤。此函数找到一个虚地址对应的二级页表项的内核虚地址，如果此二级页表项不存在，则分配一个包含此项的二级页表。

下面是具体实现，对应kern/mm/pmm.c文件

pte_t * 
get_pte(pde_t *pgdir, uintptr_t la, bool create) {
    // 获取传入的线性地址中所对应的页目录条目的物理地址
    pde_t *pdep = &pgdir[PDX(la)];
    // 如果该条目不可用(not present)
    if (!(*pdep & PTE_P)) {
        struct Page *page;
        // 如果分配页面失败，或者不允许分配，则返回NULL
        if (!create || (page = alloc_page()) == NULL)
            return NULL;
        // 设置该物理页面的引用次数为1
        set_page_ref(page, 1);
        // 获取当前物理页面所管理的物理地址
        uintptr_t pa = page2pa(page);
        // 清空该物理页面的数据。需要注意的是使用虚拟地址
        memset(KADDR(pa), 0, PGSIZE);
        // 将新分配的页面设置为当前缺失的页目录条目中
        // 之后该页面就是其中的一个二级页面
        *pdep = pa | PTE_U | PTE_W | PTE_P;
    }
    // 返回在pgdir中对应于la的二级页表项
    return &((pte_t *)KADDR(PDE_ADDR(*pdep)))[PTX(la)];
}

请描述页目录项（Page Directory Entry）和页表项（Page Table Entry）中每个组成部分的含义以及对ucore而言的潜在用处。

每个页目录（PDE）都由一个32位整数来存储数据，其结构如下

bit 0(P): resent 位，若该位为 1 ,则 PDE 存在，否则不存在。
bit 1(R/W): read/write 位，若该位为 0 ,则只读，否则可写。
bit 2(U/S): user/supervisor位。
bit 3(PWT): page-level write-through，若该位为1则开启页层次的写回机制。
bit 4(PCD): page-level cache disable，若该位为1,则禁止页层次的缓存。
bit 5(A): accessed 位，若该位为1,表示这项曾在地址翻译的过程中被访问。
bit 6: 该位忽略。
bit 7(PS): 这个位用来确定 32 位分页的页大小，当该位为 1 且 CR4 的 PSE 位为 1 时，页大小为4M，否则为4K。
bit 11:8: 这几位忽略。
bit 32:12: 页表的PPN（页对齐的物理地址）。

页表项：

页表项除了第 7 ， 8 位与 PDE 不同，其余位作用均相同。

bit 7(PAT): 如果支持 PAT 分页，间接决定这项访问的 4 K 页的内存类型;如果不支持，这位保留（必须为 0 ）。
bit 8(G): global 位。当 CR4 的 PGE 位为 1 时，若该位为 1 ，翻译是全局的;否则，忽略该位。

其中被忽略的位可以被操作系统用于实现各种功能;和权限相关的位可以用来增强ucore的内存保护机制;access 位可以用来实现内存页交换算法。

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

将引发页访问异常的地址将被保存在cr2寄存器中
设置错误代码
引发Page Fault，将外存的数据换到内存中
进行上下文切换，退出中断，返回到中断前的状态

练习 3 释放某虚地址所在的页并取消对应二级页表项的映射

当释放一个包含某虚地址的物理内存页时，需要让对应此物理内存页的管理数据结构Page做相关的清除处理，使得此物理内存页成为空闲；另外还需把表示虚地址与物理地址对应关系的二级页表项清除。

这个练习跟之前 Lab 1 最后一个练习一样，看着注释就能写完了，仍然是在kern/mm/pmm.c：

static inline void
page_remove_pte(pde_t *pgdir, uintptr_t la, pte_t *ptep) {
    // 如果传入的页表条目是可用的
    if (*ptep & PTE_P) {
        // 获取该页表条目所对应的地址
        struct Page *page = pte2page(*ptep);
        // 如果该页的引用次数在减1后为0
        if (page_ref_dec(page) == 0)
            // 释放当前页
            free_page(page);
        // 清空PTE
        *ptep = 0;
        // 刷新TLB内的数据
        tlb_invalidate(pgdir, la);
    }
}

数据结构Page的全局变量（其实是一个数组）的每一项与页表中的页目录项和页表项有无对应关系？如果有，其对应关系是啥？

当页目录项或页表项有效时，Page数组中的项与页目录项或页表项存在对应关系。
页目录表中存放着数个页表条目PTE，这些页表条目中存放了某个二级页表所在物理页的信息，包括该二级页表的物理地址，但使用线性地址的头部PDX(Page Directory Index)来索引页目录表。
总结一下，页目录表内存放二级页表的物理地址，但却使用线性地址索引页目录表中的条目。
而页表（二级页表）与页目录（一级页表）具有类似的特性，页表中的页表项指向所管理的物理页的物理地址（不是数据结构Page的地址），使用线性地址的中部PTX(Page Table Index)来索引页表。
当二级页表获取物理页时，需要对该物理页所对应的数据结构page来做一些操作。其操作包括但不限于设置引用次数，这样方便共享内存。
为什么页目录表中存放的是物理地址呢？可能是为了防止递归查找。
即原先查找页目录表的目的是想将某个线性地址转换为物理地址，但如果页目录表中存放的是二级页表的线性地址，则需要先查找该二级页表的物理地址，此时需要递归查找，这可能会出现永远也查找不到物理地址的情况。

如果希望虚拟地址与物理地址相等，则需要如何修改lab2，完成此事？

将labcodes/lab2/tools/kernel.ld中的加载地址从0xC0100000修改为0x00100000
```
// 修改前
. = 0xC0100000;
// 修改后
. = 0x00100000;
```

将mm/memlayout.h中的内核偏移地址修改为0

// 修改前
#define KERNBASE            0xC0000000
// 修改后
#define KERNBASE            0x00000000

虽然没有用到VPT，但还是建议从 0xFAC00000 改为 0xC2C00000

最后一步，关闭页机制。

将开启页机制的那一段代码删除或注释掉最后一句即可。

ucore_lab/labcodes/lab2/kern/init/entry.S

# 修改后
movl %cr0, %eax
orl $(CR0_PE | CR0_PG | CR0_AM | CR0_WP | CR0_NE | CR0_TS | CR0_EM | CR0_MP), %eax
andl $~(CR0_TS | CR0_EM), %eax
# 注释了最后一句
# movl %eax, %cr0

实验结果及分析

btmuli@amadus:~/桌面/OS/labcodes/lab2$ make qemu
WARNING: Image format was not specified for 'bin/ucore.img' and probing guessed raw.
         Automatically detecting the format is dangerous for raw images, write operations on block 0 will be restricted.
         Specify the 'raw' format explicitly to remove the restrictions.
(THU.CST) os is loading ...

Special kernel symbols:
  entry  0x00100033 (phys)
  etext  0x001060ba (phys)
  edata  0x0011c000 (phys)
  end    0x0011cf28 (phys)
Kernel executable memory footprint: 116KB
ebp:0x00118f38eip:0x00100ae6args:0x000100940x000100940x00118f680x001000c9
    kern/debug/kdebug.c:298: print_stackframe+25
ebp:0x00118f48eip:0x00100e00args:0x000000000x000000000x000000000x00118fb8
    kern/debug/kmonitor.c:129: mon_backtrace+14
ebp:0x00118f68eip:0x001000c9args:0x000000000x00118f900xffff00000x00118f94
    kern/init/init.c:49: grade_backtrace2+37
ebp:0x00118f88eip:0x001000f7args:0x000000000xffff00000x00118fb40x0000002a
    kern/init/init.c:54: grade_backtrace1+42
ebp:0x00118fa8eip:0x0010011aargs:0x000000000x001000330xffff00000x0000001d
    kern/init/init.c:59: grade_backtrace0+27
ebp:0x00118fc8eip:0x00100144args:0x001060dc0x001060c00x00000f280x00000000
    kern/init/init.c:64: grade_backtrace+38
ebp:0x00118ff8eip:0x00100088args:0x001062bc0x001062c40x00100d7c0x001062e3
    kern/init/init.c:29: kern_init+84
memory management: default_pmm_manager
e820map:
  memory: 0009fc00, [00000000, 0009fbff], type = 1.
  memory: 00000400, [0009fc00, 0009ffff], type = 2.
  memory: 00010000, [000f0000, 000fffff], type = 2.
  memory: 07ee0000, [00100000, 07fdffff], type = 1.
  memory: 00020000, [07fe0000, 07ffffff], type = 2.
  memory: 00040000, [fffc0000, ffffffff], type = 2.
check_alloc_page() succeeded!
check_pgdir() succeeded!
kernel panic at kern/mm/pmm.c:496:
    assertion failed: boot_pgdir[0] == 0
stack trackback:
ebp:0x00118f18eip:0x00100ae6args:0x001061880x00118f5c0x000001f00x0000029b
    kern/debug/kdebug.c:298: print_stackframe+25
ebp:0x00118f48eip:0x0010048fargs:0x001068d00x000001f00x001068bb0x00106c3c
    kern/debug/panic.c:27: __panic+107
ebp:0x00118f88eip:0x00103e70args:0x0011a0000x380000000x380000000x38000000
    kern/mm/pmm.c:496: check_boot_pgdir+351
ebp:0x00118fc8eip:0x00103323args:0x001060dc0x001060c00x00000f280x00000000
    kern/mm/pmm.c:314: pmm_init+126
ebp:0x00118ff8eip:0x0010008dargs:0x001062bc0x001062c40x00100d7c0x001062e3
    kern/init/init.c:31: kern_init+89
Welcome to the kernel debug monitor!!
Type 'help' for a list of commands.

收获与体会

经过这次实验，个人对于操作系统页表分配、虚拟地址跟物理地址的转换有了更加清晰的认识。

物理内存页分配算法实现 · ucore_os_docs (gitbooks.io) ↩︎