ucore lab2 实验报告

不愧是内存管理,读了一晚上的源码。

  1. ucore lab1 实验报告
  2. ucore lab2 实验报告
  3. ucore lab3 实验报告

流程

相比于 lab1 , lab2 主要是开启了分页机制。在较老的 ucore 代码中,是先进行一次 GDT 调整性加载内核段寄存器。而在 twd2 大佬的一次 PR 之后,直接从 kern/init/entry.S 的 kern_entry 函数开始就开启分页管理,除此之外它还优化了一波参考答案。但是可惜的是文档还没有跟上,文档的内容都是过时的。

在这个阶段物理地址和逻辑地址映射我们也没必要担心,不论是新代码还是老代码都做好了平滑切换的过程,到我们需要补充代码的地方都已经是 Logical-Address = Linear-Address + KERNBASE 了,因此现在访存均为 KERNBASE + offset 模式的,这也是宏 KADDR(offset) 的工作——也就是从原先 lab1 的物理地址转换为逻辑地址。

twd2 提交的 patch 只是使得 ucore 直接在 kern/init/entry.S 完成了临时映射的过渡,建立了物理地址 0 ~ 4MB 的页表,将这部分的页表同时映射到了原地 (boot_pgdir[0]) 和 KERNBASE=0xc0000000 (boot_pgdir[0x300]) 以上,并在 jmp 之后删去了从 0 开始的那个映射 (boot_pgdir[0]) ,从这里开始就正式进入分页管理模式。

因此我们不需要去理会物理地址和虚地址映射的问题。只需要考虑物理地址管理。这方面,源码中提供了 struct pmm_manager 结构体,只要实现了这个接口就可以作为物理内存管理器来使用。默认的管理器实现在 kern/mm/default_pmm.c 中,采用的是 FFMA ,这里需要我们实现一部分以达到文档中要求的链表的有序性。

除此之外还有两个杂项,一个是

练习0:填写已有实验

其实 lab1 中只有 kern/debug/kdebug.c kern/init/init.c kern/trap/trap.c 被我改了, diffpatch 没有方便的冲突处理,这俩又在同一个 git 仓库下,不好 merge ,于是我直接开 vimdiff 手动改了。

也就几个函数而已。

练习1:实现 first-fit 连续物理内存分配算法(需要编程)

kern/mm/default_pmm.c 中都是默认内存分配器的实现,一开始一大段超长的注释,解释了分配器的具体算法,看完之后翻一下几个函数——这不都写好了吗?

不过跑了一下 make qemu 还是没法通过 assert ,实际上它们的实现并不完整,需要我们增加内容。

default_check 中的第 37 行的断言失败(我已经改了源码,忘了是文件第几行了……)。过一遍检查的流程会发现,断言失败之前的检查都是针对页分配成功、失败的测试,从失败的断言这里开始是对分配的页的位置进行的检查。

实际上,最初的实现 default_*_pages 只是简单的插入到链表,根本没有关心被插入到了哪里,所以在多次 alloc/free 之后页块在链表中的位置乱得一塌糊涂……如果需要保序,我们需要对每个改动链表的地方注意一下位置。

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

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;
    le = &free_list;
    while ((le = list_next(le)) != &free_list)
        if (base < le2page(le, page_link)) break;
    list_add_before(le, &base->page_link);
}

成功了会有一个提示

check_alloc_page() succeeded!

然后会在另一个地方断言挂掉,那是接下来的实验了。

Question 1

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

当然啦,这种东西用线段树可以实现 alloc 和 free 达到 O(\log n) 级别的时间复杂度,不过空间(复杂度虽然还是 O(n) 不变)要增加一倍。

当然我懒得写,这几乎就是 challenge 的内容, buddy system 的本质就是线段树维护零散的可分配的内存块,从根往下找罢了。

话说这就不叫 First Fit 了吧?不过线段树的确可以做到每次 alloc 和 First Fit 分配的页地址完全相同,当然可以做到更好,不过那就不是 First Fit 而是 Best Fit 了……

练习2:实现寻找虚拟地址对应的页表项(需要编程)

具体是在 check_pgdir 函数中一个断言 get_pte 返回值失败的,看到 get_pte 函数,就是第二个练习需要编写修改的地方。

这里稍微涉及到了物理地址和虚拟地址的转换……不过不用在意细节,只需要把头文件里的几个函数和宏过一遍,主要是 kern/mm/pmm.c kern/mm/mmu.h kern/mm/memlayout.h 这仨。

get_pte ,是给出 Page Directory 基址和物理地址,求对应的 Page Table Entry 地址。按照注释给出的八个流程来就差不多了。

pte_t *get_pte(pde_t *pgdir, uintptr_t la, bool create) {
  pde_t *pdep = pgdir + PDX(la);
  if ((*pdep & PTE_P) == 0) {
    if (!create) return NULL;
    struct Page *page = alloc_page();
    if (page == NULL) return NULL;
    set_page_ref(page, 1);
    uintptr_t pa = page2pa(page);
    memset(KADDR(pa), 0, PGSIZE);
    *pdep = pa | PTE_USER;
  }
  pte_t *pa = (pte_t *)PTE_ADDR(*pdep) + PTX(la);
  return KADDR((uintptr_t)pa);
}

首先注释中的 pdep (我猜是 Page Directory Entry Pointer ),就是 PD 基质加上 PDE 编号,编号就是 LA 的高十位( x86 的约定),可以通过 PDX 宏获取。

然后检查是否设置了 Present 位,也就是 PDE_P 位。不过实际上并没有 PDE_P 这个宏,使用注释里告诉我们的等价的 PTE_P 来检查(注释里告诉我们这个位是 PDE 和 PTE 通用的,虽然这三个位的确是通用的,不过毕竟 PD 和 PT 的保留位还是有所不同的)。

如果没有设置而且 bool create 设置为需要申请,就需要按注释 (3) ~ (7) 中提示一般的 alloc 一个页、设置引用计数、获得线性地址、使用 memset 清空页内容、设置 PDE 项中权限位。

最后再从 la 中获取一下中间十位,也就是 PTE 编号,从 PD 获取一下基址,相加就是 PTE 的线性地址了,用 KADDR 处理一下即可。

解决了的话应该会输出一行

check_pgdir() succeeded!

然后在下一个断言的地方挂掉(好吧我改了源文件,忘了具体哪一行了),总之是针对页面的引用计数的断言挂了,这又是下一个练习的任务了。

然后回答一下要求里的俩问题——

Question 1

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

再次召唤 OSDev.org 了……

PDE 详解

从低到高,分别是:

  • P (Present) 位:表示该页保存在物理内存中。
  • R (Read/Write) 位:表示该页可读可写。
  • U (User) 位:表示该页可以被任何权限用户访问。
  • W (Write Through) 位:表示 CPU 可以直写回内存。
  • D (Cache Disable) 位:表示不需要被 CPU 缓存。
  • A (Access) 位:表示该页被写过。
  • S (Size) 位:表示一个页 4MB 。
  • 9-11 位保留给 OS 使用。
  • 12-31 位指明 PTE 基质地址。

PTE 详解

从低到高,分别是:

  • 0-3 位同 PDE。
  • C (Cache Disable) 位:同 PDE D 位。
  • A (Access) 位:同 PDE 。
  • D (Dirty) 位:表示该页被写过。
  • G (Global) 位:表示在 CR3 寄存器更新时无需刷新 TLB 中关于该页的地址。
  • 9-11 位保留给 OS 使用。
  • 12-31 位指明物理页基址。

Question 2

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

用 cr2 保存触发异常的虚地址,然后触发 14 号中断也就是缺页错误,这些是硬件做的事情。

剩下的 ISR 就是软件的事情了。

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

之前断言失败是因为在 page_insert 中调用了 page_remove_pte ,而 page_remove_pte 并没有修改引用计数所以导致了对于引用计数的断言失败。

跟着注释走的话,应该不难:

static void inline page_remove_pte(pde_t *pgdir, uintptr_t la, pte_t *ptep) { 
  if ((*ptep & PTE_P) == 0) return;
  struct Page *page = pte2page(*ptep);
  page_ref_dec(page);
  if (page_ref(page) == 0)
    free_page(page);
  *ptep = 0;
  tlb_invalidate(pgdir, la);
}

首先判断一下 ptep 是不是合法——检查一下 Present 位就是了。

然后通过注释中所说的,通过 pte2page(*ptep) 获取相应页,减少引用计数并决定是否释放页。

最后把 TLB 中该页的缓存刷掉就可以了。

最后是可以反应时钟中断和键盘中断的,不过切换内核态用户态的中断跑不过去,因为 lab5 还有用户进程创建运行的练习,所以这里我就直接删掉了内核用户态切换的部分……

Question 1

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

可以参照 kern/mm/pmm.h 中的转换函数。

其实就是 Page 全局数组中以 Page Directory Index 和 Page Table Index 的组合 PPN (Physical Page Number) 为索引的那一项。

Question 2

如果希望虚拟地址与物理地址相等,则需要如何修改lab2,完成此事? 鼓励通过编程来具体完成这个问题

托 twd2 几个月前的 PR 的福,这题突然变得难了一点。

首先

  1. (托 twd2 的福)将开启分页这步操作先从 kern/init/entry.S 取消,否则在分页模式,取消掉 boot_pgdir[0] 的页表下 kern_init 会被置于一个根本无法访问到的地址。不过简单关闭分页估计会导致出现一些奇怪的错误,毕竟 user mode 的 GDT 没有 load 。

然后,正如实验手册所说的

  1. KERNBASE 调整回 0x00000000 。
  2. 链接脚本修改虚拟地址为 0x00100000 。

于是这样内核就会被置于正确的位置, eip 不会跑偏。

接下来的问题是 check_pgdircheck_boot_pgdir 这两个检查函数会变得乱七八糟。它们都假设 KERNBASE 不为 0 ,所以会对 Linear Address 为 0 的地址为所欲为所欲为,比如查询 0 地址的页表分配、给 0 地址申请页表,对其动手动脚,写入数据等。不仅仅是威胁到内核安全,主要是页表操作失败本身就会导致断言失败。

所以这两个函数直接去掉就好了。

后记

这玩意儿花了我两天,花了一天在研究源码上。

这几周集训队那边要出题,我不熟悉的字符串专题,周三的 deadline ,结果周二又被(同事?大概吧?)叫去搬砖,苦得要死。然后又花了一整天来追番(春物真好看,这波实验做完了我要去追小说),没多少时间做这东西。

两个 challenge 做完 lab3 之后再考虑补一下,看了一下具体的算法,感觉可能又要一个 challenge 用一天才写得完。

buddy system 和 slub 算法打算今天花一天肝出来,另开一篇文章写了,咕。

发表评论

电子邮件地址不会被公开。 必填项已用*标注