数据结构

这里讲的内容主要是queue.h里的内容。

值得注意的主要是pp_link，在pp_link里有一个struct Page ** le_prev，这个指针指向的是前一个结点的le_next，这样就可以通过后一个结点，修改前一个结点的连接值。

示意图如下：

知道了队列的结构，再结合已有的代码，想必你就能比较简单的完成queue.h的内容了。

一点注意事项

1、所有带env的东西，似乎都不是这一个lab需要理解的，所以就不说了，我写的时候也不太懂，以后lab如果弄明白了在回来补充(如果我还记得)

2、GitHub上有一些前辈留下的代码可供参考，大家可以观摩学习。

3、咱们的指导书是从低端向上，基础函数讲完在将上层的，我是从main函数开始写，遇到一个函数写一个函数，从顶端向下来说明的，希望能从一个不同的角度展现lab2的构建。这其中有一些函数，我觉得比较简单，或者和已经写过的函数有异曲同工的关系，就不再多笔了。

函数串讲

关于变量之间的转换

对于本实验，我们所有的虚拟地址都是内核虚拟地址，不经过mmu转换，物理地址直接通过虚拟地址首位变为0就能得到。由于虚拟页和物理页式线性对应的，我们把所有虚拟页面的指针Page*，按照映射顺序排成一个数组pages，就可以根据Page* p1在pages中的位置找到对应的虚拟地址，再把虚拟地址转化为物理地址。Page组成的链表用来记录没有使用的页面。

---

页表构建

1、

​ mips_detect_init中初始化内存大小等数据

2、

​ mips_vm_init中首先给页目录分配4KB内存，指针为pgdir。然后创建一个数组struct Page* pages，给它分配npage个元素大小的内存。然后调用boot_map_segment(pgdir, UPAGES, n, PADDR(pages)，PTE_R);建立映射关系。

​ 这里我有一个问题也不太理解，就是为什么用UPAGES当做参数。如果以后找到了答案，我再补上。

3、

​ 在boot_map_segment中核心函数是boot_pgdir_walk。这个函数创建（create==1的话）并返回va对应的页表项地址。在这个函数中，pgdir是页表入口，va是目标虚拟地址。pgdir_entryp是pgdir+(va >> 22)，也就是对应va的页表项。

​ 然后检查*(pgdir_entryp)中的权限位，如果不存在可以创建新的页表，也就是先用alloc分配一个页面的内存，然后把这个页面的虚拟地址赋给pgtable，物理地址（用PADDR得到的）和权限位存入*(pgdir_entryp)中。如果存在，就直接把页面的虚拟地址（根据物理地址用KADDR得到）赋给pgtable。

​ 这样一来pgtable就是va对应的页表的基地址，然后把页表项的地址赋给pgtable_entry，pgtable_entry=pgtable + (va>>12)。

​ 最后返回pgtable_entry

4、

​ 知道了boot_pgdir_walk，再回来看boot_map_segment。

​ 对虚拟地址[va, va+size)中每4KB内存，都会调用pgtable_entry=boot_pgdir_walk(pgdir,va_temp,1)。这样每4KB内存就获得了一个页表，pgtable_entry对应页表项地址。然后由于pa，va是线性映射，应该向页表中写入的地址是pa+i。再设置好权限位。

​ 最后，在向页目录项中设置权限位（页目录项内容在boot_pgdir_walk中已经设置好了）。

5、

​ 结束了mips_vm_init，就到了最后的page_init()了。

​ 首先调用了LIST_INIT初始化了一个链表，这个链表用来储存空页面。

​ 用pages储存所有页面，由于页和内存线性映射，因此可以用一个循环把已经分配的页面（freemem之下的）都做标记。然后把没有分配的页面放到list中去。

至此我们就完成页表系统的建立。

---

页分配

主要实现是page_alloc，注意这个函数增加

1、

​ 从free_page_list头部获得一个空页表。

2、

​ 得到这个空页表的虚拟地址，主要是通过page2kva(struct Page **pp)。这里需要介绍一下通过Page *指针获得对应其他内容的过程

page2ppn

​ 计算出pp是pages里面是第几个

page2pa

​ 由于page和内存线性对应，且内存都不经过mmu，直接左移12位就拿到了物理地址。

pa2page

​ 截取高22位作为索引，在pages中找到对应的页

page2kva

​ 先根据pp得到物理地址，然后最高位置1。

…………

3、

​ 总之，拿到ppage_temp对应的虚拟地址后，把这部分内存清零，然后从free_page_list中移除这个页，最后把结果赋给*pp

---

页插入

page_insert

1、

​ 调用pgdir_walk(pgdir, va, 0, &pgtable_entry)，这个函数和boot_page_walk有点像，功能也是一样，都是根据虚拟地址分配页面并返回页表项。但是它是用于二级页表已经建立完成之后的内存分配函数。

​ 首先先获得va对应的页目录项pgdir_entryp=pgdir+PDX(va)。

​ 如果pgdir_entryp不存在且允许创建新的页面，就用page_alloc给ppage分配一个新的页，并且把这个页的引用次数+1，把物理地址写入页目录项并设置权限位，把ppage的虚拟地址写入页表基址pgtable中。

​ 设置*ppte为页表项地址。

2、

​ 经过上一步，pgtable_entry储存了va对应的页表项地址。如果页表项内容对应的就是pp这个物理页那么更新tlb内容，把权限更新一下，就可以返回了。

​ 如果不是pp这个物理页，进入下一步

3、

​ 既然*pgtable_entry内容不是pp这个物理页面，那就要先调用page_remove(pgdir, va)。

​ 这个函数里面调用了page_lookup，用来获得va对应的页面指针ppage和页表项指针pagetable_entry。

​ 然后让ppage的引用-1，如果可能就释放它。然后先把对应的页表项清零，接着更新了tlb，也就是把对应的tlb清零了(更新策略后面说)，返回

4、

​ 调用完page_remove，回到了page_insert，下一步是更新tlb，更新tlb用的就是函数tlb_invalidate()，而这个函数里面主要函数是tlb_out()。

​ tlb_out是一个汇编函数，进入tlb_out，首先就是设置协处理器。关于协处理器的知识，可以参照See MIPS Run Linux这本书TLB章节。前两个指令读取并写入cp0的$10，其中$a0是进入函数时的参数。

​ 然后的tlbp指令，这个指令会把检查TLB，如果TLB中有项和EntryHi寄存器匹配，就把Index寄存器设置为对应的项，如果没有匹配的项，就把Index最高位设置为1（也就是变成负数）。这里要注意的是，TLB内部是流水线式的，遍历全部的TLB需要一定时间，如果tlbp后直接读取，就可能在Index设置好之前就读出数据，所以必须添加足够的指令把它和tlbwi隔开。

​ 接下来我们读取Index的值，如果小于零，显然没找到，那就跳转到NOFOUND，恢复遍历之前的状况，跳转回之前函数。

​ 如果找到了，那就写入TLB，tlbwi把ENTRYHI和ENTRYLO0写入Index所指的项，在这里，就是把这一项清零了。

​ 最后我们还是会进入NOFOUND，把一开始ENTRYHI数值重新输入回去，恢复现场，跳转回去。

​ 到这里，tlb_out()所做的所有工作就都完成了

5、

​ 好了，了解了tlb_out()，我们回到tlb_invalidata()。

​ 这个函数就是用tlb_out()把va对应的tlb项清空

6、

​ 了解了tlb_invalidata，我们再往前回到page_insert。

​ 把tlb清空后，我们用pgdir_walk重新获得va对应的页表项，并且也把页表项内容设置为pp对应的物理地址，再设定权限位。

注意

​ 这里tlb只清空不写入，所以就很恶心，一旦虚拟地址在tlb中被清空过一次，就再也向里面写入了，因为如果写入，会产生tlb缺失，在这个lab是没法处理的，只能不断循环，需要有重写机制才能再次使用。

结语

这个东西时我在做lab2的时候写的，还是希望能帮到学弟学妹，但是计算机这个东西很多时候你看再多的东西也不如自己真正做一遍理解的通透，我的内容可以参考，但是千万别自己不动手，一定要自己亲自去做一下。

如果我写的有疏漏，希望能帮忙指出，不胜感激。

另外如果有什么问题，也可以问我，我会在力所能及的范围内回复。