【xv6操作系统】页表与写时拷贝解析及相关实验设计
页表
页表概念
deepseek说：
页表（Page Table）是操作系统中用于实现虚拟内存管理的核心数据结构，它负责将进程的虚拟地址（Virtual Address）转换为实际的物理地址（Physical Address）。通过分页机制，操作系统能够更高效、安全地管理内存资源。
1. 页表的核心作用：
地址映射： 每个进程“看到”的是一个连续的虚拟地址空间（如0x0000 ~ 0xFFFF）。实际上，物理内存可能分散且不连续。页表记录了 虚拟页号 → 物理页框号 的映射关系，由CPU的 内存管理单元（MMU） 自动完成地址转换。
内存保护： 页表中的每个条目（页表项）包含权限标志位，如：
- 读/写（R/W）：保护进程无法误操作只读数据或代码段
- 用户/内核（U/S）：阻止用户程序访问内核内存（避免崩溃或攻击）
- 存在位（Present Bit）：标记该页是否已加载到物理内存
简化内存管理： 以分页的方式管理内存，支持动态内存分配和释放。当某个虚拟页未在物理内存中时，触发触发缺页中断（Page Fault），操作系统会从磁盘（如Swap分区）加载所需页面到内存，并更新页表。这使得物理内存成为磁盘的缓存，突破了内存容量限制。
实现虚拟内存： 页表是虚拟内存管理的基础支持。借助页表，操作系统能够将程序需要的内存部分保存在磁盘上（例如交换空间），并在需要时动态加载到内存中，从而使得程序可以使用更大的内存空间，提升系统的扩展能力和性能。
虚拟内存和物理内存通常被划分为固定大小的块，称为“页”（Page）和 “页框号”（Frame）。每个页面由相同数量的连续字节组成，常见的页面大小有4KB、8KB等。
2. 页表的结构： 页表主要包含每个 虚拟页号（VPN） 对应的 物理页框号（PPN） 及一些控制信息，以下是页表的主要组成部分：
- 页表项（PTE）：每一项记录了一个虚拟页和一个物理页的映射关系，通常包含：
- 物理页框号（PPN）： 指向物理内存中的页面框。
- 有效位： 指示该页是否在内存中有效。
- 访问权限： 指示对该页的访问权限（如可读、可写、可执行等）。
- 其他信息： 如引用位、修改位等，用于页面置换算法。
3. 地址转换过程：在访问内存时，CPU会将虚拟地址划分为页号和页内偏移（offset），具体步骤如下：
- 获取虚拟页号： 从虚拟地址中提取页号部分。
- 查找页表： 使用虚拟页号查询相应的页表项，获取物理页框号。
- 构建物理地址： 将物理页框号与原虚拟地址中的页内偏移结合，生成物理地址，访问实际的内存。
4. 多级页表： 由于页表可能非常大，操作系统通常采用多级页表结构，分层存储以减少内存占用。例如，二级或三级页表可以将页表分解为多个层次，只有在需要时才分配内存。
5. TLB（Translation Lookaside Buffer）： CPU缓存频繁使用的页表项，加速地址转换。若TLB命中，省去多级页表访问步骤，TLB 的主要优势如下：
- 提高地址转换速度： 通过缓存频繁使用的页表项，减少了内存访问延迟。
- 降低内存带宽消耗： 减少对页表的访问频率，减轻内存负担。
- 提高系统性能： 尤其在涉及大量内存访问的应用程序中，TLB 的使用显著提高了系统的整体性能。
整理一些基本名词，不熟悉的先留个印象，后续都比较重要
- 页表page table： 记录从VPN→PPN的映射关系表
- 页表项 PTE： 页表中的每一项，具体内容如上述中的解释
- 虚拟页号VPN： virtual page number
- 物理页号PPN/PFN： physical page number
- 页内偏移量offset： 偏移量的位数决定了一页的大小，一般是12位，即4KB
- 虚拟地址va： virtual address相当于VPN与offset的组合
- 物理地址pa： physical address相当于PFN/PPN与offset的组合
- 物理页帧： page frame
xv6页表
- XV6基于Sv39 RISC-V运行，这意味着它只使用64位虚拟地址的低39位，高25位不使用。虚拟地址的前27位用于索引页表，页表在逻辑上视作由 227个 页表条目(PTE) 组成的数组，每个PTE中包含一个44位的物理页码(PPN)，以及一些控制和状态的标志位。
- 地址转换过程：处理一个虚拟地址时，使用该虚拟地址的前27位在页表中查找对应的PTE后。找到PTEPTE中的44位PPN与虚拟地址的低12位组合(即页内偏移)，生成一个 56位的物理地址
- 页表允许操作系统控制虚拟地址到物理地址的映射，并且以 4096字节(4KB)的页 为单位进行转换和管理，以 4096(212)字节的对齐块的粒度控制虚拟地址到物理地址的转换
但实际在Sv39中，页表是一个三级树型结构，根页表是这棵树的根节点，它是一个4KB(4096字节)的页，每个页有512个PTE(每个PTE大小是8个字节(64位)，总共可以有512个条目，4096字节: 8字节)。每个PTE记录了下一级页表的位置(也就是下一级页表的物理地址)。虚拟地址使用39位，其中的前27位被用来在三级页表结构中进行查找。在找到第三级的PTE之后，PTE中会有物理页号(PPN)，这个物理页号提供了物理地址的高44位，虚拟地址的最后12位作页内偏移。实际的转换如下图所示：
每一页页表的属性主要包含以下标志位：
PTE_V:是否预配置 PTEPTE_R:是否可读PTE_W:是否可写PTE_X:是否可执行
页表是分页机制的关键部分，负责记录虚拟页到物理页的映射关系；操作系统负责对页表进行配置
xv6 TLB
- 对于一个虚拟内存地址的寻址，需要读三次内存，代价有点高。实际中，几乎所有的处理器都会对最近使用过的虚拟地址的翻译结果有缓存。这个缓存被称为：Translation Lookside Buffer，TLB。这就是Page Table Entry的缓存，也就是PTE的缓存。
- 当处理器第一次查找一个虚拟地址时，硬件通过3级page table得到最终的PPN，TLB会保存虚拟地址到物理地址的映射关系。这样下一次访问同一个虚拟地址时，处理器可以査看TLB，TLB会直接返回物理地址，而不需要通过page table得到结果。
- 如果切换了page table，操作系统需要告诉处理器当前正在切换page table，处理器会清空TLB。
内核地址空间
xv6为每个进程维护一个页表，用以描述每个进程的用户地址空间，外加一个单独描述内核地址空间的页表。内核配置其地址空间的布局，以允许自己以可预测的虚拟地址访问物理内存和各种硬件资源。
- 包括从物理地址0x80000000开始并至少到0x86400000结束的RAM（物理内存），xv6称结束地址为
PHYSTOP - 操作系统启动时，会从地址0x80000000开始运行，左侧低于PHYSTOP的虚拟地址，与右侧使用的物理地址是一样的(直接映射)，直接映射简化了读取或写入物理内存的内核代码
有几个内核虚拟地址不是直接映射：
- 蹦床页面(
trampolinepage)。它映射在虚拟地址空间的顶部；用户页表具有相同的映射。一个物理页面（持有蹦床代码）在内核的虚拟地址空间中映射了两次：一次在虚拟地址空间的顶部，一次直接映射。 - 内核栈页面。每个进程都有自己的内核栈，它将映射到偏高一些的地址，这样xv6在它之下就可以留下一个未映射的保护页(
guard page)。保护页的PTE是无效的（也就是说PTE_V没有设置），所以如果内核溢出内核栈就会引发一个异常，内核触发panic。如果没有保护页，栈溢出将会覆盖其他内核内存，引发错误操作。恐慌崩溃（panic crash）是更可取的方案。（注：Guard page不会浪费物理内存，它只是占据了虚拟地址空间的一段靠后的地址，但并不映射到物理地址空间。）
实验1：加速系统调用
- 通过在用户空间和内核之间共享只读区域的数据来加速某些系统调用，消除在执行这些系统调用时需要进行内核切换的必要性
- 当每个进程被创建时，在USYSCALL（在memlayout.h中定义的虚拟地址）处映射一个只读页面。在该页面的开头，存储一个struct usyscall（同样在memlayout.h中定义），并初始化它以存储当前进程的PID。
- 本实验核心在于对页的布局、分配与创建及释放的理解与程序实现
实验要求：实现优化getpid()，创建一个页 将p->pid存入新的页中
1. 创建每个进程后，在 USYSCALL（在 memlayout.h 中定义的 VA）中映射一个只读页面，内存分配布局图
- 其中
MAXVA定义如下：9 + 9 + 9 +12表示三级页表 + 12位偏移 啊#define MAXVA (1L << (9 + 9 + 9 + 12 - 1))
2. 在 proc_pagetable 中对新插入的SYSCALL页表进行映射，并设置只读权限
模仿 TRAMPOLINE 页与 TRAPFRAME 页进行页表映射，并在进程结构体中添加页usyscall页
注意的是这里不能只设置PTE_R位，因为用户需要访问该物理页，所以还需要设置PTE_U位。
// Create a user page table for a given process, // with no user memory, but with trampoline pages. pagetable_t proc_pagetable(struct proc *p) { ... // map the trapframe just below TRAMPOLINE, for trampoline.S. if(mappages(pagetable, TRAPFRAME, PGSIZE, (uint64)(p->trapframe), PTE_R | PTE_W) < 0){ uvmunmap(pagetable, TRAMPOLINE, 1, 0); uvmfree(pagetable, 0); return 0; } // 分配USYSCALL页 if(mappages(pagetable, USYSCALL, PGSIZE,(uint64)(p->usyscall) , PTE_R | PTE_W | PTE_U) < 0){ uvmunmap(pagetable, TRAMPOLINE, 1, 0); uvmunmap(pagetable, TRAPFRAME, 1, 0); uvmfree(pagetable, 0); return 0; } return pagetable; }
3. 在 allocproc 函数中为新的syscall页申请内存空间和初始化，同样仿照 TRAPFRAME 页进行申请内存空间和初始化，并把进程的 pid 放到 syscall 页中去
// Look in the process table for an UNUSED proc.
// If found, initialize state required to run in the kernel,
// and return with p->lock held.
// If there are no free procs, or a memory allocation fails, return 0.
static struct proc*
allocproc(void)
{
struct proc *p;
struct usyscall u;
...
found:
p->pid = allocpid();
p->state = USED;
// Allocate a trapframe page.
if((p->trapframe = (struct trapframe *)kalloc()) == 0){
freeproc(p);
release(&p->lock);
return 0;
}
// Allocate a usyscall page.
if((p->usyscall = (uint64)kalloc()) == 0){
freeproc(p);
release(&p->lock);
return 0;
}
// 把进程pid放进usyscall页
u.pid = p->pid;
*(struct usyscall*)(p->usyscall) = u;
// An empty user page table.
...
}
4. 释放内存
释放页表
static void freeproc(struct proc *p) { if(p->trapframe) kfree((void*)p->trapframe); p->trapframe = 0; // 释放usyscall页 if(p->usyscall) kfree((void*)p->usyscall); p->usyscall = 0; if(p->pagetable) proc_freepagetable(p->pagetable, p->sz); p->pagetable = 0; ... }取消映射
// kernel/proc.c // Free a process's page table, and free the physical memory it refers to. void proc_freepagetable(pagetable_t pagetable, uint64 sz) { uvmunmap(pagetable, TRAMPOLINE, 1, 0); uvmunmap(pagetable, TRAPFRAME, 1, 0); uvmunmap(pagetable, USYSCALL, 1, 0); uvmfree(pagetable, sz); }
实验2：打印三级页表
- 该实验需要实现一个打印页表内容的函数，以题目所示的格式打印传进的
页表。 - 在Sv39模式下，页表是一个三级树型结构，根页表是这棵树的根节点它是一个4KB(4096字节)的页，每个页有512个PTE，每个PTE记录了下级页表的位置(也就是下一级页表的物理地址，最后一级页表的PTE指向的是最终映射的物理地址)
- 需要模拟查询页表的过程，对三级页表进行遍历并打印。在虚拟内存相的 kernel/vm.c 中的 freewalk()函数已经实现了递归遍历页表并将其释放，所以只要模仿其逻辑实现打印功能即可。代码：
void print_page(pagetable_t pagetable, int level) { // there are 2^9 = 512 PTEs in a page table. // 遍历页表项 for(int i = 0; i < 512; i++) { pte_t pte = pagetable[i]; // 如果页表项存在，并且可读，可写可执行 if((pte & PTE_V) && (pte & (PTE_R|PTE_W|PTE_X)) == 0) { uint64 child = PTE2PA(pte); for (int i = 0; i < level; i++) { printf(".. "); } printf(".."); printf("%d pte: %p pa:%p\n", level, pte, child); print_page((pagetable_t)child, level+1); } else if(pte & PTE_V) { uint64 child = PTE2PA(pte); for (int i = 0; i < level; i++) { printf(".. "); } printf(".."); printf("%d pte: %p pa:%p\n", level, pte, child); } } } void vmprint(pagetable_t pagetable) { printf("page table %p\n", *pagetable); print_page(pagetable, 0); } - 记得在defs.h中添加其函数声明
void vmprint(pagetable_t);，并在 exec.c:execreturn argc;之前插入代码//kernel/defs.h void vmprint(pagetable_t);// kernel/exec.c-exec() if(p->pid==1) vmprint(p->pagetable); return argc; // this ends up in a0
实验3：检测已访问的页表
- 为 xv6 添加一个新功能，该功能通过检查 RISC-V 页表中的访问位来检测并报告这一信息给用户空间
- 检测多个页是否被访问，返回多个页被访问情况的位掩码
检测页访问流程图如下图左，返回值是一个按位表示，如下图右
sys_pgaccess函数实现流程图如下：
程序实现：
int sys_pgaccess(void)
{
uint64 addr;
int len;
int bitmask;
// 获取用户参数
if(argaddr(0, &addr) < 0 || argint(1, &len) < 0 || argint(2, &bitmask) < 0)
return -1;
if(len > 32 || len < 0)
return -1;
int res = 0;
// 核心 计算res
struct proc *p = myproc();
for (int i = 0; i < len; i++)
{
uint64 va = addr + i * PGSIZE;
// 计算虚拟内存va对应的页内的PTE_A的flag是否为1
int abit = pgaccess(p->pagetable, va);
res = res | abit << i;
}
// Copy from kernel to user.
if(copyout(p->pagetable, bitmask, (char *)&res, sizeof(res)) < 0)
return -1;
return 0;
}
// 计算虚拟内存va对应的页内的PTE_A的flag是否为1
int pgaccess(pagetable_t pagetable, uint64 va)
{
pte_t *pte;
if(va >= MAXVA)
return 0;
pte = walk(pagetable, va, 0);
if(pte == 0)
return 0;
if(*pte & PTE_A) {
*pte = *pte & (~PTE_A); // 清空pte的第六位
return 1;
}
return 0;
}
- 记到定义访问标志位 define PTE_A in kernel/riscv.h，页面已访问表示位，访问后硬件会自动置1，但需要软件清零
写时拷贝
页面错误异常：
- 加载页面错误： 当加载指令访问的虚拟地址找不到对应的物理地址时触发。
- 存储页面错误： 当存储指令访问的虚拟地址找不到对应的物理地址时触发。
- 指令页面错误： 当指令获取的虚拟地址找不到对应的物理地址时触发
这些页面错误信息保存在 RISC-V 的两个寄存器中:
scause:指示页面错误的类型(加载、存储或指stval:保存无法转换的虚拟地址。
写时拷贝
在原始的XV6中，fork函数是通过直接对进程的地址空间完整地复制一份来实现的。但是，拷贝整个地址空间是十分耗时的，并且在很多情况下，程序立即调用 exec 函数来替换掉地址空间，导致 fork 做了很多无用功。
该实验的改进：
COW fork()为子进程创建一个页表，让子进程和父进程都一起映射到父进程的物理页禁止写权限，因为一旦子进程想要修改这些内存的内容，相应的更新应该对父进程不可见，因此需要将这里的父进程和子进程的PTE的标志位都设置成只读的
当任一进程试图写入其中一个COW页时，CPU将强制产生页面错误。内核页面错误处理程序检测到这种情况，将为出错进程分配一页物理内存，将原始页复制到新页中，并修改出错进程中的相关PTE指向新的页面，将PTE标记为可写。
👉 
当页面错误处理程序返回时，用户进程将能够写入其页面副本。
COW fork()将使得释放用户内存的物理页面变得更加棘手。给定的物理页可能会被多个进程的页表引用，并且只有在最后一个引用消失时才应该被释放，所以针对这个问题需要有引用计数机制。
页的生命周期进行管理，确保页没有被任何进程使用的时候才释放：
原本的xv6中，一个物理页只会在一个进程中有映射，kalloc用来分配物理页，kfree 用来回收物理页。在COW机制中，一个物理页会在多个进程中有映射，所以要在最后一个映射释放的时候，才真正释放回收该物理页，结合这些，需要实现以下操作:
kalloc：分配物理页，将其引用数置为1krefpage：创建物理页的一个新映射的时候，引用数+1kcopy_n_deref：将原物理页的数据复制到一个新物理页上(引用数为 1)，返回得到的新物理页；并将原物理页的引用数 -1kfree：释放物理页的一个映射，引用数减 1；如果引用数变为 0，则释放回收物理页
实验实现
步骤一： 如何判断获得的 va 是一个 cow_fault，记录每个PTE是否是COW映射，可以使用RISC-V PTE中的 RSW（reserved for software，即为软件保留的）位来实现此目的。
- 定义 PTE_COW 标志
步骤二： 修改 uvmcopy() 将父进程的物理页映射到子进程，而不是分配新页。在子进程和父进程的PTE中清除PTE_W标志，并增加内存的引用计数 kaddrefcnt，该函数在引用计数中涉及。
uvmcopy(pagetable_t old, pagetable_t new, uint64 sz)
{
pte_t *pte;
uint64 pa, i;
uint flags;
for(i = 0; i < sz; i += PGSIZE){
if((pte = walk(old, i, 0)) == 0)
panic("uvmcopy: pte should exist");
if((*pte & PTE_V) == 0)
panic("uvmcopy: page not present");
pa = PTE2PA(*pte);
flags = PTE_FLAGS(*pte);
// 仅对可写页面设置COW标记
if (flags & PTE_W){
flags = (flags | PTE_COW) & ~PTE_W;
*pte = PA2PTE(pa) | flags;
}
// 直接将pa地址拷贝给new
if(mappages(new, i, PGSIZE, (uint64)pa, flags) != 0){
goto err;
}
// 增加内存的引用计数
kaddrefcnt((char*)pa);
}
return 0;
err:
uvmunmap(new, 0, i / PGSIZE, 1);
return -1;
}
步骤三： 修改 usertrap() 以识别页面错误。当COW页面出现页面错误时，使用kalloc()分配一个新页面，并将旧页面复制到新页面，然后将新页面添加到PTE中并设置PTE_W。
if(r_scause() == 8){
...
}
else if((which_dev = devintr()) != 0){
...
}
else if (r_scause() == 15 || r_scause() == 13) {
// 获取出错的虚拟地址
uint64 va = r_stval();
if(va >= p->sz ||
is_cow_fault(p->pagetable, va) != 0 ||
cow_alloc(p->pagetable, PGROUNDDOWN(va)) == 0)
p->killed = 1;
}
else {
printf("usertrap(): unexpected scause %p pid=%d\n", r_scause(), p->pid);
printf(" sepc=%p stval=%p\n", r_sepc(), r_stval());
p->killed = 1;
}
在vm.c最后定义 is_cow_fault 与 cow_alloc 函数，分别用于判断是否为cow_fault以及为创建新的页，注意必要的函数在defs.h中声明
is_cow_faul：判断是否为 cow 错误//判断是否为cow_fault 0是 -1不是 // param: 执行查询的页表 虚拟地址 int is_cow_fault(pagetable_t pagetable, uint64 va) { if(va >= MAXVA) return -1; // 获取页表页 pte_t *pte = walk(pagetable, va,0); //前置判断 if(pte == 0) return -1; if((*pte & PTE_V) == 0) return -1; //判断页表条目的PTE_COW位是否为1 return (*pte & PTE_COW ? 0 : -1); }cow_alloc：分配内存// 为 cow_fault 分配实际物理内存 // param: 执行查询的页表 虚拟地址 // 分配后va对应的物理地址，如果返回0则分配失败 void* cow_alloc(pagetable_t pagetable, uint64 va) { if(va % PGSIZE != 0) return 0; // 获取页表地址 uint64 pa = walkaddr(pagetable, va); // 获取对应的物理地址 if(pa == 0) return 0; // 获取页表页 pte_t *pte = walk(pagetable, va,0); if (krefcnt((char*)pa) == 1) { // 只剩一个进程对此物理地址存在引用 // 则直接修改对应的PTE即可 *pte |= PTE_W; *pte &= ~PTE_COW; return (void*)pa; } else { // 多个进程对物理内存存在引用 // 需要分配新的页面，并拷贝旧页面的内容 char *mem = kalloc(); if (mem == 0) return 0; // 复制旧页面内容到新页 memmove(mem, (char*)pa, PGSIZE); // 清除PTE_V，否则在mappagges中会判定为remap *pte &= ~PTE_V; // 为新页面添加映射 if(mappages(pagetable, va, PGSIZE, (uint64)mem, (PTE_FLAGS(*pte) | PTE_W) & ~PTE_COW) != 0) { kfree(mem); *pte |= PTE_V; return 0; } // 将原来的物理内存引用计数减1 kfree((char*)PGROUNDDOWN(pa)); return mem; } }
步骤四： 在copyout中处理相同的情况，如果是COW页面，需要更换pa0指向的物理地址
while(len > 0){
va0 = PGROUNDDOWN(dstva);
pa0 = walkaddr(pagetable, va0);
// 处理COW页面的情况
if(cowpage(pagetable, va0) == 0) {
// 更换目标物理地址
pa0 = (uint64)cowalloc(pagetable, va0);
}
if(pa0 == 0)
return -1;
...
}
步骤五：“引用计数” 在 kalloc.c 下修改
定义引用计数的全局变量
ref，其中包含了一个自旋锁和一个引用计数数组，由于ref是全局变量，会被自动初始化为全0。//定义引用计数的全局变量ref struct ref_stru { struct spinlock lock; int cnt[PHYSTOP / PGSIZE]; // 引用计数 } ref;在
kinit中初始化ref的自旋锁void kinit() { initlock(&kmem.lock, "kmem"); initlock(&ref.lock, "ref"); // kinit中初始化ref的自旋锁 freerange(end, (void*)PHYSTOP); }修改
kalloc和kfree函数，在kalloc中初始化内存引用计数为1，在kfree函数中对内存引用计数减1，如果引用计数为0时才真正删除void kfree(void *pa) { struct run *r; if(((uint64)pa % PGSIZE) != 0 || (char*)pa < end || (uint64)pa >= PHYSTOP) panic("kfree"); // 只有当引用计数为0了才回收空间 // 否则只是将引用计数减1 acquire(&ref.lock); if(--ref.cnt[(uint64)pa / PGSIZE] == 0) { release(&ref.lock); r = (struct run*)pa; // Fill with junk to catch dangling refs. memset(pa, 1, PGSIZE); acquire(&kmem.lock); r->next = kmem.freelist; kmem.freelist = r; release(&kmem.lock); } else { release(&ref.lock); } } // 初始化内存引用计数为1， void *kalloc(void) { struct run *r; acquire(&kmem.lock); r = kmem.freelist; if(r){ kmem.freelist = r->next; acquire(&ref.lock); ref.cnt[(uint64)r / PGSIZE] = 1; // 将引用计数初始化为1 release(&ref.lock); } release(&kmem.lock); if(r) memset((char*)r, 5, PGSIZE); // fill with junk return (void*)r; }添加如下2个函数，分别用于获取内存的引用计数与增加内存的引用计数
// 获取内存的引用计数 在 cow_alloc 中获取引用计数判断进程数 int krefcnt(void* pa) { return ref.cnt[(uint64)pa / PGSIZE]; } // 增加内存的引用计数 成功返回0 失败返回 -1 在 uvmcopy 中调用 int kaddrefcnt(void* pa) { if(((uint64)pa % PGSIZE) != 0 || (char*)pa < end || (uint64)pa >= PHYSTOP) return -1; acquire(&ref.lock); ref.cnt[(uint64)pa / PGSIZE]++; release(&ref.lock); return 0; }修改
freerangevoid freerange(void *pa_start, void *pa_end) { char *p; p = (char*)PGROUNDUP((uint64)pa_start); for(; p + PGSIZE <= (char*)pa_end; p += PGSIZE) { // 在kfree中将会对cnt[]减1，这里要先设为1，否则就会减成负数 ref.cnt[(uint64)p / PGSIZE] = 1; kfree(p); } }