在实现6.S081 Lab3过程中，需要对xv6页表有一定的掌握，因此写了这份源码分析。
一、基本原理
1 页表介绍
1.1 地址范围
xv6系统是64位的，但是地址只用到了39位：9 9 9 12，地址空间512G，三级页表，页表项占8B，每一页存放512项。
每一个页表项(Page Table Entry)占8B，包含44位物理页号(Phsical Page Number)和10位flag，剩余10位未用，物理地址共44 12=56位。
xv6地址1.2 地址转换
页表是一个中间层，有以下优点：
- 拥有独立的地址空间，隔离性强。
- 支持离散分配、按需分配，内存利用率高。
- 支持进程间共享数据。 地址转换时先从satp寄存器获取页表顶级目录物理地址，然后MMU三次转换，得到最终的物理地址，需要三次访存，故产生TLB来缓存部分页表项减少访存次数。
satp寄存器每个CPU都有一个
地址转换2 内核页表
xv6为每个进程提供了一个用户页表，还有一个全局内核页表。内核页表只会维护内核区域的映射关系，用户页表也只会维护用户区域的映射关系，两者相互独立。用户态切换到内核态时会将内核页表的地址设置到satp寄存器中。
虚拟地址空间虽然有2^39这么大，但其实远远用不了这么多，而且内存编址不仅仅是RAM，还包括CPU寄存器、设备控制器等。RAM范围是在KERNBASE--PHYSTOP这个范围，PHYSTOP最少是0x86400000，xv6中设置为0x88000000，也就是RAM128MB。0--KERNBASE这个范围是给设备与寄存器编址的。
内核区域由以下几部分组成：
- KERNBASE以下，这部分是设备编址。
- Kernel text、kernel data。
- 最后一个进程内核栈kstackn--MAXVA。
内核区域都是直接映射，虚拟地址就是物理地址。
内核页表布局Trampoline： 位于虚拟空间顶端，它在内核区域也直接映射过一次，是用户态跳入内核态的途径，也是内核态返回用户态的必经之路。
kstack： 每个进程都有一个内核栈，并且下面会有一个guard page，guard page不可访问，一旦内核栈溢出到guard page时就会终止。
3 用户页表
用户页表布局所有进程共享全局的内核页表，但每个进程都有一个独立的用户页表。它从0开始，包含进程代码段、数据段、初始栈、堆、trampoline。
栈刚开始只有一页，exec会初始main函数地址、argc、argv。
trampoline在内核页表、用户页表都有，是用于用户态和内核态切换的，涉及到页表地址的设置。
二、main源码分析
1 启动分析
代码语言：c复制// start() jumps here in supervisor mode on all CPUs.
void
main()
{
if(cpuid() == 0){
//控制台输入输出初始化
consoleinit();
printfinit();
printf("n");
printf("xv6 kernel is bootingn");
printf("n");
//物理内存分配器初始化
kinit(); // physical page allocator
//全局内核页表初始化
kvminit(); // create kernel page table
//页表初始化后，开启分页机制
kvminithart(); // turn on paging
//初始化进程表，主要是分配进程内核栈
procinit(); // process table
//初始化tickslock用于时钟中断
trapinit(); // trap vectors
//中断向量
trapinithart(); // install kernel trap vector
plicinit(); // set up interrupt controller
plicinithart(); // ask PLIC for device interrupts
//初始化buffer
binit(); // buffer cache
//初始化inode列表
iinit(); // inode table
fileinit(); // file table
virtio_disk_init(); // emulated hard disk
//初始化init进程
userinit(); // first user process
__sync_synchronize();
//此时只有cpu 0正在运行，其它cpu自旋
started = 1;
} else {
while(started == 0)
;
__sync_synchronize();
printf("hart %d startingn", cpuid());
kvminithart(); // turn on paging
trapinithart(); // install kernel trap vector
plicinithart(); // ask PLIC for device interrupts
}
scheduler();
}这里面初始化了很多spinlock和sleeplock，两者的区别是spinlock是通过一个整数和原子命令来实现，锁内存数据，不能够阻塞。sleeplock是结合spinlock使用的，进程持有锁时可以阻塞，等待被唤醒。
代码语言：c复制// Mutual exclusion lock.
struct spinlock {
uint locked; // Is the lock held?
// For debugging:
char *name; // Name of lock.
struct cpu *cpu; // The cpu holding the lock.
};
struct sleeplock {
uint locked; // Is the lock held?
struct spinlock lk; // spinlock protecting this sleep lock
// For debugging:
char *name; // Name of lock.
int pid; // Process holding lock
};2 物理内存分配
2.1 分配器结构
代码语言：c复制//内存分配器
struct run {
struct run *next;
};
struct {
struct spinlock lock;
struct run *freelist;
} kmem;run表示一块物理页，而每个物理页中起始处保存了下一物理页地址，这样便不需要辅助空间存放分配器，只需要一个kmem固定空间就够了。
2.2 内存分配器初始化
执行kinit函数时还没有开启分页机制，此时使用的是物理地址，而内核中所有全局变量都是在编译时确定地址的，加载到内存后占用的是内核数据段地址，这一段地址不能够分配。
代码语言：c复制void
kinit()
{
initlock(&kmem.lock, "kmem");
//从kernel end后开始收集释放所有物理内存，将它们放入到内存分配器中
//PHYSTOP表示RAM最后的地址
freerange(end, (void*)PHYSTOP);
}
void
freerange(void *pa_start, void *pa_end)
{
char *p;
p = (char*)PGROUNDUP((uint64)pa_start);
for(; p PGSIZE <= (char*)pa_end; p = PGSIZE)
kfree(p);
}
void
kfree(void *pa)
{
struct run *r;
if(((uint64)pa % PGSIZE) != 0 || (char*)pa < end || (uint64)pa >= PHYSTOP)
panic("kfree");
// Fill with junk to catch dangling refs.
memset(pa, 1, PGSIZE);
r = (struct run*)pa;
acquire(&kmem.lock);
r->next = kmem.freelist;
kmem.freelist = r;
release(&kmem.lock);
}2.3 物理页分配和释放
代码语言：c复制void *
kalloc(void)
{
struct run *r;
acquire(&kmem.lock);
r = kmem.freelist;
if(r)
kmem.freelist = r->next;
release(&kmem.lock);
if(r)
memset((char*)r, 5, PGSIZE); // fill with junk
return (void*)r;
}
void
kfree(void *pa)
{
struct run *r;
if(((uint64)pa % PGSIZE) != 0 || (char*)pa < end || (uint64)pa >= PHYSTOP)
panic("kfree");
// Fill with junk to catch dangling refs.
memset(pa, 1, PGSIZE);
r = (struct run*)pa;
acquire(&kmem.lock);
r->next = kmem.freelist;
kmem.freelist = r;
release(&kmem.lock);
}3 内核页表初始化
初始化一个全局的内核页表，会将各个设备寄存器、CPU寄存器、内核代码段、数据段等直接映射到固定位置，具体可以看下一节内核页表源码分析。内核页表初始化后就会开启分页机制，将内核页表地址放入satp寄存器，MMU会自动地址转换。
代码语言：c复制void
kvminithart()
{
w_satp(MAKE_SATP(kernel_pagetable));
//刷新TLB
sfence_vma();
}4 进程表初始化
遍历进程数组，会每个进程分配内核栈，一页物理页，guard page不占物理内存，此时进程处于UNUSED状态。
代码语言：c复制void
procinit(void)
{
struct proc *p;
initlock(&pid_lock, "nextpid");
initlock(&wait_lock, "wait_lock");
for(p = proc; p < &proc[NPROC]; p ) {
initlock(&p->lock, "proc");
p->kstack = KSTACK((int) (p - proc));
}
}三、内核页表源码分析
1 内核页表初始化
代码语言：c复制void
main()
{
if(cpuid() == 0){
//...
kvminit(); // create kernel page table
kvminithart(); // turn on paging
procinit(); // process table
//...
}
}
void
kvminit(void)
{
kernel_pagetable = kvmmake();
}
// Make a direct-map page table for the kernel.
pagetable_t
kvmmake(void)
{
pagetable_t kpgtbl;
kpgtbl = (pagetable_t) kalloc();
memset(kpgtbl, 0, PGSIZE);
// uart registers
kvmmap(kpgtbl, UART0, UART0, PGSIZE, PTE_R | PTE_W);
// virtio mmio disk interface
kvmmap(kpgtbl, VIRTIO0, VIRTIO0, PGSIZE, PTE_R | PTE_W);
// PLIC
kvmmap(kpgtbl, PLIC, PLIC, 0x400000, PTE_R | PTE_W);
// map kernel text executable and read-only.
kvmmap(kpgtbl, KERNBASE, KERNBASE, (uint64)etext-KERNBASE, 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);
// 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);
// map kernel stacks
proc_mapstacks(kpgtbl);
return kpgtbl;
}创建页表就是分配一页物理内存作为最高级页目录，然后将各个设备、寄存器添加到页表上，直接映射，虚拟地址和物理地址都一样。
trampoline是trampoline.S文件的字符数组映射到虚拟地址最高端用于内陷。
2 初始化进程内核栈
上节中kvmmake调用了proc_mapstacks(kpgtbl)来初始化进程内核栈，具体过程是在trampoline以下依次为每个进程分配一页物理内存作为内核栈，并且会留下一页作为guard page，不会分配物理内存。
代码语言：c复制// Allocate a page for each process's kernel stack.
// Map it high in memory, followed by an invalid
// guard page.
void
proc_mapstacks(pagetable_t kpgtbl) {
struct proc *p;
for(p = proc; p < &proc[NPROC]; p ) {
char *pa = kalloc();
if(pa == 0)
panic("kalloc");
uint64 va = KSTACK((int) (p - proc));
kvmmap(kpgtbl, va, (uint64)pa, PGSIZE, PTE_R | PTE_W);
}
}3 添加页表项
代码语言：c复制// add a mapping to the kernel page table.
// only used when booting.
// does not flush TLB or enable paging.
// va表示虚拟地址，pa是物理地址
void
kvmmap(pagetable_t kpgtbl, uint64 va, uint64 pa, uint64 sz, int perm)
{
if(mappages(kpgtbl, va, sz, pa, perm) != 0)
panic("kvmmap");
}
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)
return -1;
if(*pte & PTE_V)
panic("mappages: remap");
//修改该页表项的标志，设置物理页地址
*pte = PA2PTE(pa) | perm | PTE_V;
if(a == last)
break;
a = PGSIZE;
//物理空间连续分配，所以只能用于内核初始化映射
pa = PGSIZE;
}
return 0;
}
// A 64-bit virtual address is split into five fields:
// 39..63 -- must be zero.
// 30..38 -- 9 bits of level-2 index.
// 21..29 -- 9 bits of level-1 index.
// 12..20 -- 9 bits of level-0 index.
// 0..11 -- 12 bits of byte offset within the page.
pte_t *
walk(pagetable_t pagetable, uint64 va, int alloc)
{
if(va >= MAXVA)
panic("walk");
for(int level = 2; level > 0; level--) {
pte_t *pte = &pagetable[PX(level, va)];
//如果该页表项存在，则往下级页目录走
if(*pte & PTE_V) {
pagetable = (pagetable_t)PTE2PA(*pte);
} else {
//如果该页表项不存在，则分配物理页
if(!alloc || (pagetable = (pde_t*)kalloc()) == 0)
return 0;
memset(pagetable, 0, PGSIZE);
*pte = PA2PTE(pagetable) | PTE_V;
}
}
return &pagetable[PX(0, va)];
}
#define PXMASK 0x1FF // 9 bits
#define PXSHIFT(level) (PGSHIFT (9*(level)))
//获取对应level的目录号，PXMASK取低10位
#define PX(level, va) ((((uint64) (va)) >> PXSHIFT(level)) & PXMASK)
//先左移掉10位标志位，再右移流出页內偏移
#define PTE2PA(pte) (((pte) >> 10) << 12)四、用户页表源码分析
1 用户页表初始化
进程调用fork系统调用时会创建分配一个UNUSED进程控制块，然后设置唯一的pid，创建页表、拷贝页表、文件，最后将新进程修改为就绪态。创建用户页表会经历以下几步。
代码语言：c复制// Create a user page table for a given process,
// with no user memory, but with trampoline pages.
pagetable_t
proc_pagetable(struct proc *p)
{
pagetable_t pagetable;
// An empty page table.
//分配一页作为最高级页目录，物理地址
pagetable = uvmcreate();
if(pagetable == 0)
return 0;
// map the trampoline code (for system call return)
// at the highest user virtual address.
// only the supervisor uses it, on the way
// to/from user space, so not PTE_U.
//用户页表最高处是trampoline，用于中断，不属于用户
if(mappages(pagetable, TRAMPOLINE, PGSIZE,
(uint64)trampoline, PTE_R | PTE_X) < 0){
uvmfree(pagetable, 0);
return 0;
}
//内陷帧
// 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;
}
//设置一些静态字段，用于加速部分系统调用，减少上下文切换
if(mappages(pagetable, USYSCALL, PGSIZE,
(uint64)p->usyscall, PTE_R | PTE_U) < 0){
uvmunmap(pagetable, USYSCALL, 1, 0);
uvmfree(pagetable, 0);
return 0;
}
return pagetable;
}2 用户页表遍历
代码语言：c复制//返回物理地址
uint64
walkaddr(pagetable_t pagetable, uint64 va)
{
pte_t *pte;
uint64 pa;
if(va >= MAXVA)
return 0;
pte = walk(pagetable, va, 0);
if(pte == 0)
return 0;
if((*pte & PTE_V) == 0)
return 0;
if((*pte & PTE_U) == 0)
return 0;
pa = PTE2PA(*pte);
return pa;
}
//返回页表项
pte_t *
walk(pagetable_t pagetable, uint64 va, int alloc)
{
if(va >= MAXVA)
panic("walk");
//三次循环，每次下移一级
for(int level = 2; level > 0; level--) {
//PX用于获取对应级别页表的目录
pte_t *pte = &pagetable[PX(level, va)];
//如果该页表项存在，则往下级页目录走
if(*pte & PTE_V) {
pagetable = (pagetable_t)PTE2PA(*pte);
} else {
//如果该页表项不存在，则分配物理页，单纯的遍历不需要分配新的页表项
if(!alloc || (pagetable = (pde_t*)kalloc()) == 0)
return 0;
memset(pagetable, 0, PGSIZE);
*pte = PA2PTE(pagetable) | PTE_V;
}
}
return &pagetable[PX(0, va)];
}3 释放页表
代码语言：c复制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);
}
void
uvmfree(pagetable_t pagetable, uint64 sz)
{
if(sz > 0)
uvmunmap(pagetable, 0, PGROUNDUP(sz)/PGSIZE, 1);
freewalk(pagetable);
}
//释放物理页，并设置页表项为0
void
uvmunmap(pagetable_t pagetable, uint64 va, uint64 npages, int do_free)
{
uint64 a;
pte_t *pte;
if((va % PGSIZE) != 0)
panic("uvmunmap: not aligned");
for(a = va; a < va npages*PGSIZE; a = PGSIZE){
if((pte = walk(pagetable, a, 0)) == 0)
panic("uvmunmap: walk");
if((*pte & PTE_V) == 0)
panic("uvmunmap: not mapped");
if(PTE_FLAGS(*pte) == PTE_V)
panic("uvmunmap: not a leaf");
if(do_free){
//释放每一个页表项
uint64 pa = PTE2PA(*pte);
kfree((void*)pa);
}
*pte = 0;
}
}
//释放页表本身的辅助空间
void
freewalk(pagetable_t pagetable)
{
// there are 2^9 = 512 PTEs in a page table.
for(int i = 0; i < 512; i ){
pte_t pte = pagetable[i];
//表示不为叶结点， 叶结点PTE_R|PTE_W|PTE_X至少占一个
if((pte & PTE_V) && (pte & (PTE_R|PTE_W|PTE_X)) == 0){
// this PTE points to a lower-level page table.
uint64 child = PTE2PA(pte);
freewalk((pagetable_t)child);
pagetable[i] = 0;
} else if(pte & PTE_V){
panic("freewalk: leaf");
}
}
kfree((void*)pagetable);
}
