[MIT6.S081] 难起来了呀 · Lab3 · page tables

La3b 讲义

源码阅读

在开始coding前，应该先阅读以下源码：

1. kernel/memlayout.h

memlayout.h定义了一些物理地址，反映了内存的布局。
在0x8000 0000L 以下是其它设备，例如I/O设备。内核可以通过读写这些物理地址来与这些设备互动。

在0x8000 0000L 以上地址是RAM，由 KERNBASE 到 PHYSTOP，共128MB

#define KERNBASE 0x8000000L
#define PHYSTOP (KERNBASE + 128*1024*1024)

2. kernel/vm.c

vm.c包含了大部分与虚拟内存相关的代码。
![[pic_3lev_pt.png]]
区分一下pagetable相关的一些变量的类型与作用：
一个page directory（代码里为pagetable）实际上是一个存放在物理内存中的长度为512数组，总大小为$512\times 8Byte = 4kB$
三级页表则是物理内存中一组page directory。
pagetable_t是指针，指向长度为512的数组，每个元素是一个页表项pte_t，一个页表项的内容是一个64位的无符号整数;

// @brief: 模拟mmu功能
// @prama: pagetable 页表, va 虚拟地址, alloc 
pte_t * walk(pagetable_t pagetable, uint64 va, int alloc) {
	if(va >= MAXVA)
		panic("walk");
	// 处理 level2 level1 页表
	for(int level = 2; level > 0; level--) {
		// pte_t *pte 指向 pagetable的一个页表项
		pte_t *pte = &pagetable[PX(level, va)];
		// 如果&pagetable[PX(level, va)]不指向NULL并且设置了PTE_V
		if(*pte & PTE_V) {
			// 将pte的内容转换为物理地址，得到下一级页表地址
			pagetable = (pagetable_t)PTE2PA(*pte);
		} 
		// 否则
		else {
			if(!alloc || (pagetable = (pde_t*)kalloc()) == 0)
				return 0;
			// 将该页表的内容全设置为0
			memset(pagetable, 0, PGSIZE);
			// 将该页表项 并 设置并设置PTE_V
			*pte = PA2PTE(pagetable) | PTE_V;
		}
	}
	// 返回 指向level0页表中对应的表项的指针
	return &pagetable[PX(0, va)];
}

kernel/riscv.h
注：使用宏而不是函数来实现一些简单的功能，能够提升内核的效率，但同时也会导致编译后的代码膨胀。这一点与C++的inline有相似之处。

// 页表项与物理地址的转换
// 还未理解这是怎么转换的
#define PA2PTE(pa) ((((uint64)pa) >> 12) << 10)
#define PTE2PA(pte) (((pte) >> 10) << 12)


#define PXMASK 0x1FF // 9 bits
#define PGSHIFT 12 // bits of offset within a page
#define PXSHIFT(level) (PGSHIFT+(9*(level)))
// 根据level的值，将va左移(12+9*level)，取最后九位
#define PX(level, va) ((((uint64) (va)) >> PXSHIFT(level)) & PXMASK)
#define MAXVA (1L << (9 + 9 + 9 + 12 - 1))

typedef uint64 pte_t;
// pagetable_t是指向uint64类型的指针，且是指向一个长度为512的uint64数组的指针
// 每个元素是一个页表项，即pte_t
typedef uint64 *pagetable_t; // 512 PTEs

3. kernel/kalloc.c

kalloc.c包含了用来分配和释放物理内存的代码
注意：kalloc.c只收分配理内存中内核后之后的内存空间，即内核虚拟地址中Free Memory的部分
每次分配和释放一整个页(4096-byte)。
在使用kalloc()为进程分配空间时候，已经使用了页表，为什么还能使用物理内存地址？这是为进程分配内存时候，是使用的内核页表，内核页表使用了恒等映射。
![[pic_kernel_table.png]]

void freerange(void *pa_start, void *pa_end);

extern char end[]; // 内核后的第一个





struct run {
	struct run *next;
};
  
struct {
	struct spinlock lock;
	struct run *freelist;
} kmem;
  
void kinit() {
	initlock(&kmem.lock, "kmem");
	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);
}

// Free the page of physical memory pointed at by v,
// which normally should have been returned by a
// call to kalloc(). (The exception is when
// initializing the allocator; see kinit above.)
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);
}

// Allocate one 4096-byte page of physical memory.
// Returns a pointer that the kernel can use.
// Returns 0 if the memory cannot be allocated.
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;
}

kernel.ld

SECTIONS
{
	// 将当前位置设置为 0x80000000，确保 `entry.S` 文件中的 `_entry` 符号位于该地址处，
	// 以便 qemu 的 `-kernel` 参数跳转到这个地址运行。
	. = 0x80000000;
	//  将 `end` 符号定义为当前位置，表示整个程序的结束地址
	PROVIDE(end = .);
}

Print a page table (easy)

搞清楚了页表的原理和各个变量的意义，这题蛮简单的。
可以从三级页表中看到，pid=1的进程一共使用了5个物理页，加上用户页表占据一个物理页，一共占据了$6 \times 4Kb = 24Kb$的物理内存空间。
Level 2 页表的第0个表项和第255个表项是有设置的，

Q:Explain the output of vmprint in terms of Fig 3-4 from the text. What does page 0 contain? What is in page 2? When running in user mode, could the process read/write the memory mapped by page 1?

page table 0x0000000087f64000
..0: pte 0x0000000021fd8001 pa 0x0000000087f60000
.. ..0: pte 0x0000000021fd7c01 pa 0x0000000087f5f000
.. .. ..0: pte 0x0000000021fd841f pa 0x0000000087f61000
.. .. ..1: pte 0x0000000021fd780f pa 0x0000000087f5e000
.. .. ..2: pte 0x0000000021fd741f pa 0x0000000087f5d000
..255: pte 0x0000000021fd8c01 pa 0x0000000087f63000
.. ..511: pte 0x0000000021fd8801 pa 0x0000000087f62000
.. .. ..510: pte 0x0000000021fed807 pa 0x0000000087fb6000
.. .. ..511: pte 0x0000000020001c0b pa 0x0000000080007000

A:
1.上面显示的L0页目录的page0是进程的text和data，page1 是guard page，page2 是 stack。
2.不能。由page1的pte可以看到其flag的低八位是0x0f，即PTE_U位为0，user不能访问。

A kernel page table per process (hard)

由于现在内核页表没有包括用户进程的虚拟地址到物理地址的映射，因此如果内核需要使用用户在系统调用中传递的指针，则内核就必须先将该指针转化为物理地址，而本题和下一题的目的是让内核能够直接对用户指针解引用。

要实现该需求，我们就要将用户使用的映射保存到内核页表(kernel_pagetable)中。但若直接在kernel_pagetable中保存每一个用户的映射，则在进程结束时，都还需要先释放掉那部分映射，这就要求还得记录每个进程在kernel_pagetable中的映射（也许还有其它坏处，但还未想到）。更好的做法是为每个进程维护一张内核页表（process’s kernel pagetable），每次执行一个进程时，就将该进程的内核页表加载到satp寄存器中（原来是加载只有一张的那个内核页表），如果没有处于RUNNABLE状态的进程，则加载kernel_pagetable。

几个小细节：

1. 每个进程维护的内核页表都是独立的，而不是物理内存中的同一张内核页表，也就是说要为每个process’s kernel pagetable 分配物理内存空间来存放。
2. 为什么不在初始化进程表的时候(即在procinit()中)就将user’s kernel_pagetable也分配好？后续就不需要在每次分配进程时重新获取user’s kernel_pagetable，也不需要在释放进程时释放user’s kernel_pagetable了。可能是因为这样的实现会占据过多的物理内存空间。
3. 在修改前的代码中，每个进程的内核栈在xv6启动，初始化进程表(procinit())时就分配好了。之所以可以提前分配好，是因为在修改前的实现中，所有进程在调用系统调用，进入内核空间时，都是使用的同一张内核页表(kernel_pagetable)，因此对于每个进程而言，其内核栈地址映射都是保存到同一张页表中的，具体而言就是kvmmap()函数。但在修改后的代码中，每个进程使用的就不是同一张页表了，因此需要在分配好process’s kernel pagetable 后再将内核栈的映射保存到该页表中。
4. 在使能页表后，cpu的指令中使用的都是虚拟地址，通过MMU转换为物理地址。为什么在使能页表后，还能对物理内存进行分配？这是因为在使能页表前，可分配的物理内存以链表的结构记录下来了？
5. 讲义中的一个hint: ” You’ll need a way to free a page table without also freeing the leaf physical memory pages.”是什么意思？”你们需要一个方法来释放页表但不是否叶子物理内存页”。意思是释放页表的时候，不释放页表映射的物理内存空间。为什么不需要释放叶子物理内存页？对于用户进程而言，当用户进程运行结束，就需要释放其占用的所有内存空间。但对于内核页表来说，其映射了内核占用的物理地址。因此释放内核页表时，只需要将存储内核页表的物理内存空间释放掉即可。

还有some details about the code:

1. 修改前，内核页表维护了内核栈

// 设置内核页表在虚拟内存中的位置
// kernel/proc.c
uint64 va = KSTACK((int) (p - proc));
// kernel/memlayout.h
#define KSTACK(p) (TRAMPOLINE - ((p)+1)* 2*PGSIZE)

scheduler cpu调度函数，可见使用的是简单的round robin算法进行进程调度。

void scheduler(void) {
	struct proc *p;
	struct cpu *c = mycpu();
	c->proc = 0;
	for(;;){
		// Avoid deadlock by ensuring that devices can interrupt.
		intr_on();
		int found = 0;
	
		for(p = proc; p < &proc[NPROC]; p++) {	
			acquire(&p->lock);
			if(p->state == RUNNABLE) {
				// Switch to chosen process. It is the process's job
				// to release its lock and then reacquire it
				// before jumping back to us.	
				p->state = RUNNING;
				c->proc = p;
				swtch(&c->context, &p->context);
				
				// 进程执行完毕
				c->proc = 0;
				found = 1;
			}
			release(&p->lock);
		}
	}
}

swtch的作用是在任务切换时保存和加载寄存器状态，以便恢复任务执行时的上下文。
原理:将当前寄存器状态保存到old结构体中，并从new结构体中加载寄存器状态。
具体实现：将寄存器的值保存到old结构体的相应偏移位置，然后从new结构体的相应偏移位置加载寄存器的值。在保存和加载寄存器时，使用了sd（store doubleword）和ld（load doubleword）指令。
doubleword是双字，在risc-v中是64bits。
最后，通过ret指令返回到调用该函数的位置。

kernel/swtch.S

# Context switch
#   void swtch(struct context *old, struct context *new);
# Save current registers in old. Load from new.	





# 将base寄存器中的值加上offset，得到内存地址，将rs寄存器中的值保存在该内存中
# sd rs, offset(base)
# 将base寄存器中的值加上offset，得到内存地址，将该内存中值加载到rd寄存器中
# ld rd, offset(base)

# a0寄存器中保存了old结构体的地址，a1保存了new结构体的地址
.globl swtch
swtch:
        sd ra, 0(a0)
        sd sp, 8(a0)
        sd s0, 16(a0)
        sd s1, 24(a0)
        sd s2, 32(a0)
        sd s3, 40(a0)
        sd s4, 48(a0)
        sd s5, 56(a0)
        sd s6, 64(a0)
        sd s7, 72(a0)
        sd s8, 80(a0)
        sd s9, 88(a0)
        sd s10, 96(a0)
        sd s11, 104(a0)

        ld ra, 0(a1)
        ld sp, 8(a1)
        ld s0, 16(a1)
        ld s1, 24(a1)
        ld s2, 32(a1)
        ld s3, 40(a1)
        ld s4, 48(a1)
        ld s5, 56(a1)
        ld s6, 64(a1)
        ld s7, 72(a1)
        ld s8, 80(a1)
        ld s9, 88(a1)
        ld s10, 96(a1)
        ld s11, 104(a1)
        
        ret

遇到的一些bugs:

1.进程中没有维护完整的kernel pagetable
现象：

> make CPUS=1 qemu
*** Now run 'gdb' in another window.
qemu-system-riscv64 -machine virt -bios none -kernel kernel/kernel -m 128M -smp 1 -nographic -drive file=fs.img,if=none,format=raw,id=x0 -device virtio-blk-device,drive=x0,bus=virtio-mmio-bus.0 -S -gdb tcp::26000





xv6 kernel is booting




scause 0x000000000000000d
sepc=0x0000000080001072 stval=0x1414141414141ff8
panic: kerneltrap

分析：通过查看kernel/kernel.asm可以得知出错位置是在walk()函数中。通过gdb调试，发现kernel/main.c的main调用userinit()，userinit()调用allocproc()。最后在allocproc()函数的分配内核栈的代码块中出错，具体而言是以下语句出错：

if(mappages(p->kernel_pagetable, va, PGSIZE, (uint64)pa, PTE_R | PTE_W) != 0)
	panic("ukvmmap");

检查发现是在kvminit()中，只将kernel_pagetable L2页表的第一个页表项复制给了process’s kernel pagetable，如下：

if(kernel_pagetable != 0) {
	pagetable_t proc_kernel_pagetable = (pagetable_t) kalloc();
	*proc_kernel_pagetable = *kernel_pagetable;
	return proc_kernel_pagetable;
}

修改：仿照kernel_pagetable的初始化方法，新增ukvminit()和ukvmmap()两个函数，为process’s kernel pagetable也进行完全一致的初始化。

2.在分配内核栈前就设置了进程的sp寄存器
现象：卡住在xv6 kernel is booting输出后

make CPUS=1 qemu


qemu-system-riscv64 -machine virt -bios none -kernel kernel/kernel -m 128M -smp 1 -nographic -drive file=fs.img,if=none,format=raw,id=x0 -device virtio-blk-device,drive=x0,bus=virtio-mmio-bus.0



xv6 kernel is booting

分析：
通过gdb可以看到xv6在调用scheduler()中调用swtch()后返回到forkret()，然后就卡住了。看到汇编语句，是卡住在了0x80001bca的语句。

│   0x80001bc8 <forkret>    addi    sp,sp,-16                                
│  >0x80001bca <forkret+2>  sd      ra,8(sp) 

指令addi sp,sp,-16的作用是将当前堆栈指针向下移动16个字节，以在栈上为函数调用或局部变量分配16个字节的空间。
指令sd ra,8(sp)的作用是将forkret()的返回地址保存到当前栈帧的偏移量为 8 个字节的位置。保存返回地址的目的是在函数执行完后，可以通过读取该地址来返回到调用者函数的正确位置。
因此猜测可能是sp寄存器设置有误。经检查发现在allocproc()中，我在分配内核栈前就设置了进程的sp寄存器。

// Set up new context to start executing at forkret,
// which returns to user space.
memset(&p->context, 0, sizeof(p->context));
p->context.ra = (uint64)forkret;
p->context.sp = p->kstack + PGSIZE;



p->kernel_pagetable = ukvminit();
char *pa = kalloc();
if(pa == 0)
	panic("kalloc");
uint64 va = KSTACK((int) 0);
if(mappages(p->kernel_pagetable, va, PGSIZE, (uint64)pa, PTE_R | PTE_W) != 0)
	panic("ukstack");
p->kstack = va;
va = KSTACK((int) (p - proc));
kvmmap(va, (uint64)pa, PGSIZE, PTE_R | PTE_W);

修改：将设置进程p的上下文context的代码块移至最后。

3.没有为kernel_pagetable设置每个进程的内核栈映射
现象：输出了panic: kvmpa

make CPUS=1 qemu


qemu-system-riscv64 -machine virt -bios none -kernel kernel/kernel -m 128M -smp 1 -nographic -drive file=fs.img,if=none,format=raw,id=x0 -device virtio-blk-device,drive=x0,bus=virtio-mmio-bus.0



xv6 kernel is booting



panic: kvmpa

分析：在项目目录中搜索kvmpa，发现只在virtio_disk.c中调用了kvmpa()。由注释中可知，buf0是在内核栈中的。而kvmpa()是使用kernel_pagetable的。修改前，在kvminit()中为kernel_pagetable设置了每个进程的内核栈的映射。而修改后，我只为user’s kernel page table设置了内核栈映射，且移除了原来在kvminit()中的内核栈设置，所以用kvmpa()时映射不到相应的物理内存。

// buf0 is on a kernel stack, which is not direct mapped,
// thus the call to kvmpa().
disk.desc[idx[0]].addr = (uint64) kvmpa((uint64) &buf0);

uint64 kvmpa(uint64 va) {
  uint64 off = va % PGSIZE;
  pte_t *pte;
  uint64 pa;
  
  pte = walk(kernel_pagetable, va, 0);
  if(pte == 0)
    panic("kvmpa 0");
  if((*pte & PTE_V) == 0)
    panic("kvmpa 1");
  pa = PTE2PA(*pte);
  return pa+off;
}

修改：

char *pa = kalloc(); // 分配内核栈空间
if(pa == 0)
	panic("kalloc");





// 为process's kernel pagetable 设置内核栈映射
uint64 va = KSTACK((int) 0);
if(mappages(p->kernel_pagetable, va, PGSIZE, (uint64)pa, PTE_R | PTE_W) != 0)
	panic("ukstack");
p->kstack = va;

// 为kernel_pagetable设置内核栈映射
va = KSTACK((int) (p - proc));
kvmmap(va, (uint64)pa, PGSIZE, PTE_R | PTE_W);

对于这个bug还有另外一种解决办法，就是修改virtio_disk.c，具体可以看第六个bug的解决，且这个方法还顺带解决了第四个bug。
4.
现象：

make CPUS=1 qemu


make CPUS=1 qemu
qemu-system-riscv64 -machine virt -bios none -kernel kernel/kernel -m 128M -smp 1 -nographic -drive file=fs.img,if=none,format=raw,id=x0 -device virtio-blk-device,drive=x0,bus=virtio-mmio-bus.0





xv6 kernel is booting




page table 0x0000000087f64000
..0: pte 0x0000000021fd8001 pa 0x0000000087f60000
.. ..0: pte 0x0000000021fd7c01 pa 0x0000000087f5f000
.. .. ..0: pte 0x0000000021fd841f pa 0x0000000087f61000
.. .. ..1: pte 0x0000000021fd780f pa 0x0000000087f5e000
.. .. ..2: pte 0x0000000021fd741f pa 0x0000000087f5d000
..255: pte 0x0000000021fd8c01 pa 0x0000000087f63000
.. ..511: pte 0x0000000021fd8801 pa 0x0000000087f62000
.. .. ..510: pte 0x0000000021fed807 pa 0x0000000087fb6000
.. .. ..511: pte 0x0000000020001c0b pa 0x0000000080007000
init: starting sh
panic: virtio_disk_intr status

分析：
搜索virtio_disk_intr status可知这句错误信息是由kernel/virtio_disk.c的virtio_disk_intr()输出的。再搜索virtio_disk_intr得知其只在kernel/trap.c中调用。可以看到这个错误与中断相关，应该是与IO设备的映射相关，应该是与页表设置相关。
这个bug检查了巨久，一开始花了很多时间想通过gdb来看是从哪里出错的，但找不到。然后才想到应该是与页表的设置相关，然后花了些时间检查我新增的ukvmmap()函数，但这个函数的主要实现与kvmmap()函数是完全一致的，应该没有问题。最后才想到还需要设置了内核栈的映射，两张页表应该是要完全一致的！

解决：

// 为process's kernel pagetable 设置内核栈映射
uint64 va = KSTACK((int) 0); // 错误
uint64 va = KSTACK((int) (p - proc)); // 正确
// 为kernel_pagetable设置内核栈映射
va = KSTACK((int) (p - proc));

5. bug5

$ usertests
usertests starting
panic: freewalk: leaf

分析：
搜索freewalk: leaf得知该报错由freewalk()输出，阅读该函数得知若叶子映射的物理内存空间没有被释放，则会输出该错误信息。

// Recursively free page-table pages.
// L0级的映射应该在释放物理内存时已经全部设置为0
void freewalk(pagetable_t pagetable) {
  // 一张页表有 2^9 = 512 PTEs
  for(int i = 0; i < 512; i++){
    pte_t pte = pagetable[i];
    // PTE_V 是 1 并且 PTE_R PTE_W PTE_X三项是 0. == 优先级高于 &&
    // 注意在三级页表中，没有分配的物理内存是不需要建立映射的，也即
    // 有部分页表项是.
    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);
}

这是因为我直接调用了freewalk()前没有释放页表映射的物理内存，但这也是上文分析过的需求。
修改：
新增一个void freewalk2(pagetable_t, int)，通过当前页表层级的信息来作为递归的终止条件，且不检查叶子映射的物理内存空间是否被释放。

6. remap

usertests starting
test execout: panic: remap

当前尝试建立映射的物理地址已经
是在run()函数中调用fork()的时候出错的。

分析：
搜索panic: remap， 发现该错误是在mappages()函数中输出的。*pte & PTE_V意味着该页表项的PTE_V标志为1。
gdb调试发现该错误是在fork()中，分配新进程allocproc()时，调用ukvminit()为新进程建立新的进程内核页表时输出的。

fork()系统调用不是第一次调用，在sh程序中就已经调用过了，但为什么这里才出错？
在这之前是否执行过freeproc()，然后没有删除干

花费了许多时间重复检查进程内核页表的构建相关的代码，都没有问题。最后发现是在freeproc()中没有释放内核栈。
修改：
对于内核栈的释放，有三处地方需要处理，一是要释放内核栈占用的物理内存空间(但实际测试时，使用kfree()释放物理内存会出错)，二是要在用户内核页表中解除映射，三是要在内核页表中解除映射。但更方便的做法是不在内核页表中建立内核栈的映射，如此也就不需要释放。但需要注意这个处理方法中，由于内核页表中不再维护内核栈的映射，因此要修改使用内核栈映射的相关代码。

// kernel/proc.c
// 取消映射
if(p->kstack) {
	uvmunmap(p->kernel_pagetable, p->kstack, 1, 1);
	// kfree((void*)p->kstack_pa); // 为什么不行？
}

// virtio_disk.c
// 由于内核页表中不维护内核栈的映射，故应该使用进程内核页表
#include "proc.h" // 添加头文件proc.h
struct proc *p = myproc();
disk.desc[idx[0]].addr = (uint64) vmpa(p->kernel_pagetable, (uint64) &buf0);

// kernel/vm.c
uint64 vmpa(pagetable_t pagetable, uint64 va) {
	uint64 off = va % PGSIZE;
	pte_t *pte;
	uint64 pa;
	pte = walk(pagetable, va, 0);
	if(pte == 0)
		panic("vmpa 0");
	if((*pte & PTE_V) == 0)
		panic("vmpa 1");
	pa = PTE2PA(*pte);
	return pa+off;
}

到此终于将所有debug完成，能够完全通过usertests。还有一个遗留的问题是释放内核栈的时候，如果使用kfree释放内核栈占用的物理内存空间，则还会出错，还没研究明白是什么原因。

Simplify copyin/copyinstr (hard)