MIT 6.828 操作系统课程系列3 Page tables#
https://pdos.csail.mit.edu/6.828/2022/labs/pgtbl.html
本次lab需要读xv6手册第3章。看相关kernel代码。
理解页表的原理并实现一些相关功能。
页表的作用是通过地址映射，使得每个进程看上去拥有自己独立的地址空间和内存，但实际是所有进程共用一套物理内存和地址。
页表定义了内存地址，决定哪些物理地址能被访问。
分页硬件#
riscv指令(user和kernel)都只操作虚拟地址。riscv分页硬件会把虚拟地址映射到实际地址。
xv6系统只会用到64bit的虚拟地址里的低39bit(Sv39方案)。见riscv文档。
39bit中的高27bit用来对应一个页表项(page table entries(PTE))。一共2^27=134217728个PTE。
Sv39方案的分页粒度为4096(4k)字节。
低12bit，2^12=4096，正好表示一页中的offset。1层结构
每个PTE为64bit，包含一个44bit的物理页号physical page number(PPN)，一些标志位，和一些备用的bit。
分页硬件用虚拟地址39bit里的高27bit查到一个PTE，再把PTE里的PPN(44bit)和原始虚拟地址的后12bit(39 - 27)拼起来组成一个56bit的物理地址。每个PTE映射一页4k字节，一共134217728个
PTE，理论上可支持的最大内存为134217728 * 4k = 512g字节。
每个PTE映射到一个物理页的首地址。
我们实际模拟使用128m内存。那么最多只用到12810241024/4096=32768个PTE。3层结构
上面说的用高27bit查PTE，存在三级树形结构里，每层刚好512项。
前9bit对应第一级的index，中9bit对应第二级的index，后9bit对应第三级的index。
2 ^ 9 = 512。512 * 512 * 512 = 134217728。总数不变。
只要有一级找不到，就会报page-fault异常，交给kernel处理。页表本身需要内存
一个pte为64bit，8字节。一级512个pte就是4k字节，正好一页。
所以如果整个页表都填满，三层页表本身需要4k + 512*4k + 512*512*4k = 1g或者134217728*8 = 1g内存。多层结构相比1层的好处，省资源。
比如我现在只需要分配1个页。如果没有其他手段的话，1层结构必须把所有134217728个pte都分配好。
而3层的话。只需分配第一层的512个pte，第二层的512个pte，和的三层的512个pte即可。
省去了第二层的511*4k和第三层的511*512*4k。多层可能的坏处。cpu需要load三个PTE来做转换。
riscv用Translation Look-aside Buffer(TLB)来缓解这个问题。PTE里有十个左右的各种标志位。
PTE_VPTE是否存在
PTE_R是否允许读
PTE_W是否允许写
PTE_X是否允许cpu执行
PTE_Uuser模式下指令是否能读写Supervisor Address Translation and Protection (satp) Register
riscv cpu的satp寄存器控制地址转换。使用时必须把根PPN地址交给它。
每个cpu都有自己的satp，可以独立处理地址转换。
kernel地址空间#
xv6给每个进程维护一个user空间的页表
kernel空间有一个单独的页表
kernel会给自己的地址空间做详细的配置，比如哪些资源映射到哪些虚拟地址。见memlayout.h。qemu
qemu为我们的模拟的物理内存从0x80000000开始到0x88000000，一共128m(见memlayout.h，从KERNBASE到PHYSTOP)。
也会模拟io设备比如磁盘。qemu把设备接口做成内存映射(0x88000000以下)的寄存器暴露给软件。
kernel通过读写这些地址跟设备交互。kernel获取设备地址是用的”直接映射”，即虚拟地址和实际地址一样。直接映射就省去了转换操作，很多场景会用到。
仔细看下手册图3.3，kernel的地址空间。
MAXVA为0x4000000000(256G字节)。虚拟地址的寻址空间为0->(0x4000000000-1)
KERNBASE为0x80000000(2G字节)。之前的都是kernel特殊使用。
PHYSTOP为0x88000000，与KERNBASE之间的128M为实际的可用内存。
其中KERNBASE开始存kernel代码和数据。
kernel的代码和数据的末尾定义为end(见kalloc.c)。实际在kernel.ld中定义。
end到PHYSTOP就是被内存管理系统控制(通过kalloc/kfree)的内存(见kalloc.c)。就是图中的freememory。
用户进程分配到的物理内存都是分布在freememory里。虽然寻址空间都是0->(0x4000000000-1)。
创建地址空间#
上个lab已经看了kalloc相关流程。所有物理页做成了一个list。
仔细看它的结构，是有点东西的。struct run结构里只有一个next指针，把pa强转成struct run*来操作。
这样搞其是直接把这个list放在物理内存了。而不是在kernel栈里维护对应关系。确实省了大批资源。
可以发现默认代码的一些问题。初始化后是一个好的list没问题。
当对一个地址kalloc后这个一页就从list中去除了。必须对其kfree才能让它回来，否则永远丢失。
另外，如果对一个free状态的页再kfree，会破坏list的结构，可造成崩溃。看页表相关代码
vm.c
主要的数据pagetable_t是一个uint64 *看懂
walk函数
pte_t *walk(pagetable_t pagetable, uint64 va, int alloc)
给一个pagetable头地址，一个虚拟地址va，一个alloc选项。
返回va的物理地址。
typedef uint64 pte_t;
typedef uint64 *pagetable_t; // 512 PTEs
pte_t *
walk(pagetable_t pagetable, uint64 va, int alloc)
{
if(va >= MAXVA) // MAXVA = 0x4000000000
panic("walk"); // 跑飞了
for(int level = 2; level > 0; level--) { // 三级循环
pte_t *pte = &pagetable[PX(level, va)];
// #define PX(level, va) ((((uint64) (va)) >> PXSHIFT(level)) & PXMASK)
// #define PXSHIFT(level) (PGSHIFT+(9*(level)))
// #define PXMASK 0x1FF // 9 bits
// PX把va按层数右移再取9位。也就是取对应级数的PTE。
if(*pte & PTE_V) { // 如果此PTE有效
pagetable = (pagetable_t)PTE2PA(*pte);
// #define PTE2PA(pte) (((pte) >> 10) << 12)
// 右移10bit取PPN。左移12bit得到物理地址。走下一层。
} else {
// 页表数据本身也占用物理内存。
// 如果不分配，直接返回。
// 否则kalloc分配一页。并且置PTE_V。继续走下一层
if(!alloc || (pagetable = (pde_t*)kalloc()) == 0)
return 0;
memset(pagetable, 0, PGSIZE);
*pte = PA2PTE(pagetable) | PTE_V;
// #define PA2PTE(pa) ((((uint64)pa) >> 12) << 10)
// 右移12bit取PPN。左移10bit组成PTE值。置PTE_V。走下一层。
}
}
return &pagetable[PX(0, va)];
}
页对齐
目的是方便兼容不同硬件和提高效率，不对齐会有额外的io开销。
两个计算对齐地址的宏:
PGROUNDDOWN把地址往下对齐一页，不满一页的值抹掉，比如0x1003会变成0x1000。
PGROUNDUP把地址往上对齐一页，只要超出1就会往上走一页，比如0x1001会变成0x2000。
如果正好是对齐的地址比如0x1000，都不会发生改变。看懂
mappages函数
给一个pagetable头地址，一个虚拟地址va，一个数size，一个物理地址pa， 一个配置项perm。
更新页表里的项，给定size，对于从va和pa开始的size个字节(以页分组)，va和pa地址一一对应，把映射关系安装到页表。
把va和va+size对齐一下分别作为头尾。开始循环。
对于其间的每个虚拟地址，调walk得到其PTE位置，再把物理地址pa转成PTE赋值到页表。每次循环va和pa都往后走一页。
要注意这个映射是针对对齐的页的首地址。并不是针对size范围内所有单个地址。
int mappages(pagetable_t pagetable, uint64 va, uint64 size, uint64 pa, int perm)
{
uint64 a, last;
pte_t *pte;
if(size == 0)
panic("mappages: size");
a = PGROUNDDOWN(va); // 往下对齐
last = PGROUNDDOWN(va + size - 1); // 算出最后涉及的页
for(;;){
if((pte = walk(pagetable, a, 1)) == 0) // 找到PTE
return -1;
if(*pte & PTE_V) // 如果已经设置过。报错。
panic("mappages: remap");
*pte = PA2PTE(pa) | perm | PTE_V; // 设置为PTE值。置PTE_V和perm选项。
if(a == last)
break;
a += PGSIZE;
pa += PGSIZE;
}
return 0;
}
kvmmap()用mappages把映射关系安装到kernel的页表。
在main()里kvminit()用kvmmap安装一系列硬件等映射。这个发生在页表使能之前，所以地址都是物理地址。
void
kvminit(void)
{
kernel_pagetable = kvmmake();
pagetable_t kpgtbl;
kpgtbl = (pagetable_t) kalloc(); // 新物理页
memset(kpgtbl, 0, PGSIZE);
// uart registers
kvmmap(kpgtbl, UART0, UART0, PGSIZE, PTE_R | PTE_W); // UART0虚拟地址映射到相同的物理地址
// virtio mmio disk interface
kvmmap(kpgtbl, VIRTIO0, VIRTIO0, PGSIZE, PTE_R | PTE_W); // VIRTIO0虚拟地址映射到相同的物理地址
// PLIC
kvmmap(kpgtbl, PLIC, PLIC, 0x400000, PTE_R | PTE_W); // PLIC虚拟地址映射到相同的物理地址
// map kernel text executable and read-only.
kvmmap(kpgtbl, KERNBASE, KERNBASE, (uint64)etext-KERNBASE, PTE_R | PTE_X);
// KERNBASE为0x80000000。etext在kernel.ld中定义。为.text的末尾。
// 看kernel.ld
// . = 0x80000000; // 从0x80000000开始
// .text : {
// *(.text .text.*) // 指令数据
// . = ALIGN(0x1000); // 对齐到下个4k字节
// _trampoline = .; // _trampoline设为当前地址
// *(trampsec) // trampsec放到这里。trampsec为整个trampoline.S。
// . = ALIGN(0x1000); // 对齐到下个4k字节
// // 检查_trampoline大小。不能超过1页。
// ASSERT(. - _trampoline == 0x1000, "error: trampoline larger than one page");
// PROVIDE(etext = .); // 输出etext
// }
// 最后效果是把kernel代码从0x80000000起映射到相同的地址。
// PTE_R | PTE_X设置为可读可执行
// map kernel data and the physical RAM we'll make use of.
kvmmap(kpgtbl, (uint64)etext, (uint64)etext, PHYSTOP-(uint64)etext, PTE_R | PTE_W);
// PHYSTOP为0x80000000开始的128M处
// 128M中从etext开始的剩余部分映射到相同的地址
// 作为主要的内存。可读可写
// 这样的效果就是在S模式下或kernel空间中，一般都是直接操作物理地址。
// map the trampoline for trap entry/exit to
// the highest virtual address in the kernel.
kvmmap(kpgtbl, TRAMPOLINE, (uint64)trampoline, PGSIZE, PTE_R | PTE_X);
// TRAMPOLINE = MAXVA - PGSIZE
// trampoline是trampoline.S的label。是指令地址。
// 效果是把虚拟地址的最后一页映射到汇编中的trampoline函数。
// 可读可执行
// allocate and map a kernel stack for each process.
proc_mapstacks(kpgtbl);
// 所有进程的kstack排在虚拟地址末尾处
for(p = proc; p < &proc[NPROC]; p++)
char *pa = kalloc();
uint64 va = KSTACK((int) (p - proc));
kvmmap(kpgtbl, va, (uint64)pa, PGSIZE, PTE_R | PTE_W);
return kpgtbl;
}
进程地址空间#
每个进程有独立的页表，当进程发生切换时同时会切换页表。
见图2.3。进程的用户内存从0开始到MAXVA(riscv.h)，一共是256G字节大小。进程向xv6内核请求更多内存时，xv6用kalloc分配物理页。然后往页表中插入PTE项(指向新分配的物理地址)(就是把映射关系装进页表)。
通过巧妙的设计，不同进程的虚拟地址会映射到不同的物理地址，不会相互干扰。进程自己可见的内存地址时连续的，虽然实际对应的物理地址是散乱的。
整理一下内存和分页相关的函数
函数 |
功能 |
|---|---|
kalloc |
分配一页1k字节物理内存 |
kfree |
回收一页1k字节物理内存 |
freerange |
用kfree回收范围内物理内存。 |
walk |
在页表中找虚拟地址对应的PTE地址(可选是否为未分配内存的PTE分配内存) |
freewalk |
递归形式。用kfree回收整个页表本身。 |
mappages |
往页表中安装虚拟地址-物理地址的对应关系。如果PTE没分配内存，分配内存(页表本身占用内存)。 |
kvmmap |
用mappages把地址对应关系安装到kernel的页表 |
uvmunmap |
把页表里从虚拟地址va开始的n个page的对应关系删除(可选是否kfree物理地址) |
uvmcreate |
用kalloc分配一页，创建一个空页表。4k字节清零，此时第一级512个pte都是无效状态。 |
uvmdealloc |
给定新老内存size，用uvmunmap删除其间的va对应关系(可选是否回收内存)。 |
uvmalloc |
给定新老内存size。遍历老size到新size之间的页，每个页先kalloc分配物理内存，再mappages安装到页表。 |
copyout |
把数据从物理地址copy到虚拟地址对应的物理地址 |
copyin |
把数据从虚拟地址对应的物理地址copy到物理地址 |
uvmfree |
用uvmunmap删除页表中从0开始n个地址的对应关系(同时kfree每页的物理地址)。再freewalk删除页表本身。 |
uvmcopy |
给定新老两个页表和size，把老页表0开始到size的虚拟地址的数据复制到新页表。从0开始的每一页虚拟地址，找到老表的PTE、物理地址，kalloc分配一页，把物理地址上的数据复制到新分配的页，再用mappages把虚拟地址和新分配的页安装到页表。 |
uvmfirst |
特殊操作。分配第一页，做映射，并把数据复制进去。 |
sbrk#
sbrk改变program break的位置，改变了进程的数据段。program break变大的效果就是增大了进程的内存，反之减小。
看xv6的sbrk，直接调用growproc(n)来增减内存。
如果n大于0，用uvmalloc增加。
如果n小于0，用uvmdealloc减小。
相关的函数基本都建立在之前看过的kfree/kalloc/walk/mappages基础之上。
sys_sbrk
uint64 addr;
int n;
argint(0, &n);
addr = myproc()->sz; //返回初始sz。也就是新内存的起始位置。
if(growproc(n) < 0)
int growproc(int n)
uint64 sz;
struct proc *p = myproc();
sz = p->sz;
if(n > 0){
if((sz = uvmalloc(p->pagetable, sz, sz + n, PTE_W)) == 0) {
// 内存从sz增加n
uint64 uvmalloc(pagetable_t pagetable, uint64 oldsz, uint64 newsz, int xperm)
char *mem;
uint64 a;
if(newsz < oldsz)
return oldsz;
oldsz = PGROUNDUP(oldsz); // 往后对齐
for(a = oldsz; a < newsz; a += PGSIZE){ // 一页页分配
mem = kalloc(); // 申请物理内存
if(mem == 0){
uvmdealloc(pagetable, a, oldsz);
return 0;
}
memset(mem, 0, PGSIZE); // 数据清零
// 把a也就是虚拟地址va，映射到物理内存地址mem。
// 以后用户操作这个va，实际就是操作mem。
if(mappages(pagetable, a, PGSIZE, (uint64)mem, PTE_R|PTE_U|xperm) != 0){
kfree(mem);
uvmdealloc(pagetable, a, oldsz);
return 0;
}
}
return newsz;
return -1;
}
} else if(n < 0){
// 反向操作。缩小内存。
sz = uvmdealloc(p->pagetable, sz, sz + n);
if(newsz >= oldsz)
return oldsz;
if(PGROUNDUP(newsz) < PGROUNDUP(oldsz)){
int npages = (PGROUNDUP(oldsz) - PGROUNDUP(newsz)) / PGSIZE;
// 清除映射并kfree
uvmunmap(pagetable, PGROUNDUP(newsz), npages, 1);
}
}
// 更新sz
p->sz = sz;
return 0;
return -1;
// 返回初始sz。也就是新内存的起始位置。
return addr;
用户代码malloc申请内存就是走sbrk。
做题1.Speed up system calls#
默认kernel传数据回user需要复制数据。现约定一个USYSCALL虚拟地址，每个进程分配一页映射这个地址，把pid存上去。user直接取数据就行。
仿照p->trapframe做一页数据存usyscall即可
做题2.打印页表#
vm.c里做一个函数vmprint，给定页表头和level，打印出页表所有非空的PTE和物理地址。插到exec函数返回前。
参考freewalk做一个递归打印每个PTE，依靠level填上前缀即可。
或者整三个循环也可。用make grade测试，测试通过会打印出：pte printout: OK
做题3.Detect which pages have been accessed#
把虚拟地址的PTE找到查看PTE_A并记录。最后返给user即可。
相比2020版本的lab。2022的有简化。