• 欢迎大家分享资料!前往留言板评论即可!

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

合宙 模组资料网 5个月前 (05-15) 85次浏览 已收录 0个评论 扫描二维码

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,从KERNBASEPHYSTOP)。
    也会模拟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)。
    endPHYSTOP就是被内存管理系统控制(通过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之后要立马切换回来。如果等到found0才切换,某些情况会有概率回不来,原因暂不深究了。
    这样测试能通过了。有恶心到。

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

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


总结

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


喜欢 (1)
发表我的评论
取消评论

表情 贴图 加粗 删除线 居中 斜体

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址