MIT 6.S081 操作系统课程系列3 Page tables

https://pdos.csail.mit.edu/6.828/2020/labs/pgtbl.html https://pdos.csail.mit.edu/6.828/2020/xv6/book-riscv-rev1.pdf 本次实验需要读xv6手册第3章。看相关kernel代码。 理解页表的原理并实现一些相关功能。

页表的作用是通过地址映射，使得每个进程看上去拥有自己独立的地址空间和内存，但实际是所有进程共用一套物理内存和地址。

分页硬件

  • riscv指令(user和kernel)都只操作虚拟地址。riscv硬件会把虚拟地址映射到实际地址。 xv6系统下，只会用到64bit的虚拟地址里的低39bit。页表逻辑上就是一个数组，包含pow(2, 27)=134217728个页表项(page table entries(PTE))。

  • 看手册图3.1和3.2。 每个PTE为64bit，包含一个44bit的页号physical page number(PPN)，一些标志位，和一些备用的bit。 分页硬件用虚拟地址39bit里的高27bit查到一个PTE，再把PTE里的PPN(44bit)和原始虚拟地址的后12bit(39 - 27)拼起来组成一个56bit的物理地址。

  • 分页的粒度常用4096(4k)字节。后续可以看到很多内存操作都会处理4k对齐，内存也是按页分配。

  • 134217728(512 * 512 * 512)个PTE存在三级树形结构里，每层刚好512项。 上面说的用高27bit查PTE，即前9bit对应第一级的index，中9bit对应第二级的index，后9bit对应第三级的index。 只要有一级找不到，就会报page-fault异常，交给kernel处理。

  • PTE里有十个左右的各种标志位。 PTE_V PTE是否存在 PTE_U 如果开启，kernel下不允许读。 PTE_R 是否允许读 PTE_W 是否允许写 PTE_X 是否允许执行

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)。 end到PHYSTOP就是被内存管理系统控制(通过kalloc/kfree)的内存(见kalloc.c)。就是图中的freememory。 用户进程分配到的物理内存都是分布在freememory里。虽然寻址空间都是0->(0x4000000000-1)。

创建地址空间

  • 看页表相关代码vm.c 主要的数据pagetable_t是一个uint64 *(riscv.h)

  • 看懂walk函数 pte_t *walk(pagetable_t pagetable, uint64 va, int alloc) 给一个pagetable头地址(L2页表地址)(物理地址)，一个虚拟地址va，一个alloc选项。 返回va的物理地址。

  • 看图3.2 L2L1L0为上述三级PTE。 先有L2页表的地址。

1.拿L2的9bit(PX宏展开就是把va的对应级别的9bit拿出来)，可以得到L2中对应的PTE项，检查它的PTE_V标志。
   1.1如果PTE_V标识为0说明该PTE不存在，那么看alloc选项。
       1.1.1如果为0，函数返回0。
       1.1.2如果为1，用kalloc()分配一个页，并标记PTE_V有效。
            计算L1的页表地址(PTE2PA宏是把PTE的44bitPPN拿出来左移12bit)。
   1.2如果PTE_V标志为1说明该PTE有效，计算L1的页表地址。

同样算法从L1得到L0的页表地址后，直接拿出L0数组里对应的PTE项，返回其地址。

需要注意的是新的页表最开始只分配了一页的内存，只能支持一小部分的PTE，如果发现下一级的页表头不存在，说明还没给它分配内存，那么要根据alloc来分配内存。

  • 页对齐 目的是方便兼容不同硬件和提高效率，不对齐会有额外的io开销。 两个计算对齐地址的宏: PGROUNDDOWN把地址往下对齐一页，不满一页的值抹掉，比如0x1003会变成0x1000。 PGROUNDUP把地址往上对齐一页，只要超出1就会往上走一页，比如0x1001会变成0x2000。 如果正好是对齐的地址比如0x1000，都不会发生改变。

  • 看懂mappages函数 int mappages(pagetable_t pagetable, uint64 va, uint64 size, uint64 pa, int perm) 给一个pagetable头地址(L2页表地址)(物理地址)，一个虚拟地址va，一个数size，一个物理地址pa， 一个配置项perm。

    功能就是更新页表里的项，给定size，对于从va和pa开始的size个字节(以页分组)，va和pa地址一一对应，把映射关系安装到页表。 把va和va+size对齐一下分别作为头尾。开始循环。

    对于其间的每个虚拟地址，调walk得到其PTE位置，再把物理地址pa转成PTE赋值到页表。每次循环va和pa都往后走一页。

  • kvmmap()用mappages把映射关系安装到kernel的页表。 在main()里kvminit()用kvmmap安装一系列硬件等映射。这个发生在页表使能之前，所以地址都是物理地址。

物理地址的分配

见kalloc.c。上次lab已经看懂了它的原理，这里跳过。

进程地址空间

  • 每个进程有独立的页表，当进程发生切换时也会切换页表。 见图2.3。进程的用户内存从0开始到MAXVA(riscv.h)，一共是256G字节大小。

  • 进程向xv6内核请求更多内存时，xv6用kalloc分配物理页。然后往页表中插入PTE项(指向新分配的物理地址)(就是把映射关系装进页表)。

  • 通过巧妙的设计，不同进程的虚拟地址会映射到不同的物理地址，不会相互干扰。进程自己可见的内存地址时连续的，虽然实际对应的物理地址是散乱的。

sbrk

  • 按linux手册的描述，sbrk改变program break的位置，改变了进程的数据段。program break变大的效果就是增大了进程的内存，反之减小。

  • 看xv6的sbrk，直接调用growproc(n)来增减内存。 如果n大于0，用uvmalloc增加。 如果n小于0，用uvmdealloc减小。 相关的函数基本都建立在之前看过的kfree/kalloc/walk/mappages基础之上，

  • 整理一下内存和分页相关的函数

    函数

    功能

    kalloc

    分配一页4096字节物理内存

    kfree

    回收一页4096字节物理内存

    freerange

    用kfree回收范围内物理内存

    walk

    在页表中找虚拟地址对应的PTE地址(可选是否为未分配内存的PTE分配内存)

    freewalk

    递归形式。用kfree回收整个页表本身。

    mappages

    往页表中安装虚拟地址-物理地址的对应关系。如果PTE没分配内存，分配内存。

    kvmmap

    用mappages把地址对应关系安装到kernel的页表

    uvmunmap

    把页表里从虚拟地址va开始的n个page的对应关系删除(可选是否kfree物理地址)

    uvmdealloc

    给定新老内存size，用uvmunmap删除其间的va对应关系(可选是否回收内存)。

    uvmalloc

    给定新老内存size。遍历老size到新size之间的页，每个页先kalloc分配物理内存，再mappages安装到页表。

    copyout

    把数据从物理地址copy到虚拟地址对应的物理地址

    copyin

    把数据从虚拟地址对应的物理地址copy到物理地址

    uvmcreate

    用kalloc分配一页，创建一个空页表。

    uvmfree

    用uvmunmap删除页表中从0开始n个地址的对应关系(同时kfree每页的物理地址)。再freewalk删除页表本身。

    uvmcopy

    给定新老两个页表和size，把老页表0开始到size的虚拟地址的数据复制到新页表。从0开始的每一页虚拟地址，找到老表的PTE、物理地址，kalloc分配一页，把物理地址上的数据复制到新分配的页，再用mappages把虚拟地址和新分配的页安装到页表。

exec流程

  • ELF(Executable Linking Format)文件是广泛用于类unix系统的文件格式，xv6的应用程序就是用的elf文件。 https://wiki.osdev.org/ELF https://elinux.org/Executable_and_Linkable_Format_(ELF) https://linuxhint.com/understanding_elf_file_format/

  • 格式定义见elf.h，有一个elf头elfhdr，一个program头proghdr。 每个proghdr定义一个需要加载到内存的应用程序。 每个xv6程序只包含一个proghdr，其他系统可能包含多个。

  • exec(exec.c)目的是运行一个程序(可执行的文件)。先用namei(fs.c)打开要执行的文件。再读elfhdr。检查ELF_MAGIC(elf.h)。 用proc_pagetable(exec.c)创建user页表。 对于每一个程序段，用uvmalloc分配内存，更新页表。用loadseg把程序段加载到指定地址。 再处理exec参数。设置寄存器以运行指定的程序。

  • 其实细节很复杂。后续会不断更新理解。

做题1.打印页表

  • vm.c里做一个函数vmprint，给定页表头和level，打印出页表所有非空的PTE和物理地址。插到exec函数返回前。 参考freewalk做一个递归打印每个PTE，依靠level填上前缀即可。

  • 用make grade测试，测试通过会打印出：pte printout: OK

做题2.每个进程独有的kernel页表

  • 得反复看代码，了解进程的结构和工作流程，内存、页表的布局。

  • 看proc.h，默认的代码下，每个进程有一个独立的用户页表pagetable。而kernel页表是所有进程共用(见vm.c)。

  • NPROC最大进程数为64(param.h)

  • TRAMPOLINE为MAXVA前一页，也就是整个虚拟地址空间的最后一页。

  • 看proc.c procinit 初始化进程表。给进程表每项分配一页作为kernel栈(kstack)，用KSTACK把每个kernel栈的虚拟地址顺序按排在TRAMPOLINE之前。 最后用kvminithart使能kernel页表。

  • allocproc 初始化一个进程。从进程表里找一个state为UNUSED的项，allocpid分配新的pid，为trapframe分配一页，proc_pagetable创建一个空的用户页表，初始化context结构体，context包含一批寄存器。切换进程的swith函数需要传入这个context。

  • allocproc在userinit和fork里用到。

  • userinit 在main函数里会调userinit，创建第一个user进程。 用allocproc分配一个进程，初始化，配置成initcode，也就是init.c的main，起sh程序(sh.c)。 进程的state设为RUNNABLE。 main最后会调scheduler()开始进程的调度，系统的进程就跑起来了。

  • scheduler 每个cpu都会起一个。会跑一个for的死循环，不会返回。 每次循环从进程表里找一个RUNNABLE的进程，设为RUNNING，用swtch()切换，执行找到的进程。

  • fork 用allocproc分配一个子进程，用uvmcopy复制一份页表到子进程，同时复制父进程user页表的数据到子进程。子进程状态设为RUNNABLE。

实现：

默认代码里只有唯一一个kernel页表(vm.c的kernel_pagetable)，现在要求做成每个进程自己维护一个kernel页表，进程运行时切换到自己的kernel页表。

  1. proc结构体添加一个kernel页表

  2. 目前allocproc函数里会创建用户页表，很自然可以把创建kernel页表加到此处。

  3. 做一个make_kernel_page_table函数。里面创建一个空页表作为每个进程的kernel页表。

  4. make_kernel_page_table里把进程的kstack的映射安装到新页表(kstack默认在procinit里初始化过，所以只安装映射即可)

  5. make_kernel_page_table里参考kvminit把映射安装到进程自己的kernel页表。

  6. freeproc里free自己的kernel页表。

  7. scheduler里swith之前要切换到进程的kernel页表。参考kvminithart。

Debug：

p->sz问题

  • 出现panic: uvmunmap: walk 因为freeproc里我仿照uvmfree()删除自己的kernel页表，而size不明确，用p->sz是不对的，导致uvmunmap里walk找不到va的对应关系而出panic。 那么size到底是多少，这个非常值得追踪一下。

  • 看一下进程的p->sz赋值情况(暂时找到这些)

    1. userinit。第一个进程。sz写死的PGSIZE。

    2. exec。对每个程序段用uvmalloc扩大内存大小，最后再加2个page。比如echo执行时是12k(3页)。

    3. growproc。直接扩大内存n字节。可以看出sz大小不是页对齐的。但映射永远是页对齐的。

    4. fork。子进程直接设为父进程的sz。

  • 最后看下来kernel页表不会像user页表那么随意变化。原始代码对kernel_pagetable的操作只在kvminit里。 那么参考kvminit反向操作一下，unmap就行了，不用管p->sz。

  • 另外kstack也需要处理。添加映射和删除映射要配对，否则容易出panic。

执行一个命令后shell无反应

  • 原因是在用户进程switch那，我们做成了切换到进程自己的kernel页表，但如果没有进程了就出问题了，相当于没有kernel页表了。 课程主页也有提示，没有可执行的进程时得切换到原始的kernel页表。 在found == 0时要切换回默认的kernel页表。

  • make qemu进入系统测试一下常用命令 没问题后输usertests进行系统各项测试。可能会持续十几分钟。虚拟机的话多给点内存，否则可能卡住。 最后打印出ALL TESTS PASSED说明成功。

做题3.简化copyin/copyinstr

  • 看懂copyin 给定页表，目标地址dst，起始地址va，长度len。把va开始的len长度的地址范围的数据复制到dst。 细节是头尾没页对齐的部分分别复制，中间对齐的部分整页整页地复制。

  • copyinstr 和copyin类似，给定最大长度，复制字符串。碰到0要停止。

  • lab2里用了copyout。总结一下。 copyout把物理地址的数据复制到目标虚拟地址转换后的物理地址。按课程的说法就是kernel的数据复制到user。 copyin 把虚拟地址转换后的物理地址的数据复制到目标物理地址。按课程的说法就是user的数据复制到kernel。 in就是进kernel。out就是出到user。 在exec流程里，user程序把参数地址(虚拟，用户只允许用虚拟地址)存进某个寄存器，再调用exec(system call)。 然后进入kernel程序，取user存的参数的虚拟地址，会用fetchaddr，最后用到copyin把虚拟地址的参数copy出来。

  • 任务是简化copyin。用vmcopyin.c里的copyin_new代替原始的copyin。 copyin_new直接一个memmove复制数据，不用一页页做地址转换再复制。

  • 这里卡了半天没懂他的意思。既然物理地址不一定连续，怎么可能用一个memmove复制连续物理地址上的大批数据呢？ 后来反复看手册和代码，参考网上的信息顿悟。

  • 这里有一个理解的缺失：kernel页表到底是用在哪的？ kernel_pagetable这个变量搜了所有代码，只有kvminithart里传进去，其他没有实质使用。

  • 大胆总结： kvminithart里是把kernel_pagetable喂给硬件分页了。 kvminit初始化时是把kernel data和freememory都线性映射到kernel_pagetable了(这里一直没仔细看)。 在一个较低的层面，可能是驱动或更下面，至少是memmove之下，硬件分页一定会按kernel_pagetable做一次转换的。 就是说memmove执行的时候会把地址按kernel_pagetable做一次转换。

  • 这样就清楚了，需要事先把用户虚拟地址上的数据都做好映射，同步到进程自己的kernel页表，再喂给硬件分页。 硬件分页处理用户进程，默认是用了线性的映射，现在要改成处理user页表的映射。 本质上就是要把copyin里的一页页转换交给硬件分页处理，从而简化了copyin的代码。 地址的转换仍然是存在的。

  • 需要把进程的user页表完全同步到kernel页表。 什么时候同步？user映射发生变化的时候。 仔细看代码会发现p->sz的变化总是伴随着user页表映射的变化。 刚好上边总结过p->sz的赋值情况。跟课程的提示完全一致。 那么p->sz发生变化的时候同步一下user页表就行了。

其他问题点

  • 页表、内存相关的边界处理一定要严谨，否则各种panic。必须看懂代码。

  • 同步user页表时PTE_U要关掉。否则copyin_new时会panic，因为PTE_U打开时kernel不允许读。 这个非常坑，课程有提示，但是很难联系上。

  • 需要同步user页表到kernel页表，但user地址空间是从0到MAXVA，与kvminit里kernel页表其他的初始化可能会冲突。 课程给的解法是把用户的最大虚拟地址定为kernel页表用到的最低的地址。课程说是PLIC，但看手册和代码最低是CLINT的0x2000000？？ growproc里扩大内存时先判断一下地址，如果大于PLIC返回-1。这样把虚拟地址控制在PLIC以下。 测试里的sbrkmuch会分配100m内存，如果限制在CLINT的话内存只有32m了，也会失败。

  • growproc里的同步 不能偷懒每次都unmap全部再map，这样太慢了。必须只更新扩大或缩小的部分，处理好边界和对齐问题。

  • 卡死的问题 最后测试还是会卡死，也不报错，不知道原因。单个测试某项能通过。 把切换kernel页表和copyin/copyinstr替换关掉就没问题。看来代码还是有问题。 发现多次运行不存在的命令后shell会卡死，cpu跑满。 仔细看下sh和exec的流程。

    main->userinit->init.c的main 死循环里先fork，子进程exec运行sh，父进程等待这个sh的结果。 sh.c里main不断等输入，就是我们看到的shell界面。 输入命令后fork，子进程调exec运行命令。父进程sh等待子进程返回。

    基本就是切换结束时某个环节出了问题。 颠来倒去查了很久实在没辙了。 看别人代码发现切换kernel页表swtch之后要立马切换回来。如果等到found==0才切换，某些情况会有概率回不来，原因暂不深究了。 这样测试能通过了。有恶心到。

  • sbrk问题 测试里有一个分配所有内存的操作，不断地分配直到返回0xffffffffffffffffLL，其实是-1。 运行make grade时sbrkmuch会失败。但单独运行usertests sbrkmuch是好的。先搁置。

  • 另一个卡死 exec里走到bad时不要回收kernel页表。在freeproc里回收就够了。

总结

  • 细节其实非常多，运气不好或者理解不够深就得花很多时间看代码和调试。 通过这次实验。研究了大量页表、内存分配和进程相关的底层代码。对内存操作有了很多新的认识。