文章目录：
这章的难度断崖式上升，看不懂一点，还没有梳理，下面只是我的一些“中文版注释”等辅助内容。
AC代码：lab2.zip
todo：
- 各种宏分类梳理
- 整个Lab的逻辑
- 各种函数的梳理
- 各种文件的中文注释翻译版
各种头文件/宏定义
mmu.h
#ifndef _MMU_H_
#define _MMU_H_ // 防止头文件重复包含
/*
* 第一部分：页表 / 页目录相关定义
*/
// ASID（地址空间标识符）的最大数量
#define NASID 256
// 页面大小：4KB
#define PAGE_SIZE 4096
// 单个页表项映射的字节数：4KB
#define PTMAP PAGE_SIZE
// 单个页目录项映射的字节数：4MB
#define PDMAP (4 * 1024 * 1024)
// 页内偏移所占的位数：12 位（2^12 = 4096）
#define PGSHIFT 12
// 页目录索引对应的位移：22 位（2^22 = 4MB）
#define PDSHIFT 22 // log2(PDMAP)
// 从虚拟地址 va 中取出页目录索引（高 10 位）
#define PDX(va) ((((u_long)(va)) >> PDSHIFT) & 0x03FF)
// 从虚拟地址 va 中取出页表索引（中间 10 位）
#define PTX(va) ((((u_long)(va)) >> PGSHIFT) & 0x03FF)
// 从页表项/页目录项中取出物理页帧地址（清除低 12 位标志位）
#define PTE_ADDR(pte) (((u_long)(pte)) & ~0xFFF)
// 从页表项/页目录项中取出低 12 位标志位
#define PTE_FLAGS(pte) (((u_long)(pte)) & 0xFFF)
// 地址中的页号字段
// 物理地址对应的物理页号（Physical Page Number）
#define PPN(pa) (((u_long)(pa)) >> PGSHIFT)
// 虚拟地址对应的虚拟页号（Virtual Page Number）
#define VPN(va) (((u_long)(va)) >> PGSHIFT)
// 页表项 / 页目录项中的硬件标志位从第 6 位开始
#define PTE_HARDFLAG_SHIFT 6
/*
* TLB 的 EntryLo 和内存中页表项 PTE 的位布局关系：
* entrylo.value == pte.value >> 6
*
* 页表项 PTE 可以理解为：
* [31:12] 物理页帧号 PFN（20 位）
* [11:6] 硬件标志位
* C: Cache 属性位
* D: Dirty / 可写位
* V: Valid / 有效位
* G: Global / 全局位
* [5:0] 软件标志位
*/
// 全局位 G：如果 TLB 项设置了 G，则匹配时只看 VPN，不再检查 ASID
#define PTE_G (0x0001 << PTE_HARDFLAG_SHIFT)
// 有效位 V：如果为 0，则匹配到该项时会触发 TLB miss 异常（TLBL/TLBS）
#define PTE_V (0x0002 << PTE_HARDFLAG_SHIFT)
// 脏位 D（实际上更像“可写位”）：
// 为 1 时允许写；为 0 时写该页会触发 TLB Mod 异常
#define PTE_D (0x0004 << PTE_HARDFLAG_SHIFT)
// Cache 一致性属性：可缓存
#define PTE_C_CACHEABLE (0x0018 << PTE_HARDFLAG_SHIFT)
// Cache 一致性属性：不可缓存
#define PTE_C_UNCACHEABLE (0x0010 << PTE_HARDFLAG_SHIFT)
// 写时复制标志（软件保留位，fork 时使用）
#define PTE_COW 0x0001
// 共享内存标志（软件保留位，fork 时使用）
#define PTE_LIBRARY 0x0002
// 内存段起始地址（32 位内核模式地址空间）
#define KUSEG 0x00000000U // 用户空间
#define KSEG0 0x80000000U // 内核直映射、可缓存
#define KSEG1 0xA0000000U // 内核直映射、不可缓存，常用于设备
#define KSEG2 0xC0000000U // 内核高地址映射区
/*
* 第二部分：本实验中的地址空间约定
*/
/*
* 4GB 虚拟地址空间布局如下：
*
* 4G -----------> +----------------------------+------------0x100000000
* | ... | kseg2
* KSEG2 -----> +----------------------------+------------0xc0000000
* | 设备区域 | kseg1
* KSEG1 -----> +----------------------------+------------0xa0000000
* | 无效内存 | /|\
* +----------------------------+----|-------物理内存上限
* | ... | kseg0
* KSTACKTOP-----> +----------------------------+----|-------0x80400000---末尾
* | 内核栈 | | KSTKSIZE /|\
* +----------------------------+----|------ |
* | 内核代码 | | PDMAP
* KERNBASE -----> +----------------------------+----|-------0x80020000 |
* | 异常入口 | \|/ \|/
* ULIM -----> +----------------------------+------------0x80000000-----
* | 用户只读页表 UVPT | PDMAP /|\
* UVPT -----> +----------------------------+------------0x7fc00000 |
* | pages 数组 | PDMAP |
* UPAGES -----> +----------------------------+------------0x7f800000 |
* | envs 数组 | PDMAP |
* UTOP,UENVS -----> +----------------------------+------------0x7f400000 |
* UXSTACKTOP -/ | 用户异常栈 | PTMAP |
* +----------------------------+------------0x7f3ff000 |
* | | PTMAP |
* USTACKTOP ----> +----------------------------+------------0x7f3fe000 |
* | 普通用户栈 | PTMAP |
* +----------------------------+------------0x7f3fd000 |
* | | |
* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ |
* . . |
* . . kuseg
* . . |
* |~~~~~~~~~~~~~~~~~~~~~~~~~~~~| |
* | | |
* UTEXT -----> +----------------------------+------------0x00400000 |
* | 为 COW 预留的页 | PTMAP |
* UCOW -----> +----------------------------+------------0x003ff000 |
* | 为临时映射预留 | PTMAP |
* UTEMP -----> +----------------------------+------------0x003fe000 |
* | 无效内存 | \|/
* 0 ---------> +----------------------------+----------------------------
*/
// 内核映像起始虚拟地址
#define KERNBASE 0x80020000
// 内核栈顶地址
#define KSTACKTOP (ULIM + PDMAP)
// 用户空间上限；用户态不能访问该地址及以上的空间
#define ULIM 0x80000000
// 用户只读页表映射区（Virtual Page Table）
#define UVPT (ULIM - PDMAP)
// 用户只读的物理页信息数组映射区
#define UPAGES (UVPT - PDMAP)
// 用户只读的 Env 数组映射区
#define UENVS (UPAGES - PDMAP)
// 用户地址空间顶部
#define UTOP UENVS
// 用户异常栈顶部
#define UXSTACKTOP UTOP
// 普通用户栈顶部（与异常栈之间留有一页空白）
#define USTACKTOP (UTOP - 2 * PTMAP)
// 用户程序正文起始地址
#define UTEXT PDMAP
// 为写时复制（COW）预留的一页
#define UCOW (UTEXT - PTMAP)
// 为临时映射预留的一页
#define UTEMP (UCOW - PTMAP)
#ifndef __ASSEMBLER__
/*
* 第三部分：辅助宏和函数
*/
#include <error.h>
#include <string.h>
#include <types.h>
extern u_long npage;
typedef u_long Pde;
typedef u_long Pte;
// 将内核虚拟地址转换成物理地址
#define PADDR(kva) \
({ \
u_long _a = (u_long)(kva); \
if (_a < ULIM) \
panic("PADDR called with invalid kva %08lx", _a); \
_a - ULIM; \
})
// 将物理地址转换成内核虚拟地址
#define KADDR(pa) \
({ \
u_long _ppn = PPN(pa); \
if (_ppn >= npage) { \
panic("KADDR called with invalid pa %08lx", (u_long)pa); \
} \
(pa) + ULIM; \
})
// 断言宏：条件不成立时触发 panic
#define assert(x) \
do { \
if (!(x)) { \
panic("assertion failed: %s", #x); \
} \
} while (0)
// 将指针/地址限制在不超过 ULIM 的范围内；如果超过则截断为 ULIM
#define TRUP(_p) \
({ \
typeof((_p)) __m_p = (_p); \
(u_int)__m_p > ULIM ? (typeof(_p))ULIM : __m_p; \
})
extern void tlb_out(u_int entryhi);
void tlb_invalidate(u_int asid, u_long va);
#endif // !__ASSEMBLER__
#endif // !_MMU_H_queue.h
位置include/queue.h，实现双向链表功能，定义了很多宏定义。指导书的一些对宏定义的解释说明（基本上都是要传指针进去的）：
| 作用 | 宏名 |
|---|---|
| 定义链表头结构体 | LIST_HEAD(name, type) |
| 定义链表节点中的链接字段 | LIST_ENTRY(type) |
| 判断链表是否为空 | LIST_EMPTY(head) |
| 获取链表第一个元素（重要） | LIST_FIRST(head) |
| 初始化链表 | LIST_INIT(head) |
| 获取当前元素的下一个元素（重要） | LIST_NEXT(elm, field) |
| 在某元素后插入新元素 | LIST_INSERT_AFTER(listelm, elm, field) |
| 在某元素前插入新元素 | LIST_INSERT_BEFORE(listelm, elm, field) |
| 在链表头部插入元素 | LIST_INSERT_HEAD(head, elm, field) |
| 删除某个元素 | LIST_REMOVE(elm, field) |
结构体定义
定义里面最重要的是LIST_ENTRY这个结构体定义，它负责链表的连接工作。
#define LIST_ENTRY(type) \
struct { \
struct type *le_next; /* 下一个元素 */ \
struct type **le_prev; /* 前一个位置中的 next 指针地址 */ \
}上面的链表只有前后节点，但是链表不能没有值，所以LIST_ENTRY并不是完整的链表元素结构体，他是链表元素的一部分（嵌套进去的，结构体中结构体），只负责链接工作，比如真正的链表元素结构体类似于下面这种：
struct Page {
int id;
LIST_ENTRY(Page) page_link; // 上面的宏定义
};上面例子里面的page_link即是后面很多宏定义所需的field字段，比如通过Page->page_link，我们可以拿到LIST_ENTRY这个结构体，故我们可以用Page->page_link.le_next获取当前元素的下一个元素指针。
宏定义特性
- 记住宏定义是把对应的定义在代码中直接替换成后面所有的内容。
- 每行写完之后加上
\，代表这个宏定义还没有结束。 - 使用
while{ } do(0)结构，防止宏定义解析到单行的if或者while之后被拆开，同时do(0)后面最好不加分号，真正代码里再加。 - 部分字段为了防止解析错误，最好加上括号，比如
(elm)，防止解析的时候被拆开，优先解析。有的部分不能加括号。
如何修改链表元素
链表里面每一个元素保存了下一个元素的指针next，同时还保存了上一个元素的next指针的指针prev（类型是指针的指针，指向的是next指针，而非元素）。
所以不管是修改/插入/删除元素，都只需要考虑修改四件事（删除的时候不用管与当前元素相关的两项，删了就好）。可以分为两类：
首先是当前和上一项的next，即当前元素对应的下一个元素指针le_next (LIST_NEXT(elm, field))、上一个元素对应的下一个元素指针le_next(LIST_NEXT(pre, field) (知道上一个元素的话) 或者 *elm->field.le_prev)
然后是当前和下一项的prev，以及当前元素下保存上一个元素next指针的指针(elm->field.le_prev )、下一个元素保存的上一个元素next指针的指针（nxt->field.le_prev (知道下一个元素的话) 或者 LIST_NEXT((elm), field)->field.le_prev）。
上面这段话第二天我自己都读不懂
下面是完整的中文注释版：
#ifndef _SYS_QUEUE_H_
#define _SYS_QUEUE_H_
/*
* 本文件定义了三种数据结构：链表（list）、尾队列（tail queue）和循环队列
* （circular queue）。
*
* 链表（list）的头部只有一个前向指针（如果用于哈希表头，也可以理解为一个前向
* 指针数组）。链表中的元素是双向链接的，因此删除任意元素时，不需要从头遍历整
* 条链表。新元素可以插入到某个已有元素之前、之后，或者直接插到链表头部。链表
* 一般只支持沿 next 方向进行正向遍历。
*
* 尾队列（tail queue）的头部包含两个指针：一个指向首元素，另一个用于快速定位
* 尾部。元素同样是双向链接的，因此删除任意元素时也不需要遍历。新元素可以插入
* 到某个已有元素之前、之后、头部或尾部。
*
* 循环队列（circular queue）的头部也包含两个指针，分别关联到首元素和尾元素。
* 元素同样是双向链接的，因此删除任意元素不需要遍历。新元素可以插入到某个已有
* 元素之前、之后、头部或尾部。循环队列既可以正向遍历，也可以反向遍历，但判断
* “是否到达末尾”的逻辑会更复杂。
*
* 更详细的用法可参考 queue(3) 手册页。
*/
/*
* LIST（链表）相关声明。
*/
/*
* LIST_HEAD(name, type) 用于定义一个“链表头结构体类型”。
* 这个头结构体里只有一个成员 lh_first，用来指向 type 类型链表的首元素。
*
* 典型写法：
* LIST_HEAD(HEADNAME, TYPE) head;
*
* 其中：
* - HEADNAME：要定义出来的链表头结构体名称
* - TYPE：链表中元素的类型名
*/
#define LIST_HEAD(name, type) \
struct name { \
struct type *lh_first; /* 指向链表首元素 */ \
}
/*
* 可将一个链表头变量初始化为 LIST_HEAD_INITIALIZER(head)，
* 使它表示一个空链表（常用于静态初始化）。
*/
#define LIST_HEAD_INITIALIZER(head) \
{ NULL }
/*
* LIST_ENTRY(type) 一般作为某个结构体中的一个字段出现，例如：
*
* LIST_ENTRY(Page) page_link;
*
* 它本质上是一个“链表项（链接信息）”，包含两个指针：
* - le_next：指向下一个元素
* - le_prev：指向“前一个位置里那个 next 指针”的地址
*
* 注意：
* le_prev 不是“前驱结点指针”，而是“指针的指针”。
* 这样删除当前元素时，可以直接执行：
* *le_prev = le_next;
* 从而把前一个位置对当前元素的引用改成指向下一个元素，
* 不需要显式找到前驱结点。
*/
#define LIST_ENTRY(type) \
struct { \
struct type *le_next; /* 下一个元素 */ \
struct type **le_prev; /* 前一个位置中的 next 指针地址 */ \
}
/*
* LIST 相关操作宏。
*/
/*
* 判断 head 指向的链表是否为空。
* 若首元素指针为 NULL，则说明链表为空。
*/
#define LIST_EMPTY(head) ((head)->lh_first == NULL)
/*
* 返回 head 对应链表的首元素。
*/
#define LIST_FIRST(head) ((head)->lh_first)
/*
* 遍历 head 对应链表中的所有元素。
* 遍历过程中：
* - 当前访问到的元素赋给变量 var
* - field 是结构体中用于挂链的 LIST_ENTRY(type) 字段名
*/
#define LIST_FOREACH(var, head, field) \
for ((var) = LIST_FIRST((head)); (var); (var) = LIST_NEXT((var), field))
/*
* 将 head 对应的链表初始化为空链表。
*/
#define LIST_INIT(head) \
do { \
LIST_FIRST((head)) = NULL; \
} while (0)
/*
* 将元素 elm 插入到已经在链表中的元素 listelm 之后。
* field 为链表链接字段名。
*
* 可以按下面四步来理解：
* 1. 先让 elm->next 指向 listelm 原来的后继；
* 2. 如果 listelm 原来的后继不为空，就把那个后继的 le_prev 改成指向 elm 的 next；
* 3. 再让 listelm->next 指向 elm；
* 4. 最后把 elm->le_prev 设为 &listelm->next。
*/
#define LIST_INSERT_AFTER(listelm, elm, field) \
/* Exercise 2.2: Your code here. */ \
do { \
LIST_NEXT((elm), field) = LIST_NEXT((listelm), field); \
if ((LIST_NEXT((elm), field)) != NULL) \
LIST_NEXT((elm), field)->field.le_prev = &LIST_NEXT((elm), field); \
(elm)->field.le_prev = &LIST_NEXT((listelm), field); \
LIST_NEXT((listelm), field) = (elm); \
} while(0)
/*
* 将元素 elm 插入到已经在链表中的元素 listelm 之前。
* 由于 le_prev 保存的是“前一个位置中的 next 指针地址”，
* 所以这里不需要+显式找到前驱结点。
*/
#define LIST_INSERT_BEFORE(listelm, elm, field) \
do { \
(elm)->field.le_prev = (listelm)->field.le_prev; \
LIST_NEXT((elm), field) = (listelm); \
*(listelm)->field.le_prev = (elm); \
(listelm)->field.le_prev = &LIST_NEXT((elm), field); \
} while (0)
/*
* 将元素 elm 插入到 head 对应链表的头部，
* 插入后 elm 会成为新的首元素。
*/
#define LIST_INSERT_HEAD(head, elm, field) \
do { \
if ((LIST_NEXT((elm), field) = LIST_FIRST((head))) != NULL) \
LIST_FIRST((head))->field.le_prev = &LIST_NEXT((elm), field); \
LIST_FIRST((head)) = (elm); \
(elm)->field.le_prev = &LIST_FIRST((head)); \
} while (0)
/*
* 返回 elm 在对应链表中的下一个元素。
* 这里的 field 表示 elm 所在结构体中，用于挂链的那个 LIST_ENTRY(type) 字段名。
* 后面所有带 field 参数的 LIST 宏，field 的含义都相同。
*/
#define LIST_NEXT(elm, field) ((elm)->field.le_next)
/*
* 将元素 elm 从对应链表中删除。
* 删除时不需要遍历链表，因为 le_prev 已经记录了“前一个位置中的 next 指针地址”。
*/
#define LIST_REMOVE(elm, field) \
do { \
if (LIST_NEXT((elm), field) != NULL) \
LIST_NEXT((elm), field)->field.le_prev = (elm)->field.le_prev; \
*(elm)->field.le_prev = LIST_NEXT((elm), field); \
} while (0)
/*
* TAILQ（尾队列）相关定义。
*/
/*
* 尾队列头结构：
* - tqh_first：指向首元素
* - tqh_last：不是直接指向尾元素，而是指向“最后一个元素的 tqe_next 成员”的地址
*
* 当队列为空时：
* tqh_last == &tqh_first
*
* 这样的设计可以让尾插操作在 O(1) 时间完成。
*/
#define _TAILQ_HEAD(name, type, qual) \
struct name { \
qual type *tqh_first; /* 指向首元素 */ \
qual type *qual *tqh_last; /* 最后一个元素的 next 指针地址 */ \
}
#define TAILQ_HEAD(name, type) _TAILQ_HEAD(name, struct type, )
#define TAILQ_HEAD_INITIALIZER(head) \
{ NULL, &(head).tqh_first }
/*
* 尾队列元素中的链接字段：
* - tqe_next：指向下一个元素
* - tqe_prev：指向“前一个位置中的 next 指针”的地址
*/
#define _TAILQ_ENTRY(type, qual) \
struct { \
qual type *tqe_next; /* 下一个元素 */ \
qual type *qual *tqe_prev; /* 前一个位置中的 next 指针地址 */ \
}
#define TAILQ_ENTRY(type) _TAILQ_ENTRY(struct type, )
/*
* TAILQ 相关操作宏。
*/
#define TAILQ_INIT(head) \
do { \
(head)->tqh_first = NULL; \
(head)->tqh_last = &(head)->tqh_first; \
} while (/* 常量条件 */ 0)
#define TAILQ_INSERT_HEAD(head, elm, field) \
do { \
if (((elm)->field.tqe_next = (head)->tqh_first) != NULL) \
(head)->tqh_first->field.tqe_prev = &(elm)->field.tqe_next; \
else \
(head)->tqh_last = &(elm)->field.tqe_next; \
(head)->tqh_first = (elm); \
(elm)->field.tqe_prev = &(head)->tqh_first; \
} while (/* 常量条件 */ 0)
#define TAILQ_INSERT_TAIL(head, elm, field) \
do { \
(elm)->field.tqe_next = NULL; \
(elm)->field.tqe_prev = (head)->tqh_last; \
*(head)->tqh_last = (elm); \
(head)->tqh_last = &(elm)->field.tqe_next; \
} while (/* 常量条件 */ 0)
#define TAILQ_INSERT_AFTER(head, listelm, elm, field) \
do { \
if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL) \
(elm)->field.tqe_next->field.tqe_prev = &(elm)->field.tqe_next; \
else \
(head)->tqh_last = &(elm)->field.tqe_next; \
(listelm)->field.tqe_next = (elm); \
(elm)->field.tqe_prev = &(listelm)->field.tqe_next; \
} while (/* 常量条件 */ 0)
#define TAILQ_INSERT_BEFORE(listelm, elm, field) \
do { \
(elm)->field.tqe_prev = (listelm)->field.tqe_prev; \
(elm)->field.tqe_next = (listelm); \
*(listelm)->field.tqe_prev = (elm); \
(listelm)->field.tqe_prev = &(elm)->field.tqe_next; \
} while (/* 常量条件 */ 0)
#define TAILQ_REMOVE(head, elm, field) \
do { \
if (((elm)->field.tqe_next) != NULL) \
(elm)->field.tqe_next->field.tqe_prev = (elm)->field.tqe_prev; \
else \
(head)->tqh_last = (elm)->field.tqe_prev; \
*(elm)->field.tqe_prev = (elm)->field.tqe_next; \
} while (/* 常量条件 */ 0)
#define TAILQ_FOREACH(var, head, field) \
for ((var) = ((head)->tqh_first); (var); (var) = ((var)->field.tqe_next))
#define TAILQ_FOREACH_REVERSE(var, head, headname, field) \
for ((var) = (*(((struct headname *)((head)->tqh_last))->tqh_last)); (var); \
(var) = (*(((struct headname *)((var)->field.tqe_prev))->tqh_last)))
#define TAILQ_CONCAT(head1, head2, field) \
do { \
if (!TAILQ_EMPTY(head2)) { \
*(head1)->tqh_last = (head2)->tqh_first; \
(head2)->tqh_first->field.tqe_prev = (head1)->tqh_last; \
(head1)->tqh_last = (head2)->tqh_last; \
TAILQ_INIT((head2)); \
} \
} while (/* 常量条件 */ 0)
/*
* TAILQ 访问宏。
*/
#define TAILQ_EMPTY(head) ((head)->tqh_first == NULL)
#define TAILQ_FIRST(head) ((head)->tqh_first)
#define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next)
#define TAILQ_LAST(head, headname) (*(((struct headname *)((head)->tqh_last))->tqh_last))
#define TAILQ_PREV(elm, headname, field) (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
#endifpmap.h
#ifndef _PMAP_H_
#define _PMAP_H_
#include <mmu.h>
#include <printk.h>
#include <queue.h>
#include <types.h>
/* 当前正在使用的页目录指针（current page directory） */
extern Pde *cur_pgdir;
/* 定义一个名为 Page_list 的链表头类型，链表中的元素类型是 struct Page */
LIST_HEAD(Page_list, Page);
/* 定义 struct Page 在链表中的结点类型 */
typedef LIST_ENTRY(Page) Page_LIST_entry_t;
/* 表示一个物理页对应的元数据结构 */
struct Page {
Page_LIST_entry_t pp_link; /* 空闲页链表中的链接指针 */
// pp_ref 表示有多少个引用（通常是页表项）指向这个物理页。
// 这个引用计数只对通过 page_alloc 分配出来的页有效。
// 对于启动阶段通过 pmap.c 中的 "alloc" 分配的页，
// 它们的引用计数字段不保证有效。
u_short pp_ref; /* 当前物理页的引用计数 */
};
/* 指向全局 Page 数组的指针。
* pages[i] 对应第 i 个物理页的管理结构。 */
extern struct Page *pages;
/* 物理页空闲链表的表头 */
extern struct Page_list page_free_list;
/* 将 Page 结构指针转换为物理页号（physical page number, ppn）
* 本质上是计算该页在 pages 数组中的下标。 */
static inline u_long page2ppn(struct Page *pp) {
return pp - pages;
}
/* 将 Page 结构指针转换为对应物理页的物理地址 */
static inline u_long page2pa(struct Page *pp) {
return page2ppn(pp) << PGSHIFT;
}
/* 将物理地址转换为对应的 Page 结构指针
* 如果物理地址超出实际物理页范围，则触发 panic。 */
static inline struct Page *pa2page(u_long pa) {
if (PPN(pa) >= npage) {
panic("pa2page called with invalid pa: %x", pa);
}
return &pages[PPN(pa)];
}
/* 将 Page 结构指针转换为该页在内核中的虚拟地址 */
static inline u_long page2kva(struct Page *pp) {
return KADDR(page2pa(pp));
}
/* 根据页目录 pgdir，将虚拟地址 va 转换为物理地址
* 如果该虚拟地址没有建立映射，则返回 ~0。 */
static inline u_long va2pa(Pde *pgdir, u_long va) {
Pte *p;
/* 先找到 va 对应的页目录项 */
pgdir = &pgdir[PDX(va)];
/* 如果页目录项无效，说明没有页表，映射不存在 */
if (!(*pgdir & PTE_V)) {
return ~0;
}
/* 通过页目录项找到对应页表的内核虚拟地址 */
p = (Pte *)KADDR(PTE_ADDR(*pgdir));
/* 如果页表项无效，说明该虚拟地址未映射 */
if (!(p[PTX(va)] & PTE_V)) {
return ~0;
}
/* 返回页表项中记录的物理页基地址 */
return PTE_ADDR(p[PTX(va)]);
}
/* 检测物理内存大小，并初始化相关全局变量（如总页数 npage） */
void mips_detect_memory(u_int _memsize);
/* 初始化 MIPS 的虚拟内存管理相关数据结构 */
void mips_vm_init(void);
/* MIPS 平台总体初始化函数
* 一般会完成内存检测、页管理初始化等工作 */
void mips_init(u_int argc, char **argv, char **penv, u_int ram_low_size);
/* 初始化物理页管理结构：
* 包括设置 pages 数组和空闲页链表 page_free_list */
void page_init(void);
/* 启动阶段使用的简单物理内存分配器
* 分配 n 字节、按 align 对齐；
* 若 clear 非 0，则将分配到的内存清零。 */
void *alloc(u_int n, u_int align, int clear);
/* 从空闲页链表中分配一个物理页
* 成功时将结果写入 *pp，失败返回错误码。 */
int page_alloc(struct Page **pp);
/* 释放一个物理页，将其放回空闲页链表 */
void page_free(struct Page *pp);
/* 将物理页的引用计数减 1
* 若减到 0，则自动释放该页。 */
void page_decref(struct Page *pp);
/* 将物理页 pp 映射到页目录 pgdir 中的虚拟地址 va
* asid 是地址空间标识符，perm 是页权限。 */
int page_insert(Pde *pgdir, u_int asid, struct Page *pp, u_long va, u_int perm);
/* 查询虚拟地址 va 映射到哪个物理页
* 如果存在映射，返回对应的 Page 指针；
* 如果 ppte 不为空，还会把对应页表项地址存入 *ppte。 */
struct Page *page_lookup(Pde *pgdir, u_long va, Pte **ppte);
/* 删除虚拟地址 va 的页映射，并维护引用计数和 TLB */
void page_remove(Pde *pgdir, u_int asid, u_long va);
/* 再次声明全局 Page 数组指针（与前面的 extern 相同） */
extern struct Page *pages;
/* 检查物理内存管理模块是否正确工作的测试函数 */
void physical_memory_manage_check(void);
/* 检查页表映射、插入、删除等页管理功能是否正确的测试函数 */
void page_check(void);
#endif /* _PMAP_H_ */pmap.c
#include <bitops.h>
#include <env.h>
#include <malta.h>
#include <mmu.h>
#include <pmap.h>
#include <printk.h>
/* 这些变量由 mips_detect_memory(ram_low_size) 设置。 */
static u_long memsize; /* 最大物理地址 */
u_long npage; /* 内存总量（以页为单位） */
Pde *cur_pgdir;
struct Page *pages;
static u_long freemem;
struct Page_list page_free_list; /* 物理页空闲链表 */
/* 概述：
* 使用 bootloader 提供的 '_memsize' 来初始化 'memsize'，
* 并计算对应的 'npage' 值。
*/
void mips_detect_memory(u_int _memsize) {
/* 步骤 1：初始化 memsize。 */
memsize = _memsize;
/* 步骤 2：计算对应的 'npage' 值。 */
/* 练习 2.1：在此处填写代码。 */
npage = memsize >> PGSHIFT;
printk("Memory size: %lu KiB, number of pages: %lu\n", memsize / 1024, npage);
}
/* Lab 2 关键代码 "alloc" */
/* 概述：
以对齐方式 `align` 分配 `n` 字节的物理内存；如果 `clear` 被设置，则将所分配
的内存清零。
这个分配器只在建立虚拟内存系统时使用。
后置条件：
如果内存耗尽，应当 panic；否则返回分配到的这段内存地址。*/
void *alloc(u_int n, u_int align, int clear) {
extern char end[];
u_long alloced_mem;
/* 如果这是第一次调用，则初始化 `freemem`。
* 它表示链接器没有分配给任何内核代码或全局变量的第一个虚拟地址。 */
if (freemem == 0) {
freemem = (u_long)end; // end
}
/* 步骤 1：将 `freemem` 向上取整到满足对齐要求。 */
freemem = ROUND(freemem, align);
/* 步骤 2：保存当前 `freemem` 的值作为本次分配到的内存块起始地址。 */
alloced_mem = freemem;
/* 步骤 3：增加 `freemem`，记录这次分配。 */
freemem = freemem + n;
// 如果内存耗尽则触发 panic。
panic_on(PADDR(freemem) >= memsize);
/* 步骤 4：如果参数 `clear` 被设置，则将分配到的内存块清零。 */
if (clear) {
memset((void *)alloced_mem, 0, n);
}
/* 步骤 5：返回分配到的内存块。 */
return (void *)alloced_mem;
}
/* 关键代码 "alloc" 结束 */
/* 概述：
建立二级页表。
提示：
你可以在 include/mmu.h 中找到关于 `UPAGES` 和 `UENVS` 的更多细节。 */
void mips_vm_init() {
/* 为全局数组 `pages` 分配合适大小的物理内存，
* 以用于物理内存管理。然后，将虚拟地址 `UPAGES` 映射到之前为 `pages`
* 分配的物理地址。出于对齐考虑，在映射前应将内存大小向上取整。 */
pages = (struct Page *)alloc(npage * sizeof(struct Page), PAGE_SIZE, 1);
printk("to memory %x for struct Pages.\n", freemem);
printk("pmap.c:\t mips vm init success\n");
}
/* 概述：
* 初始化页结构和内存空闲链表。`pages` 数组中每个 `struct Page`
* 对应一个物理页。页采用引用计数管理，空闲页保存在一个链表中。
*
* 提示：使用 `LIST_INSERT_HEAD` 将空闲页插入 `page_free_list`。
*/
void page_init(void) {
/* 步骤 1：初始化 page_free_list。 */
/* 提示：使用 include/queue.h 中定义的宏 `LIST_INIT`。 */
/* 练习 2.3：在此处填写代码。（1/4） */
/* 步骤 2：将 `freemem` 向上对齐到 PAGE_SIZE 的整数倍。 */
/* 练习 2.3：在此处填写代码。（2/4） */
/* 步骤 3：将 `freemem` 以下的所有内存标记为已使用（将 `pp_ref` 设为 1） */
/* 练习 2.3：在此处填写代码。（3/4） */
/* 步骤 4：将其余内存标记为空闲。 */
/* 练习 2.3：在此处填写代码。（4/4） */
}
/* 概述：
* 从空闲内存中分配一个物理页，并将该页内容清零。
*
* 后置条件：
* 如果分配失败（内存耗尽，没有空闲页），返回 -E_NO_MEM。
* 否则，将分配得到的 `Page` 地址写入 *pp，并返回 0。
*
* 注意：
* 此函数不会增加该页的引用计数 `pp_ref`——如果有需要，调用者必须自行增加
* （可以显式增加，也可以通过 page_insert 间接增加）。
*
* 提示：使用 include/queue.h 中定义的 `LIST_FIRST` 和 `LIST_REMOVE`。
*/
int page_alloc(struct Page **new) {
/* 步骤 1：从空闲内存中取出一个页。如果失败，返回错误码。*/
struct Page *pp;
/* 练习 2.4：在此处填写代码。（1/2） */
LIST_REMOVE(pp, pp_link);
/* 步骤 2：将这个页初始化为全零。
* 提示：使用 `memset`。 */
/* 练习 2.4：在此处填写代码。（2/2） */
*new = pp;
return 0;
}
/* 概述：
* 释放页 `pp`，将其标记为空闲。
*
* 前置条件：
* `pp->pp_ref` 为 `0`。
*/
void page_free(struct Page *pp) {
assert(pp->pp_ref == 0);
/* 只需将它插入到 `page_free_list` 中。 */
/* 练习 2.5：在此处填写代码。 */
}
/* 概述：
* 给定页目录指针 `pgdir`，`pgdir_walk` 返回虚拟地址 `va`
* 对应的页表项指针。
*
* 前置条件：
* `pgdir` 是一个二级页表结构。
* `ppte` 是一个有效指针，即它不能为 NULL。
*
* 后置条件：
* 如果内存耗尽，返回 -E_NO_MEM。
* 否则，获取到页表项后，将页表项地址存入 *ppte，并返回 0 表示成功。
*
* 提示：
* 我们使用二级指针来存储页表项，并通过返回状态码来表示该函数是否成功。
*/
static int pgdir_walk(Pde *pgdir, u_long va, int create, Pte **ppte) {
Pde *pgdir_entryp;
struct Page *pp;
/* 步骤 1：获取对应的页目录项。 */
/* 练习 2.6：在此处填写代码。（1/3） */
/* 步骤 2：如果对应的页表不存在（无效），则：
* * 如果参数 `create` 被设置，则创建一个。并在页目录项中为这个新页设置权限位
* `PTE_C_CACHEABLE | PTE_V`。如果分配新页失败（内存耗尽），返回错误码。
* * 否则，将 NULL 赋值给 `*ppte` 并返回 0。
*/
/* 练习 2.6：在此处填写代码。（2/3） */
/* 步骤 3：将页表项的内核虚拟地址赋值给 `*ppte`。 */
/* 练习 2.6：在此处填写代码。（3/3） */
return 0;
}
/* 概述：
* 将物理页 `pp` 映射到虚拟地址 `va`。页表项的权限（低 12 位）
* 应设置为 `perm | PTE_C_CACHEABLE | PTE_V`。
*
* 后置条件：
* 成功时返回 0
* 如果无法分配页表，则返回 -E_NO_MEM
*
* 提示：
* 如果 `va` 处已经映射了一个页，调用 page_remove() 释放该映射。
* 如果插入成功，应增加 `pp_ref`。
*/
int page_insert(Pde *pgdir, u_int asid, struct Page *pp, u_long va, u_int perm) {
Pte *pte;
/* 步骤 1：获取对应的页表项。 */
pgdir_walk(pgdir, va, 0, &pte);
if (pte && (*pte & PTE_V)) {
if (pa2page(*pte) != pp) {
page_remove(pgdir, asid, va);
} else {
tlb_invalidate(asid, va);
*pte = page2pa(pp) | perm | PTE_C_CACHEABLE | PTE_V;
return 0;
}
}
/* 步骤 2：使用 `tlb_invalidate` 刷新 TLB。 */
/* 练习 2.7：在此处填写代码。（1/3） */
/* 步骤 3：重新获取或创建页表项。 */
/* 如果创建失败，返回错误码。 */
/* 练习 2.7：在此处填写代码。（2/3） */
/* 步骤 4：将该页插入页表项，权限设为 `perm | PTE_C_CACHEABLE | PTE_V`，
* 并增加其 `pp_ref`。 */
/* 练习 2.7：在此处填写代码。（3/3） */
return 0;
}
/* Lab 2 关键代码 "page_lookup" */
/*概述：
查找虚拟地址 `va` 映射到的 Page。
后置条件：
返回对应 Page 的指针，并将它的页表项存入 *ppte。
如果 `va` 没有映射到任何 Page，则返回 NULL。*/
struct Page *page_lookup(Pde *pgdir, u_long va, Pte **ppte) {
struct Page *pp;
Pte *pte;
/* 步骤 1：获取页表项。 */
pgdir_walk(pgdir, va, 0, &pte);
/* 提示：检查该页表项是否不存在或无效。 */
if (pte == NULL || (*pte & PTE_V) == 0) {
return NULL;
}
/* 步骤 2：获取对应的 Page 结构。 */
/* 提示：使用 include/pmap.h 中定义的函数 `pa2page`。 */
pp = pa2page(*pte);
if (ppte) {
*ppte = pte;
}
return pp;
}
/* 关键代码 "page_lookup" 结束 */
/* 概述：
* 减少页 `pp` 的 `pp_ref` 值。
* 当没有任何引用（虚拟地址映射）指向该页时，释放该页。
*/
void page_decref(struct Page *pp) {
assert(pp->pp_ref > 0);
/* 如果 `pp_ref` 递减到 0，就释放这个页。 */
if (--pp->pp_ref == 0) {
page_free(pp);
}
}
/* Lab 2 关键代码 "page_remove" */
// 概述：
// 取消虚拟地址 `va` 处的物理页映射。
void page_remove(Pde *pgdir, u_int asid, u_long va) {
Pte *pte;
/* 步骤 1：获取页表项，并检查该页表项是否有效。 */
struct Page *pp = page_lookup(pgdir, va, &pte);
if (pp == NULL) {
return;
}
/* 步骤 2：减少 `pp` 的引用计数。 */
page_decref(pp);
/* 步骤 3：刷新 TLB。 */
*pte = 0;
tlb_invalidate(asid, va);
return;
}
/* 关键代码 "page_remove" 结束 */
void physical_memory_manage_check(void) {
struct Page *pp, *pp0, *pp1, *pp2;
struct Page_list fl;
int *temp;
// 应该能够分配三个页
pp0 = pp1 = pp2 = 0;
assert(page_alloc(&pp0) == 0);
assert(page_alloc(&pp1) == 0);
assert(page_alloc(&pp2) == 0);
assert(pp0);
assert(pp1 && pp1 != pp0);
assert(pp2 && pp2 != pp1 && pp2 != pp0);
// 临时拿走其余所有空闲页
fl = page_free_list;
// 现在这个 page_free_list 必须为空！！！！
LIST_INIT(&page_free_list);
// 现在不应再有空闲内存
assert(page_alloc(&pp) == -E_NO_MEM);
temp = (int *)page2kva(pp0);
// 向 pp0 写入 1000
*temp = 1000;
// 释放 pp0
page_free(pp0);
printk("The number in address temp is %d\n", *temp);
// 再次分配
assert(page_alloc(&pp0) == 0);
assert(pp0);
// pp0 不应该发生变化
assert(temp == (int *)page2kva(pp0));
// pp0 应该被清零
assert(*temp == 0);
page_free_list = fl;
page_free(pp0);
page_free(pp1);
page_free(pp2);
struct Page_list test_free;
struct Page *test_pages;
test_pages = (struct Page *)alloc(10 * sizeof(struct Page), PAGE_SIZE, 1);
LIST_INIT(&test_free);
// LIST_FIRST(&test_free) = &test_pages[0];
int i, j = 0;
struct Page *p, *q;
for (i = 9; i >= 0; i--) {
test_pages[i].pp_ref = i;
// test_pages[i].pp_link=NULL;
// printk("0x%x 0x%x\n",&test_pages[i], test_pages[i].pp_link.le_next);
LIST_INSERT_HEAD(&test_free, &test_pages[i], pp_link);
// printk("0x%x 0x%x\n",&test_pages[i], test_pages[i].pp_link.le_next);
}
p = LIST_FIRST(&test_free);
int answer1[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
assert(p != NULL);
while (p != NULL) {
// printk("%d %d\n",p->pp_ref,answer1[j]);
assert(p->pp_ref == answer1[j++]);
// printk("ptr: 0x%x v: %d\n",(p->pp_link).le_next,((p->pp_link).le_next)->pp_ref);
p = LIST_NEXT(p, pp_link);
}
// insert_after 测试
int answer2[] = {0, 1, 2, 3, 4, 20, 5, 6, 7, 8, 9};
q = (struct Page *)alloc(sizeof(struct Page), PAGE_SIZE, 1);
q->pp_ref = 20;
// printk("---%d\n",test_pages[4].pp_ref);
LIST_INSERT_AFTER(&test_pages[4], q, pp_link);
// printk("---%d\n",LIST_NEXT(&test_pages[4],pp_link)->pp_ref);
p = LIST_FIRST(&test_free);
j = 0;
// printk("into test\n");
while (p != NULL) {
// printk("%d %d\n",p->pp_ref,answer2[j]);
assert(p->pp_ref == answer2[j++]);
p = LIST_NEXT(p, pp_link);
}
printk("physical_memory_manage_check() succeeded\n");
}
void page_check(void) {
struct Page *pp, *pp0, *pp1, *pp2;
struct Page_list fl;
// 应该能够为页目录分配一个页
assert(page_alloc(&pp) == 0);
Pde *boot_pgdir = (Pde *)page2kva(pp);
// 应该能够分配三个页
pp0 = pp1 = pp2 = 0;
assert(page_alloc(&pp0) == 0);
assert(page_alloc(&pp1) == 0);
assert(page_alloc(&pp2) == 0);
assert(pp0);
assert(pp1 && pp1 != pp0);
assert(pp2 && pp2 != pp1 && pp2 != pp0);
// 临时拿走其余所有空闲页
fl = page_free_list;
// 现在这个 page_free_list 必须为空！！！！
LIST_INIT(&page_free_list);
// 现在不应再有空闲内存
assert(page_alloc(&pp) == -E_NO_MEM);
// 当前没有空闲内存，因此无法分配页表
assert(page_insert(boot_pgdir, 0, pp1, 0x0, 0) < 0);
// 释放 pp0 后再试：pp0 应该会被用作页表
page_free(pp0);
assert(page_insert(boot_pgdir, 0, pp1, 0x0, 0) == 0);
assert(PTE_FLAGS(boot_pgdir[0]) == (PTE_C_CACHEABLE | PTE_V));
assert(PTE_ADDR(boot_pgdir[0]) == page2pa(pp0));
assert(PTE_FLAGS(*(Pte *)page2kva(pp0)) == (PTE_C_CACHEABLE | PTE_V));
printk("va2pa(boot_pgdir, 0x0) is %x\n", va2pa(boot_pgdir, 0x0));
printk("page2pa(pp1) is %x\n", page2pa(pp1));
// printk("pp1->pp_ref is %d\n",pp1->pp_ref);
assert(va2pa(boot_pgdir, 0x0) == page2pa(pp1));
assert(pp1->pp_ref == 1);
// 应该能够将 pp2 映射到 PAGE_SIZE，因为 pp0 已经被分配为页表
assert(page_insert(boot_pgdir, 0, pp2, PAGE_SIZE, 0) == 0);
assert(va2pa(boot_pgdir, PAGE_SIZE) == page2pa(pp2));
assert(pp2->pp_ref == 1);
// 现在不应再有空闲内存
assert(page_alloc(&pp) == -E_NO_MEM);
printk("start page_insert\n");
// 应该能够再次将 pp2 映射到 PAGE_SIZE，因为它本来就已经在那里
assert(page_insert(boot_pgdir, 0, pp2, PAGE_SIZE, 0) == 0);
assert(va2pa(boot_pgdir, PAGE_SIZE) == page2pa(pp2));
assert(pp2->pp_ref == 1);
// pp2 不应该在空闲链表中
// 如果 page_insert 中对引用计数处理粗心，就可能发生这种情况
assert(page_alloc(&pp) == -E_NO_MEM);
// 不应该能够映射到 PDMAP，因为创建页表需要空闲页
assert(page_insert(boot_pgdir, 0, pp0, PDMAP, 0) < 0);
// 在 PAGE_SIZE 处插入 pp1（替换 pp2）
assert(page_insert(boot_pgdir, 0, pp1, PAGE_SIZE, 0) == 0);
// 此时 pp1 应同时映射在 0 和 PAGE_SIZE，pp2 不再被映射，……
assert(va2pa(boot_pgdir, 0x0) == page2pa(pp1));
assert(va2pa(boot_pgdir, PAGE_SIZE) == page2pa(pp1));
// ……并且引用计数也应正确反映这一点
assert(pp1->pp_ref == 2);
printk("pp2->pp_ref %d\n", pp2->pp_ref);
assert(pp2->pp_ref == 0);
printk("end page_insert\n");
// pp2 应该能够被 page_alloc 返回
assert(page_alloc(&pp) == 0 && pp == pp2);
// 取消 0 处对 pp1 的映射后，pp1 仍应保留在 PAGE_SIZE 处
page_remove(boot_pgdir, 0, 0x0);
assert(va2pa(boot_pgdir, 0x0) == ~0);
assert(va2pa(boot_pgdir, PAGE_SIZE) == page2pa(pp1));
assert(pp1->pp_ref == 1);
assert(pp2->pp_ref == 0);
// 取消 PAGE_SIZE 处对 pp1 的映射后，应释放它
page_remove(boot_pgdir, 0, PAGE_SIZE);
assert(va2pa(boot_pgdir, 0x0) == ~0);
assert(va2pa(boot_pgdir, PAGE_SIZE) == ~0);
assert(pp1->pp_ref == 0);
assert(pp2->pp_ref == 0);
// 因此它应该能够再次被 page_alloc 返回
assert(page_alloc(&pp) == 0 && pp == pp1);
// 现在不应再有空闲内存
assert(page_alloc(&pp) == -E_NO_MEM);
// 强行把 pp0 取回来
assert(PTE_ADDR(boot_pgdir[0]) == page2pa(pp0));
boot_pgdir[0] = 0;
assert(pp0->pp_ref == 1);
pp0->pp_ref = 0;
// 归还空闲链表
page_free_list = fl;
// 释放我们拿走的那些页
page_free(pp0);
page_free(pp1);
page_free(pp2);
page_free(pa2page(PADDR(boot_pgdir)));
printk("page_check() succeeded!\n");
}Page_list结构体
EntryLO寄存器
- PTE_V 有效位，若某页表项的有效位为1，则该页表项有效，其中高20位就是对应的 物理页号。
- PTE_D 可写位，若某页表项的可写位为1，则允许经由该页表项对物理页进行写操作。
- PTE_G 全局位，若某页表项的全局位为1，则TLB仅通过虚页号匹配表项，而不匹配 ASID，将在 Lab3 中用于映射 pages 和 envs 到用户空间。本 Lab 中可以忽略。
- PTE_C_CACHEABLE 可缓存位，配置对应页面的访问属性为可缓存。通常对于所有物理 页面，都将其配置为可缓存，以允许CPU使用cache加速对这些页面的访存请求。
- PTE_COW 写时复制位，将在 Lab4 中用到，用于实现 fork 的写时复制机制。本 Lab 中可以忽略。
- PTE_LIBRARY 共享页面位，将在 Lab6 中用到，用于实现管道机制。本Lab中可以忽略
地址转换机制
使用到的东西
memset(void *s, int c, size_t n) ，按字节填内容。
s：要操作的内存起始地址c：要填充的值n：要填充的字节数