Lab2实验报告

思考题

Thinking 2.1 请根据上述说明，回答问题：在编写的 C 程序中，指针变量中存储的地址被视为虚拟地址，还是物理地址？MIPS 汇编程序中 lw和sw 指令使用的地址被视为虚拟地址，还是物理地址？

都是虚拟地址。

Thinking2.2请思考下述两个问题：
•从可重用性的角度，阐述用宏来实现链表的好处。
•查看实验环境中的/usr/include/sys/queue.h，了解其中单向链表与循环链表的实现，比较它们与本实验中使用的双向链表，分析三者在插入与删除操作上的性能差异。

可重用性：

  1. 各类结构体都可以使用queue.h的宏，简化代码量。
  2. 复杂宏可以大量使用简单宏。
  3. 可读性强，易于维护。

差异：

  1. 单向链表：对于单纯的插入和删除操作只有O(1)的时间复杂度，但是对于任意第i个元素的插入和删除操作来说，泽需要从头遍历一遍故而时间复杂度会上升到O(n)。
  2. 双向链表：对于任意第i个元素的插入和删除操作复杂度都只有O(1)。
  3. 循环链表：
    1. 单向循环链表：和单向链表一样，对于任意第i个元素的插入和删除操作来说，时间复杂度会为O(n)。
    2. 双向循环链表：和双向链表一样，对于任意第i个元素的插入和删除操作来说，时间复杂度会为O(1)。

Thinking2.3请阅读include/queue.h以及include/pmap.h,将Page_list的结构梳理清楚，选择正确的展开结构。
选C。

1
2
3
4
5
6
7
8
9
structPage_list{ 
    struct {
        struct{
            structPage *le_next;
            structPage **le_prev;
        }pp_link; 
        u_shortpp_ref; 
    }*lh_first;
}

Thinking 2.4 请思考下面两个问题：
• 请阅读上面有关TLB的描述，从虚拟内存和多进程操作系统的实现角度，阐述ASID的必要性。
• 请阅读 MIPS 4Kc 文档《MIPS32® 4K™ Processor Core Family Software User’s Manual》的 Section 3.3.1 与 Section 3.4，结合 ASID 段的位数，说明 4Kc 中可容纳不同的地址空间的最大数量。

  • 从虚拟内存实现角度看，ASID 的核心价值是让同一虚拟地址在不同地址空间中共存。也就是说，TLB 实际匹配的不是“虚拟页号” alone，而是“虚拟页号 + 当前 ASID”。这样两个进程都把代码装在例如 0x00400000 处也不会冲突，因为它们对应的是不同的地址空间标识。4Kc 手册对 TLB 命中条件的描述是：当前进程的 ASID（来自 EntryHi）必须和 TLB 项中的 ASID 匹配，或者该项被标记为全局项。
  • 从多进程操作系统实现角度看，ASID的另一个重要作用是减少进程切换时清空 TLB 的频率。如果没有 ASID，每次切换进程都必须大规模冲刷 TLB，否则旧进程留下的虚拟地址映射会污染新进程；而有了 ASID，内核只要在切换时改当前地址空间的 ASID，就可以让不同进程的 TLB 项并存，只有冲突或复用 ASID 时才需要额外处理。手册对这一点写得很直接：4Kc 使用的是 8-bit ASID，并且它就是为了减少上下文切换时 TLB flush 的频率。
  • 8位ASID,256个地址空间

Thinking 2.5 请回答下述三个问题：
• tlb_invalidate 和 tlb_out 的调用关系？
• 请用一句话概括tlb_invalidate 的作用。
• 逐行解释tlb_out 中的汇编代码。

  1. tlb_invalidate 在C代码中被调用，而它内部再调用汇编函数tlb_out来真正删除TLB中得旧表项。
  2. 将指定地址空间asid下虚拟地址va对应得旧TLB表项无效化，从而保证页表更新后TLB与与页表保持一致。
  3. 逐行解释
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    LEAF(tlb_out)#定义一个叶子函数(内部不会再调用别的函数)
    .set noreorder#告诉编译器不要自动重拍后面的指令
    	mfc0    t0, CP0_ENTRYHI#把当前CP0的EntryHi寄存器的内容读到t0
    	mtc0    a0, CP0_ENTRYHI#把参数a0写入EntryHi寄存器
    	nop #延迟指令，保证tlbp真正使用的是刚写进去的新EntryHi
    	tlbp #TLB的probe指令，，根据EntrtHi中的key,到TLB里查找匹配项
    	nop #延迟指令
    	mfc0    t1, CP0_INDEX #把probe的结果从CP0_Index读到t1
    .set reorder #允许汇编器进行普通重排
    	bltz    t1, NO_SUCH_ENTRY #如果t1<0，TLB里没有这个旧项，直接退出
    .set noreorder #禁止重排，下面要操作CP0
    	mtc0    zero, CP0_ENTRYHI #EntryHi清零，把覆盖写回TLB的表项的key设成0
    	mtc0    zero, CP0_ENTRYLO0 #偶页映射信息清零
    	mtc0    zero, CP0_ENTRYLO1 #奇页映射信息清零
        #即准备一个空表项来覆盖旧的TLB项
    	nop #等待CP0写入完成
    	tlbwi #TLB write indexed指令
        #按照CP0_Index指定的位置把刚才3个寄存器的内容写回TLB,即把刚刚找到的那条旧TLB表项覆盖成空项，从而实现删除/无效化

    .set reorder #恢复普通重排

    NO_SUCH_ENTRY: #没找到对应的TLB项时跳转到这里
    	mtc0    t0, CP0_ENTRYHI #把一开始备份再t0里的旧EntryHi恢复回去，这样函数执行完后不会破坏调用者原来看到的EntryHi状态
    	j       ra #跳回返回地址ra,函数结束
    END(tlb_out) #函数定义结束

Thinking 2.6 请结合 Lab2 开始的 CPU 访存流程与下图中的 Lab2 用户函数部分，尝试将函数调用与CPU访存流程对应起来，思考函数调用与CPU访存流程的关系。

  1. user process 对应 CPU 发出虚拟地址
  2. TLB miss 对应 MMU 查询 TLB 失败，随后进入 do_tlb_refill / _do_tlb_refill 异常处理流程
  3. 内核通过 page_lookup 在页表中查找映射
    1. 若映射不存在，则通过 passive_alloc、page_alloc、page_insert 和 pgdir_walk 分配物理页并建立页表映射
    2. 再通过 TLB 维护函数使 TLB 与页表保持一致。
      由此可见，函数调用链实际上就是 CPU 访存流程中“软件维护虚拟内存与 TLB”的具体实现。

Thinking 2.7 简单了解并叙述X86体系结构中的内存管理机制，比较X86和MIPS 在内存管理上的区别。

  • X86
    • 以内存分页为核心，依靠硬件按CR3指向的多级页表自动完成地址翻译，并用TLB缓存结果。
    • 通常由页表统一组织用户态和内核态映射，并通过CR3/PCID管理地址空间切换。
  • MIPS
    • 4Kc采用两级页表+软件管理TLB的方式，TLB miss 后需要内核显示执行refill。
    • 地址空间上显式划分了kuseg/kseg0/kseg1/kseg2，并用ASID区分不同地址空间。

在现代的 64 位系统中，提供了 64 位的字长，但实际上不是 64 位页式存储系统。假设在64位系统中采用三级页表机制，页面大小4KB。由于64位系统中字长为8B，且页目录也占用一页，因此页目录中有512 个页目录项，因此每级页表都需要9位。因此在64位系统下，总共需要3×9+12=39位就可以实现三级页表机制，并不需要64位。
现考虑上述39位的三级页式存储系统，虚拟地址空间为512GB，若三级页表的基地址为PTbase，请计算：
• 三级页表页目录的基地址。
• 映射到页目录自身的页目录项（自映射）

  • 页目录的第$V$项

难点分析

lab2的难点主要不在“代码量大”，而在于抽象层次多、前后依赖强、很容易在地址和状态转换上出错。可以概括成下面 5 个部分。

1. 页式内存管理整体流程的建立

Lab2 不是单独实现某一个函数，而是从物理页管理、页表建立到 TLB 重填，逐步搭起整套内存管理机制。前面的 page_init、page_alloc、page_free 负责物理页的分配与回收；中间的 pgdir_walk、page_insert 负责页表项的查找和映射建立；后面的 _do_tlb_refill、do_tlb_refill 负责在 TLB 缺失时恢复映射。只有把这些函数放到同一条流程里理解，才能真正看清虚拟地址到物理地址转换的完整路径

2. 地址转换关系容易混淆

Lab2 中同时出现了虚拟地址、物理地址、页表项中的物理页号，以及 kseg0 段用于访问物理页的内核虚拟地址。这几种地址在代码里不断转换，很容易混淆。实现过程中必须明确：CPU 访问的是虚拟地址，页表项里保存的是物理页号，而内核对某个物理页内容进行读写时，通常要先把它转换成 kseg0 对应的虚拟地址再访问。对这些关系理解不清，就容易在 page2pa、page2kva、PADDR、KADDR 这些转换上出错

3. 物理页状态维护需要保持一致

page_alloc、page_free、page_decref 这些函数代码不长，但都直接影响空闲链表和引用计数的正确性。实现时既要保证空闲页能够正确地从 page_free_list 中取出和回收，也要保证 pp_ref 的增减与映射关系一致。只要某一步顺序处理不当，就可能导致空闲链表错误、重复释放页面，或者引用计数异常，进而影响后续所有页表操作和测试结果

4. 页表查找与映射建立是核心理解点

pgdir_walk 和 page_insert 是 Lab2 中最关键的两个函数。pgdir_walk 决定了如何通过虚拟地址中的 PDX 和 PTX 找到对应页表项，并在需要时建立二级页表；page_insert 则负责把某个物理页映射到指定虚拟地址，同时维护页表项、引用计数和旧映射关系。对这两个函数的理解程度，直接影响后续 page_lookup、passive_alloc 以及 TLB refill 的实现效果

5. TLB 重填机制抽象层次较高

TLB refill 部分是 Lab2 中理解难度最高的内容之一。这里不仅要理解页表，还要理解 CPU 在访存时如何依赖 TLB 完成地址转换。当 TLB 缺项时，系统先通过页表查找对应映射；如果页表项还不存在，则通过 passive_alloc 分配物理页并建立映射，最后再把结果写入 TLB。这个过程把页表、异常处理和硬件寄存器操作联系到了一起，需要同时把 C 代码逻辑和底层异常处理流程对应起来

自映射

MIPS 4Kc采取两级页表储存制。

  • 从一级页表到二级页表是一级映射，从二级页表到物理内存是二级映射。
  • 为了方便的访问二级页表，物理内存中有一部分是二级页表的映射。
  • 而从二级页表到这一块内存的映射和从一级页表到二级页表的一级映射完全相同。即二级页表的4MB中有4KB的内容和一级页表的4KB完全相同。
    • 那么一级页表的4KB中有4B存的就是二级页表中这4KB的PTbase(实际上也等于PDbase，就是页目录的物理首地址PADDR(pgdir))。
    • 自映射时我们就需要定位到这4B,也就是说当自映射时所有va的PDX都是相同的，都指向这4B。

自映射的建立

假如把这4MB映射到[base,base+1024*PAGE_SIZE)
则页目录项是1024个页表中第PDX(base)项
建立页目录自映射:pgdir[PDX(base)] = PADDR(pgdir)|PTE_V
(注意这个页目录项不可写即没有有效位PTE_D)

自映射的建立就是通过页目录项找到自己
核心是改变自映射页目录项存的物理地址
则通过base为基址的va可以找到

自映射的地址转换

pte_va：第pdeno个页表的第pteno个页表项
va = base + pdeno * PAGE_SIZE + pteno * 4B
va = base | pdeno << 12 | pteno << 2
pde_va：页目录的第pdeno个页表项
页目录自己就是自映射区里的第PDX(base)张页表
va = base + PDX(base) * PAGE_SIZE + pdeno * 4B
va = base | PDX(base) << 12 | pdeno << 2

自映射的解除

判断页表项是否有效：(pgdir[i]&PTE_V) != 0
判断该页表项是否是自映射的页目录项：PTE_ADDR(pgdir[i])=PADDR(pgdir)
得到base：base = i << 22(建立的时候i=PDX(base))(注意base要用u_long，不然可能超范围引发不可预知的bug等等)
清0：pgdir[i] = 0
删去这4MB对应的所有TLB项：

1
2
3
for (u_long va = base; va < base + PDMAP; va += PAGE_SIZE) {
    tlb_invalidate(asid, va);
}

总结

Lab2 的难点主要集中在地址转换、页表结构、物理页状态维护和 TLB 重填这几个方面。完成实验后，我对“虚拟地址如何通过页表和 TLB 转换成物理地址”这一过程有了更完整的理解，也更加清楚操作系统内存管理中各个模块之间的联系。

实验体会

相当难受。
lab2课下看指导书看得非常艰难。但是真正去填空的话还是非常简单的。
lab2-exam也非常简单。基本上有一点数据结构知识理解链表的基本操作、会调用相关的宏就行了。
lab2-extra喜得30分。本来我以为自己已经完全理解自映射了，但当真正让我去计算地址和实现映射的时候还是一脸懵逼。尤其是实现映射，根本不知道要怎么映射，往哪映射，通过什么方式映射。说明对自映射的实现机制的理解还是不够深刻(大哭)。

好了课下也把extra给完整补完了，感觉也没那么难。但是如果不给示例不告诉我建立映射的方法的话，自己还是应该凭空想不出来的(感谢ai)。

原创说明

参考了往届三位学长学姐的博客。感谢他们的精心整理和付出。
https://hyggge.github.io
https://yanna-zy.github.io
https://demiurge-zby.github.io