xv6-labs-2020.lab2.pagetable

Posted on 2021-05-13 Edited on 2021-07-22 In OS.xv6-labs Views:

页表

lab2 pagetable

1.作业链接

https://pdos.csail.mit.edu/6.828/2020/labs/pgtbl.html

2. 实习内容

2.1 vmprint()

实现一个函数 vmprint(pagetable_t)，实现输出页表的功能
输出格式如下
- 第一行为输入的参数
- 接着输出 valid 的 PTE 以及指向的 pa（物理地址）

page table 0x0000000087f6e000
..0: pte 0x0000000021fda801 pa 0x0000000087f6a000
.. ..0: pte 0x0000000021fda401 pa 0x0000000087f69000
.. .. ..0: pte 0x0000000021fdac1f pa 0x0000000087f6b000
.. .. ..1: pte 0x0000000021fda00f pa 0x0000000087f68000
.. .. ..2: pte 0x0000000021fd9c1f pa 0x0000000087f67000
..255: pte 0x0000000021fdb401 pa 0x0000000087f6d000
.. ..511: pte 0x0000000021fdb001 pa 0x0000000087f6c000
.. .. ..510: pte 0x0000000021fdd807 pa 0x0000000087f76000
.. .. ..511: pte 0x0000000020001c0b pa 0x0000000080007000

(1) 一些提示

可以在 kernel/vm.c 中实现 vmprint()
使用在文件 kernel/riscv.h. 结尾定义的宏
参考 freewalk() 的实现
在 kernel/defs.h 中声明 vmprint()
使用 %p 输出地址

(2) 准备工作

声明函数原型

// kernel/defs.h
// vm.c
void            vmprint(pagetable_t);
// 为了方便实现, 定义的辅助函数
void            vmprint_help(pagetable_t pagetable, int level);

插入测试代码

/// kernel/exec.c
int exec(char *path, char **argv) {
    // ...
    if(p->pid==1) vmprint(p->pagetable); // Code Added
    return argc;
    // ...
}

(3) 实现

在 vm.c 中实现代码
实现上比较简单，只需要逐级输出即可
模仿 freewalk()

static char* pgtbl_level[] = {
    "..",
    ".. ..",
    ".. .. ..",
};

void vmprint(pagetable_t pagetable){
    printf("page table %p\n", pagetable);
    vmprint_help(pagetable, 0);
}

void vmprint_help(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){
            // this PTE points to a lower-level page table.
            uint64 child = PTE2PA(pte);
            printf("%s%d: pte %p pa %p\n", pgtbl_level[level], i, pte, child);
            if(level != 2) {
                vmprint_help((pagetable_t)child, level + 1);
            }
        }
    }
}

(4) 回答问题

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?

xv6 的 3 级页表如下所示

page 0 中保存的是第 2 级页表的起始地址，以及权限位
page 2 中保存的是实际物理地址的页号，以及权限位
用户态下访问不到这里 page 1映射的地址空间，因为用户态和内核态使用的不是同一个页表，翻译得到的物理地址不同

2.2 a kernel page table per process

xv6 实现的时候
- 所有的进程共享一个内核的 pagetable，是虚拟地址直接映射物理地址实现的
- 为每一个进程维护了一个 pagetable，利虚存技术实现的，虚拟地址从 0 开始
- 这样的话，进入内核之后用户态的页表就失效了，于是如果我们在内核态下想要直接访问用户态传过来的指针，必须要先进行额外的翻译操作，而不是直接去页表中翻译
这一部分实验要求每一个进程都拥有一个自己的内核页表，这个内核页表需要和当前存在的全局内核页表一致

(1) 一些提示

在数据结构 struct proc 中增加一个字段，为每一个进程保存它的内核页表
在调用 allocproc() 的时候，为每个进程分配一个内核页表
- 具体的实现参照 kvminit()
确保每个进程的内核栈都在其内核页表中有映射
- 之前是都保存在内核页表中，在 procinit() 中实现的
- 每一个进程应该只需要保存他自己的内核栈的映射即可
当进程调度的时候，需要切换页表
- 参考 kvminithart() 的实现
- 先调用 w_satp()，设置第 1 级页表的基地址
- 再调用 sfence_vma() 清空 TLB（失效了）
当没有其他进程运行的时候，scheduler() 需要使用 kernel_pagetable
freeproc() 进程释放的时候需要同时释放页表
当你释放页表的时候，不能够把最后对应的物理内存也释放了，因为他们是共享的
- 因为他们都共享原来内核的代码之类的，这些不能释放
- 内核栈也不用释放，一次分配，多次使用
之前实现的 vmprint() 用于 DEBUG
用于 DEBUG，缺页异常导致的结果
- A missing page table mapping will likely cause the kernel to encounter a page fault. It will print an error that includes sepc=0x00000000XXXXXXXX. You can find out where the fault occurred by searching for XXXXXXXX in kernel/kernel.asm.

(2) 实现

struct proc 增加一个保存内核页表的字段

// kernel/proc.h
struct proc {
    // ...
    pagetable_t pagetable_k;     // Kernel page table
}

allocproc() 分配页表
在对页表进行映射的时候，我们需要对当前进程的内核页表进行映射
通过修改 kvmmap() 为 kvmmap_k() 实现

// kernel/proc.c
extern char etext[];  // 在进行页表映射的时候需要用到

static struct proc* allocproc(void) {
    // ...
    // 分配内核页表
    p->pagetable_k = proc_pagetable_k(p);
    if(p->pagetable_k == 0){
        freeproc(p);
        release(&p->lock);
        return 0;
    }
    // ...
}


pagetable_t proc_pagetable(struct proc *p) {
    pagetable_t pagetable;
    pagetable = uvmcreate();
    if(pagetable == 0)
        return 0;
    kvmmap_k(pagetable, UART0, UART0, PGSIZE, PTE_R | PTE_W);
    kvmmap_k(pagetable, VIRTIO0, VIRTIO0, PGSIZE, PTE_R | PTE_W);
    kvmmap_k(pagetable, CLINT, CLINT, 0x10000, PTE_R | PTE_W);
    kvmmap_k(pagetable, PLIC, PLIC, 0x400000, PTE_R | PTE_W);
    kvmmap_k(pagetable, KERNBASE, KERNBASE, (uint64)etext-KERNBASE, PTE_R | PTE_X);
    kvmmap_k(pagetable, (uint64)etext, (uint64)etext, PHYSTOP-(uint64)etext, PTE_R | PTE_W);
    kvmmap_k(pagetable, TRAMPOLINE, (uint64)trampoline, PGSIZE, PTE_R | PTE_X);
    return pagetable;
}

// kernel/vm.c
void kvmmap_k(pagetable_t pagetable, uint64 va, uint64 pa, uint64 sz, int perm) {
  if(mappages(pagetable, va, sz, pa, perm) != 0)
    panic("kvmmap_k");
}

映射内核栈
只需要为每个进程映射自己的内核栈，同时在 procinit() 不需要分配栈

// kernel/proc.c
static struct proc* allocproc(void) {
    // ...
    // 分配内核页表
    char *pa = kalloc();
    if(pa == 0){
        freeproc(p);
        release(&p->lock);
        return 0;
    }
    uint64 va = KSTACK((int) (p - proc));
    kvmmap_k(p->pagetable_k, va, (uint64)pa, PGSIZE, PTE_R | PTE_W);
    p->kstack = va;
    // ...
}

void procinit(void) {
    struct proc *p;
    initlock(&pid_lock, "nextpid");
    for(p = proc; p < &proc[NPROC]; p++) {
        initlock(&p->lock, "proc");
        p->kstack = 0;
    }
    kvminithart();
}

调度的时候切换内核页表

void scheduler(void) {
    // ...
    w_satp(MAKE_SATP(p->pagetable_k));
    sfence_vma();
    swtch(&c->context, &p->context);
    kvminithart();
    // ...
}

在 freeproc() 的时候
- 首先释放栈的映射
- 释放页表，但是不能释放第 3 级页表指向的物理页

// kernel/proc.c
static void freeproc(struct proc *p) {
    // ...
    // 还得释放栈的映射(在释放整个页表之前)
    if(p->kstack != 0) {
        // dofree = 1
        uvmunmap(p->pagetable_k, p->kstack, 1, 1);
        // uint64 pa = walkaddr(p->pagetable_k, p->kstack);
        // kfree((void*)pa);
    }
    p->kstack = 0;
    if(p->pagetable_k)
        proc_freepagetable_k(p->pagetable_k);
    p->pagetable_k = 0;
    // ...
}

// 解除映射, 但是不释放内存
void proc_freepagetable_k(pagetable_t pagetable) {
    uvmunmap(pagetable, UART0, 1, 0);
    uvmunmap(pagetable, VIRTIO0, 1, 0);
    uvmunmap(pagetable, CLINT, 1, 0);
    uvmunmap(pagetable, PLIC, 1, 0);
    uvmunmap(pagetable, KERNBASE, 1, 0);
    uvmunmap(pagetable, (uint64)etext, 1, 0);
    uvmunmap(pagetable, TRAMPOLINE, 1, 0);
    freewalk_k(pagetable);
}

// kernel/vm.c
void freewalk_k(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];
        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_k((pagetable_t)child);
            pagetable[i] = 0;
        }
        // 这是允许的
        // } else if(pte & PTE_V){
        //   panic("freewalk: leaf");
        // }
    }
    kfree((void*)pagetable);
}

将上面的函数加入 kernel/defs.h

// kernel/proc.c
pagetable_t     proc_pagetable_k(struct proc *);
void            proc_freepagetable_k(pagetable_t);

// kernel/vm.c
void            kvmmap_k(pagetable_t pagetable, uint64 va, uint64 pa, uint64 sz, int perm);
void            freewalk_k(pagetable_t);

执行完之后报错

1	panic: virtio_disk_intr status

这是由于在 kvmpa() 中调用 walk() 的时候没有使用进程对应的内核页表导致的

// kernel/vm.c
uint64 kvmpa(uint64 va) {
    // ...
    pte = walk(kernel_pagetable, va, 0);
    pte = walk(myproc()->pagetable_k, va, 0);
    // ...
}

(3) 一些细节

以上的解法会导致一些其他问题，例如资源申请，发现不够了，此时应该 kill 掉这个进程，而不是 panic
例如 kvmmap_k() 的设计，我们将 panic 修改为检查返回值

// kernel/vm.c
int kvmmap_k(pagetable_t pagetable, uint64 va, uint64 pa, uint64 sz, int perm) {
    if(mappages(pagetable, va, sz, pa, perm) != 0) {
        // panic("kvmmap_k");
        return -1;
    }
    return 0;
}

// kernel/proc.c
static uint64 addr_kernel[] = {
    UART0,
    VIRTIO0,
    CLINT,
    PLIC,
    KERNBASE,
    (uint64)etext,
    TRAMPOLINE,
};

void check_proc_freepagetable_k(pagetable_t pagetable, int num) {
    for(int i = 0; i <= num; ++i) {
        uvmunmap(pagetable, addr_kernel[i], 1, 0);
    }
}

pagetable_t proc_pagetable_k(struct proc *p) {
    pagetable_t pagetable;

    // An empty page table.
    pagetable = uvmcreate();
    if(pagetable == 0)
        return 0;

    // 模仿 kvminit()
    int ret = 0;
    int num = 0;
    ret = kvmmap_k(pagetable, UART0, UART0, PGSIZE, PTE_R | PTE_W);
    if(ret != 0) goto bad;
    ++num;
    ret = kvmmap_k(pagetable, VIRTIO0, VIRTIO0, PGSIZE, PTE_R | PTE_W);
    if(ret != 0) goto bad;
    ++num;
    ret = kvmmap_k(pagetable, CLINT, CLINT, 0x10000, PTE_R | PTE_W);
    if(ret != 0) goto bad;
    ++num;
    ret = kvmmap_k(pagetable, PLIC, PLIC, 0x400000, PTE_R | PTE_W);
    if(ret != 0) goto bad;
    ++num;
    ret = kvmmap_k(pagetable, KERNBASE, KERNBASE, (uint64)etext-KERNBASE, PTE_R | PTE_X);
    if(ret != 0) goto bad;
    ++num;
    ret = kvmmap_k(pagetable, (uint64)etext, (uint64)etext, PHYSTOP-(uint64)etext, PTE_R | PTE_W);
    if(ret != 0) goto bad;
    ++num;
    ret = kvmmap_k(pagetable, TRAMPOLINE, (uint64)trampoline, PGSIZE, PTE_R | PTE_X);
    if(ret != 0) goto bad;
    ++num;
    return pagetable;

    bad:
    check_proc_freepagetable_k(pagetable, num);
    return 0;
}

static struct proc* allocproc(void) {
    // ...
    if(kvmmap_k(p->pagetable_k, va, (uint64)pa, PGSIZE, PTE_R | PTE_W) != 0) {
        free(pa);
        freeproc(p);
        release(&p->lock);
        return 0;
    }
    p->kstack = va;
    // ...
}

2.3 Simplify copyin/copyinstr

copyin() 函数在读取用户空间的虚拟地址的时候，需要先使用用户空间的页表，将其翻译成物理地址
我们在这里需要实现将每个进程用户空间保存的页表映射存到内核页表中，从而可以直接翻译访问

(1) 一些提示

这个机制依赖于用户空间和内核空间的虚拟地址的范围没有交集
- 于是我们需要让用户空间的地址增长小于最小的内核虚拟地址
- xv6 启动正常工作之后的最低地址 PLIC（0C000000）
- 需要让用户空间的地址增长小于 PLIC
- 为什么不是 CLINT 呢？CLINT 都是在 M-Mode 中映射的
先实现 copyin()，在 copyin() 中调用 copyin_new()，之后再去实现 copyinstr_new()
每次对用户页表进行修改的时候，同时修改内核页表
- fork(), exec(), sbrk()
不要忽略第一个用户进程，usertint() 中也需要将用户页表的映射加入到内核页表中
权限设置：A page with PTE_U set cannot be accessed in kernel mode.

(2) 实现

[1] CLINT

去掉内核页表对于 CLINT 的映射，注释掉即可

// kernel/proc.c
static uint64 addr_kernel[] = {
    UART0,
    VIRTIO0,
    // CLINT,
    PLIC,
    KERNBASE,
    (uint64)etext,
    TRAMPOLINE,
};

pagetable_t proc_pagetable_k(struct proc *p) {
    // ...
    // ret = kvmmap_k(pagetable, CLINT, CLINT, 0x10000, PTE_R | PTE_W);
    // if(ret != 0) goto bad;
    // ++num;
    // ...
}

用户虚拟地址的增长不能超过 PLIC

// kernel/proc.c
int growproc(int n) {
    // ...
    if(n > 0) {
        if(sz + n >= PLIC) return -1;
        // ...
    }
    // ...
}

[2] 内核页表

在修改用户页表的同时修改内核页表，设置权限
注意在释放内核页表的时候，都不能释放物理页
找到 uvmalloc() 函数修改页表的地方
构造一个复制函数

1
2
3

// kernek/defs.h
// vm.c
uint64          uvmalloc_k (pagetable_t pgold, pagetable_t pgnew, uint64 oldsz, uint64 newsz);

// kernel/vm.c
uint64 uvmalloc_k (pagetable_t pgnew, pagetable_t pgold, uint64 oldsz, uint64 newsz) {
    uint64 a;
    pte_t *pte_old, *pte_new;
    if(newsz < oldsz) return oldsz;
    oldsz = PGROUNDUP(oldsz);
    for(a = oldsz; a < newsz; a += PGSIZE){
        // 不分配
        pte_old = walk(pgold, a, 0);
        if(pte_old == 0) panic("uvmalloc_k: pte should exist!");
        // 分配
        pte_new = walk(pgnew, a, 1);
        if(pte_new == 0) panic("uvmalloc_k: kalloc error!");
        // 设置映射
        *pte_new = (*pte_old) & (~PTE_U);
    }
    return newsz;
}

userinit()

// kernel/proc.c
void userinit(void) {
    // ...
    uvminit(p->pagetable, initcode, sizeof(initcode));
    p->sz = PGSIZE;
    uvmalloc_k(p->pagetable_k, p->pagetable, 0, p->sz); // Code Added
    // ...
}

fork()

// kernel/proc.c
int fork(void) {
    // ...
    // 没有检查返回值
    uvmalloc_k(np->pagetable_k, np->pagetable, 0, p->sz); // Code Added
    release(&np->lock);
    return pid;
}

exec()

注意这里需要将原来内核页表中的映射关系解除（内核映射不需要）

// kernel/exec.c
int exec(char *path, char **argv) {
    // ...
    // Load program into memory.
    for(i=0, off=elf.phoff; i<elf.phnum; i++, off+=sizeof(ph)){
        // ...
        // 虚拟地址的大小
        if(sz1 >= PLIC)
            goto bad;
        // ...
    }
    // ...
    // 释放原来的页表(不需要释放内核原来的)
    uvmunmap(p->pagetable_k, 0, PGROUNDUP(oldsz)/PGSIZE, 0);
    // 全部都分配好了再复制
    // 没有检查返回值
    uvmalloc_k(p->pagetable_k, p->pagetable, 0, sz);

    if(p->pid==1) vmprint(p->pagetable);
    return argc; // this ends up in a0, the first argument to main(argc, argv)
    // ...
}

sys_sbrk()

可能会解除映射关系，定义函数 uvmdealloc_k() 进行处理（不释放具体的物理页）

// kernel/proc.c
// 不释放物理内存
uint64 uvmdealloc_k(pagetable_t pagetable, uint64 oldsz, uint64 newsz) {
    if(newsz >= oldsz)
        return oldsz;
    if(PGROUNDUP(newsz) < PGROUNDUP(oldsz)){
        int npages = (PGROUNDUP(oldsz) - PGROUNDUP(newsz)) / PGSIZE;
        uvmunmap(pagetable, PGROUNDUP(newsz), npages, 0);
    }
    return newsz;
}

uint64 sys_sbrk(void) {
    // ...
    // 没有检查返回值
    if(n > 0) {
        uvmalloc_k(p->pagetable_k, p->pagetable, addr, addr + n);
    } else if(n < 0){
        // 不释放物理内存
        uvmdealloc_k(p->pagetable_k, addr + n, addr);
    }
    return addr;
}

[3] 测试函数

最后修改测试函数

// kernel/vm.c
int copyin(pagetable_t pagetable, char *dst, uint64 srcva, uint64 len) {
    return copyin_new(pagetable, dst, srcva, len);
}

int copyinstr(pagetable_t pagetable, char *dst, uint64 srcva, uint64 max) {
    return copyinstr_new(pagetable, dst, srcva, max);
}

(3) 一些细节

同样是 panic 的问题，在设计上我们不应该让用户的操作造成操作系统的崩溃，因此 uvmalloc_k() 中的 panic 应该处理掉
其中 panic("uvmalloc_k: pte should exist!"); 是合理的，因为用于页表的映射是存在
panic("uvmalloc_k: kalloc error!"); 这个需要操作系统处理，而不是报错崩溃

uint64 uvmalloc_k (pagetable_t pgnew, pagetable_t pgold, uint64 oldsz, uint64 newsz) {
    // ...
    pte_new = walk(pgnew, a, 1);
    if(pte_new == 0) {
        // panic("uvmalloc_k: kalloc error!");
        return -1;
    }
    // ...
}

各处检查返回值即可

// kernel/exec.c
// 进程还在, 不需要释放内核页表
int exec(char *path, char **argv) {
    // ...
    if(uvmalloc_k(p->pagetable_k, p->pagetable, 0, sz) == -1)
        goto bad;
    // ...
}

// kernel/proc.c
// 内核态, 只会调用一次, 第一个进程
void userinit(void) {
    // ...
    if(uvmalloc_k(p->pagetable_k, p->pagetable, 0, p->sz) == -1)
        panic("usertinit error!");
    // ...
}

// kernel/proc.c
int fork(void) {
    // ...
    // 没有检查返回值
    if(uvmalloc_k(np->pagetable_k, np->pagetable, 0, p->sz) == -1) {
        freeproc(np);
        release(&np->lock);
        return -1;
    }
    // ...
}

// kernel/sysproc.c
uint64 sys_sbrk(void) {
    // ...
    // 没有检查返回值
    if(n > 0) {
        if(uvmalloc_k(p->pagetable_k, p->pagetable, addr, addr + n) == -1) {
            growproc(-n);
            return -1;
        }
    }
    // ...
}

(4) 回答问题

copyin() 中的 3 个测试

1 2	if(srcva >= p->sz \|\| srcva+len >= p->sz \|\| srcva+len < srcva) return -1;

前两个判断保证复制的整块内存区域是已经分配的，第三个判断保证 len 不为负
第三个判断是必要的，如果没有这个判断，memmove() 的第三个参数类型为 uint，会导致把大量的用户页表的内容带入内核，可能对造成内核代码修改崩溃

1	void* memmove(void dst, const void src, uint n);

3. 实验结果

在修改完 2.3 的 (3) 之后，有一次结果超时，后来都能通过测试

== Test pte printout ==
$ make qemu-gdb
pte printout: OK (13.3s)
== Test answers-pgtbl.txt == answers-pgtbl.txt: OK
== Test count copyin ==
$ make qemu-gdb
count copyin: OK (2.4s)
    (Old xv6.out.count failure log removed)
== Test usertests ==
$ make qemu-gdb
(279.6s)
== Test   usertests: copyin ==
  usertests: copyin: OK
== Test   usertests: copyinstr1 ==
  usertests: copyinstr1: OK
== Test   usertests: copyinstr2 ==
  usertests: copyinstr2: OK
== Test   usertests: copyinstr3 ==
  usertests: copyinstr3: OK
== Test   usertests: sbrkmuch ==
  usertests: sbrkmuch: OK
== Test   usertests: all tests ==
  usertests: all tests: OK
== Test time ==
time: OK
Score: 66/66

4. 遇到的困难以及收获

整体思路上不算是很难，而且提示给的很充足
但是由于测试需要跑的时间较长，整个 lab 也花了较多时间
做完这个 lab 之后对于操作系统内部的页表组织有了更深刻的理解，同时对比不同的组织方式，理解了它们之间的优劣
- 每个进程拥有一个页表，整个内核态拥有一个页表
- 每个进程拥有一个内核页表和用户页表
感觉系统性的东西，能够把想法正确实现就是很棒了

5. 对课程或 lab 的意见和建议

暂时没有意见

6. 参考文献

https://pdos.csail.mit.edu/6.828/2019/xv6/book-riscv-rev1.pdf
https://pdos.csail.mit.edu/6.828/2020/labs/pgtbl.html