BUAA-OS-Lab2

字数统计: 5.1k阅读时长: 18 min

 2022/04/14 

写在前面：

以下是在整个lab2从学习到理解的过程中，和朋友遇到的相同困惑和思考讨论后给出的答案：

c语言写代码时，只能*内核态下的虚拟地址。不能*物理地址。
在lab2中不能*用户态的虚拟地址。

在c语言中指针面向的是cpu，所以只能 *虚拟地址。寄存器中如pc也是虚拟地址。

所以页表项的PTE_ADDR是物理地址，不能*物理地址。要*KADDR(PTE_ADDR(物理地址))。

kseg1和kuseg都是虚拟地址，但是在Lab2中只能*kseg1区域的虚拟地址。原因是：MOS 中，通过页表进行地址变换时，硬件只会查询TLB，如果查找失败，就会触发 TLB 中断，对应的异常中断处理就会对 TLB 进行重填，才能完成kuseg的虚拟地址通过二级页表访问物理地址。然而，lab2 里面没有开启tlb中断这个异常处理的功能，因此在lab2中不能*kuseg的用户态虚拟地址，比如UPAGES、UENVS。

在lab3的init/init.c中开启了trap_init();中断处理后，此时tlb中断正常响应，就可以*kuseg的用户态虚拟地址了。

在编写操作系统的c代码时，变量分别存放在哪部分物理内存？page_alloc() 申请的物理页面用来存什么？

代码段、全局变量和静态变量在编译阶段被确定，链接时被链入0x8001 0000向上这部分物理内存。

临时变量在内核栈区，被存放在0x8040 0000向下8*BY2PG这部分物理内存。

申请物理页面的用途：lab3用于给新进程申请页目录、给内核进程加载外部二进制elf文件并执行；lab4用于为用户进程申请用户栈、duppage()时为COW复制的页表申请物理空间；lab5在进程内存放文件内容、lab6用于给用户进程加载外部二进制elf文件来执行命令。

申请的页面存放在0x8040 0000向上这部分物理内存

在建立两级页表的映射机制时，虚拟地址、物理地址、（页表项）指针、（页表项）指针存放的数据是什么关系？

页目录项和页表项：存储于物理内存中某个物理地址中。KADDR(物理地址)就是存储页目录项和页表项的虚拟地址（位于kseg0），这个虚拟地址是页表项指针。使用*页表项指针（kseg0的虚拟地址）可以获取到这个虚拟地址对应的物理内存中的数据（页表项）。

对于获取到的页表项数据，PTE_ADDR(页表项)得到的是物理页的基地址。PTE_ADDR(页目录项)得到的物理页是二级页表的物理页基地址。二级页表项指针pte = KADDR(PTE_ADDR(页目录项))。访存二级页表项数据*pte 。PTE_ADDR（二级页表项）得到的物理页是内存数据页的物理页基地址。内存数据指针同理KADDR(PTE_ADDR(二级页表项))，*得到要访存的虚拟地址的数据。

要访存的虚拟地址va的不同段，用于*时提供偏移，包括页目录项在页目录的偏移PDX(va)，页表项在二级页表的偏移PTX(va)，数据在物理页面（等于在虚拟页面）的偏移offset(va)。

MOS编写函数时，为了扩展性、代码复用性，在函数的传入参数上的两个设计：

传入0或者1的标志位：例如pgdir_walk()函数的create参数，用于标志寻找二级页表项时是否创建二级页表。

传入指针的指针，用作返回值：例如pgdir_walk()函数的**ppte参数，用于底层函数pgdir_walk() 传给上层调用者二级页表项地址。

alloc() 和page_alloc()

boot_pgdir_walk() 和pgdir_walk()

前后两个相似功能函数的区别？

物理内存管理：页式管理的思想

在mips_vm_init()时，才进行了pages物理页面结构体的内存初始化。所以才能进行page_init() 页式内存管理的初始化。

page_alloc() 和pgdir_walk() 页式内存管理机制。所以在mips_vm_init()时需要使用alloc() 和boot_*() 来初始化物理内存。

一些在Lab2为固定值，但是还存在于函数声明的参数：

参数pgdir在pmap.c中全是使用的内核页目录地址boot_pgdir固定值：在后续用户进程使用pmap.c的函数时，参数pgdir会传入进程的页目录基地址，不再是内核页目录地址。

align：BY2PG。在mips_vm_init()，为了申请的时候页对齐，便h后续于物理内存的管理，页式管理，按页分配回收。

一、操作系统启动时的内存初始化过程

mips_vm_init()

作用：初始化内核页目录、Page结构体数组、env结构体数组的内存空间

alloc

static void *alloc(u_int n, u_int align, int clear)

作用：建立页式管理机制前，初始化内存时标记已使用的内存
流程：修改freemem全局变量，类似向上移动移动剩余物理空间的栈顶指针。如果clear=1，同时清空所对应的物理内存。

boot_map_segment

void boot_map_segment(Pde *pgdir, u_long va, u_long size, u_long pa, int perm)

作用：把以va为起始，长度为size的这一范围内的虚拟地址，映射到起始地址为pa的这一段物理地址
如何实现页表映射：建立从va到pa的映射，也就是boot_map_segment()关键的代码：在va所对应的页表项中写入pa的物理页框号ppn以及权限位。
```
*pgtable_entry = PTE_ADDR(pa + i) | (perm | PTE_V);
```
- pa 的物理页框号ppn : PTE_ADDR(pa + i)
- 权限位： (perm | PTE_V)
- va 所对应的页表项 : *pgtable_entry
  - 如何获取页表项地址 (指针) pgtable_entry ：boot_pgdir_walk的返回值
```
pgtable_entry = boot_pgdir_walk(pgdir, va + i, 1);
```

boot_pgdir_walk

static Pte *boot_pgdir_walk(Pde *pgdir, u_long va, int create)

作用：
- 返回值作为页表项地址 (指针) pgtable_entry
- 如果页目录项的权限位为0，表示此页目录项保存的二级页表的物理地址为空，即所对的二级页表未申请物理内存。此时如果传入参数create位为1，则alloc()出va所在二级页表的物理内存地址，写入页目录项；如果传入参数create位为0，表示boot_pgdir_walk()此时只检查二级页表是否已申请物理内存。如果已申请，正常返回页表项地址。否则返回0
流程：如何找到va所对的页表项地址
- 计算页目录项的虚拟地址：pgdir_entryp = pgdir + PDX(va);
- 判断页目录项的有效性：if (!((*pgdir_entryp) & PTE_V))
  - 为空：create位为1，则alloc()出va所在二级页表的物理内存地址，写入页目录项；create位为0，返回0.
- 把页目录项PTE_ADDR存储的的二级页表物理地址，通过KADDR宏转换成kseg0的虚拟地址，得到二级页表基地址：pgtable = (Pte *) KADDR(PTE_ADDR(*pgdir_entryp));
- 计算va所对应的二级页表项的虚拟地址：pgtable_entry = pgtable + PTX(va);
- 返回va所对应的二级页表项的虚拟地址

page_init

作用：
- 建立页式内存管理机制，进行物理内存的管理。
- 一个物理页面对应一个page结构体，物理内存管理主要是修改page结构体数组的信息
流程：
- 从pages（第一个page结构体地址）开始，到freemem的所对的页面的page结构体，所有page结构体的pp_ref记为1。表示被使用次数为1.
- 剩下的所有空闲结构体的pp_ref记为0，并插入空闲结构体链表page_free_list。

二、页式内存管理机制建立后，为后续lab提供的也是内存管理接口

返回值均为函数执行是否成功。真正的返回值靠传入指针的指针返回给上层函数。

page_alloc() vs alloc()

int page_alloc(struct Page **pp)

不再使用freemem标记占用内存，而是使用页式内存管理模式，即使用空闲结构体链表page_free_list的删除和重新插入管理空闲页面。
传入一个指针的指针pp，用于修改指针的内容，也就是给*pp写入返回分配的物理页面所对的结构体指针。

pgdir_walk() vs boot_pgdir_walk()

int pgdir_walk(Pde *pgdir, u_long va, int create, Pte **ppte)

需要使用page_alloc()为二级页表申请物理内存空间，不要忘记 ppage->pp_ref++

page_insert() vs boot_map_segment

int page_insert(Pde *pgdir, struct Page *pp, u_long va, u_int perm)

作用：
- 把物理页pp映射到虚拟地址va
流程：
- pgdir_walk() 找va的二级页表项和物理地址是否存在，create=0
  - 如果存在：
    - va之前映射到的旧物理页面不是pp，pa2page(*pgtable_entry) != pp：取消va对旧物理页面的映射，page_remove(pgdir, va)
    - va之前映射到的旧物理页面是pp：更新二级页表项的perm，所以需要tlb_invalidate(pgdir, va);清空旧的TLB，返回。
- 需要对二级页表项修改PTE_ADDR，所以要tlb_invalidate(pgdir, va);清空旧的TLB
- 找到二级页表项的地址，pgdir_walk(pgdir, va, 1, &pgtable_entry)，如果不存在，此时需要创建
- 二级页表项填入ppn和perm，物理页pp的pp_ref++

page_lookup

struct Page * page_lookup(Pde *pgdir, u_long va, Pte **ppte)

检查二级页表项是否存在：pgdir_walk(pgdir, va, 0, &pte);，不存在返回0
填入二级页表项地址 *ppte = pte;
返回va物理页面结构体 return pa2page(*pte);

三、实验思考题

Thinking 2.1

请你根据上述说明，回答问题：在我们编写的 C 程序中，指针变量中存储的地址是虚拟地址还是物理地址？MIPS 汇编程序中 lw, sw 使用的是虚拟地址还是物理地址？

指针变量中存储的地址是虚拟地址;MIPS 汇编程序中 lw, sw 使用的是物理地址。

Thinking 2.2

请从可重用性的角度，阐述用宏来实现链表的好处。

各类结构体都可以使用queue.h的宏简化代码量：
- 一开始写Exercise2.2的时候没有明白field字段设置的意义，觉得传入了elm参数以后，field应该是作为elm的成员变量名，不应该作为可变参数传入，显得有点多此一举，忘记了宏定义除了可以替换成实参，还可以做字符串字面量的替换。
- 写到2.3才意识到field不是变量参数，而是pp_link这个字符串。
- 后来思考之所以在queue.h的宏里面这样定义，应该是因为这里的宏并不止服务于Page，所以从工程角度来看，field仍然属于一种变量，field的设置提高了宏的可重用性，因为可以兼顾所有结构体的所有成员变量名。
复杂宏(如LIST_INSERT_TAIL、LIST_INSERT_BEFORE)大量使用简单宏(如LIST_FIRST、LIST_NEXT)，可重用性强
可读性强，简化代码量，易于维护

Thinking 2.5

请阅读上面有关 R3000-TLB 的叙述，从虚拟内存的实现角度，阐述 ASID 的必要性

由于多线程系统中不同进程中，相同的虚拟地址各自占用不同的物理地址空间，所以同一虚拟地址通常映射到不同的物理地址。因此TLB中装着不同进程的页表项，ASID用于区别不同进程的页表项。没有ASID机制的情况下每次进程切换需要地址空间切换的时候都需要清空TLB。

请阅读《IDT R30xx Family Software Reference Manual》的 Chapter 6，结合 ASID 段的位数，说明 R3000 中可容纳不同的地址空间的最大数量。

ASID6位，容纳64个不同进程。

Thinking 2.6

请用一句话概括 tlb_invalidate 的作用

实现删除特定虚拟地址的映射，每当页表被修改，就需要调用该函数以保证下次访问该虚拟地址时诱发 TLB 重填以保证访存的正确性

逐行解释 tlb_out 中的汇编代码

/* Exercise 2.10 */
LEAF(tlb_out)
//1: j 1b
nop
    mfc0    k1,CP0_ENTRYHI
  //把当前VPN和ASID存储到$k1，用于函数结束时恢复CP0_ENTRYHI
    mtc0    a0,CP0_ENTRYHI
  //把调用函数时传入的VPN和ASID写进CP0_ENTRYHI
    nop
  nop
    tlbp
  //根据 EntryHi 中的 Key（包含 VPN 与 ASID），查找 TLB 中与之对应的表项，并将表项的索引存入 Index 寄存器（若未找到匹配项，则Index最高位被置 1）
  nop
    nop
    nop
    nop
    nop
    mfc0    k0,CP0_INDEX
    bltz    k0,NOFOUND
  //如果TLB中保存了此VPN 与 ASID对应的表项，那么把EntryHi 与 EntryLo 的值写为0，即清空此表项，用于触发TLB缺失，重新装入
    nop
    mtc0    zero,CP0_ENTRYHI
    mtc0    zero,CP0_ENTRYLO0
    nop
    tlbwi
NOFOUND:
    mtc0    k1,CP0_ENTRYHI
  //$k1保存的原VPN和ASID恢复到CP0_ENTRYHI
    
    j    ra
    nop
END(tlb_out)

Thinking 2.7

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

Thinking 2.8

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

X86 体系结构中的内存管理机制

通过分段将逻辑地址转换为线性地址，通过分页将线性地址转换为物理地址。
逻辑地址由两部分构成，一部分是段选择器，一部分是偏移。
段选择符存放在段寄存器中，如CS（存放代码段选择符）、SS（存放堆栈段选择符）、DS（存放数据段选择符）和ES、FS、GS（一般也用来存放数据段选择符）等；
偏移与对应段描述符中的基地址相加就是线性地址。
操作系统创建全局描述符表和提供逻辑地址，之后的分段操作x86的CPU会自动完成，并找到对应的线性地址。
从线性地址到物理地址的转换是CPU自动完成的，转化时使用的Page Directory和Page Table等需要操作系统提供。

X86 和 MIPS 在内存管理上的区别

TLB不命中：
- MIPS触发TLB缺失和充填，然后CPU重新访问TLB
- x86硬件MMU索引获得页框号，直接输出物理地址，MMU充填TLB加快下次访问速度
分页方式不同：
- 一种MIPS系统内部只有一种分页方式
- x86的CPU支持三种分页模式
逻辑地址不同：
- MIPS地址空间32位
- x86支持64位逻辑地址，同时提供转换为32位定址选项
段页式的不同：
- MIPS同时包含了段和段页式两种地址使用方式
- 在x86架构的保护模式下的内存管理中，分段是强制的，并不能关闭，而分页是可选的；

四、实验难点

程序空间和物理内存的映射理解：

对于Page结构体数组的理解：

虚拟空间内，存储在kseg0(pages)和kuseg(UPAGES),映射到相同物理地址。
- kseg0的pages和物理地址一一对应，va高位置0即可得到pa
- kuseg的UPAGES需要建立页目录和物理地址的映射
Page结构体插入page_free_list的顺序不需要按地支顺序。差别仅在于分配物理页面时提供的物理地址不同。保证Page所对物理页面为空即可

没有分清虚拟地址和物理地址

MOS中的页表和页表项在虚拟内存中也占有一片空间。我们模拟的内存管理都是在CPU环境下模拟MMU的映射过程，所以涉及的代码均为操作虚拟地址，也就是得到一个需要访存的程序地址，通过MMU读取页目录地址，转换成页表的虚拟地址，返回给CPU，完成访存。

pgdir_walk函数中，对应的二级页表不存在则会使用 page_alloc 函数分配一页物理内存用于存放。pp_ref 对应这一页物理内存被引用的次数，它等于有多少虚拟页映射到该物理页。所以此时pgdir_walk函数create的时候，pp_ref需要+1.

对于PPN和PTE_ADDR一开始没有分清楚

PPN得到虚页号，PTE_ADDR可以得到页表的物理地址。PTE_ADDR>>12=PPN

链表相关的指针、结构体、宏定义等C语言知识：

由于野指针导致了出现死循环

测试时发现不停的跳转到main函数里，是取了野指针的问题。后来排查发现是出现了*页目录项的问题。pgdir_walk返回的是页表项的地址，所以不需要*页目录项，而是需要把页目录项的物理地址转换成虚拟地址。

对于链表初始化重复修改了多次才成功

LIST_INIT(&page_free_list);中，page_free_list是Page_list结构体变量，链表宏需要的参数均为Page_list结构体指针，所以需要传入&page_free_list地址
page_init()函数中，不需要LIST_HEAD(Page_list,Page) page_free_list;的定义。结构体已经定义过。

双向链表的结构体结构理解不清晰

prev是struct Page**,保存next的地址；next是struct Page *,保存结构体的地址；
作用是remove节点时避免遍历双向链表

移位运算符的bug

移位运算符的优先级低于加号，需要加括号
右移后低位截断。如((*pte)>>12)&0xfff,避免出现算数右移的情况

五、体会与感想

测试代码写的很好，非常全面地测试了内存管理模块，把原来的黑盒评测变成了白盒，为debug带来了很大的方便！
回归到了最朴素的printf调试法。由于gxemul的单步调试只能看内存的存取情况，所以想观察函数和地址的行为只能用printf的方法进行单步调试。虽然看过gxemul的断点调试教程，但是比较抽象，希望如果有可能的话助教能结合lab2的具体代码给予结合gxemul的调试示例，作为第二种debug方法
虚拟内存的函数经常多次调用，返回值类型多，函数间的调用关系比较复杂。我选择在函数的入口、出口、分支判断条件的地方都加入printf语句，配合check()代码可以显式地看到内存分配的过程，加强了对内存管理的理解

六、指导书反馈

Exercise2.8给的函数中，pgdir_walk函数中，对应的二级页表不存在则会使用 page_alloc 函数分配一页物理内存用于存放。pp_ref 对应这一页物理内存被引用的次数，它等于有多少虚拟页映射到该物理页。所以此时pgdir_walk函数create的时候，pp_ref需要+1.
请在lab2就像lab3强调结构体必须为了评测而保证倒序插入一样，强调page结构体必须倒序插入。由于一开始在lab2顺序插入的page结构体，虽然在Lab2课上的题面有强调倒序，在课上评测我也按倒序做了修改。但是lab3的评测由于没有特殊说明，我没有再修改page结构体的顺序，导致lab3课下评测只过了8个点，误以为是lab3的bug导致浪费大量时间才定位到pmap.c
lab2的mmu.h增加的KADDR(pa)宏，由于没有对传入的**pa取(u_long)**，且此转换宏的逻辑是pa+ULIM也就是pa+0x8000_0000，导致如果传入指针型的变量就无法高位置1.建议从Lab2到后续lab对mmu.h的KADDR(pa)做修正
多级页表自映射可以强调一下自映射的页目录在页目录、所有页表、虚拟页框的偏移offset是一致的
可以在教程网站中增加一些mmu.h和pmap.h地址转换宏的练习题，增加对头文件的理解
增加流程图解

Next Post

BUAA-OS-Lab3
Previous Post

BUAA-OO-Unit1