Lab3-page tables && MIT6.1810操作系统工程【持续更新】

Lab：page tables

​        在这个lab中6.1810 / Fall 2025，要求我们先阅读xv6课本的Chapter 3 Page tables(第三章)。要求我们探索xv6当中关于页表的内容。并且要求我们实现一些页表相关功能的实现（例如：虚地址和物理地址的映射/解除映射，页表的创建和释放等）。
​        并且官网也给出了提示：

• 在kernel/memlayout.h当中存放了内存布局，页表大小相关的常量就在此。
  
• 在kernel/vm.c当中是页表相关逻辑的实现，接下来的大部分lab内容就在此实现。
  
• 在kernel/kalloc.c当中存放的时内存分配相关的逻辑，在新建/删除页表时会用到这里的函数。
  

Speed up system calls （简单）

​        在这个lab当中，要求我们在 xv6 中添加一个新的 用户可读的只读内存映射（USYSCALL），用来让用户态程序在不陷入内核的情况下，直接读取部分内核数据（如 pid），并正确处理其 创建、映射、访问与释放的完整生命周期。
如何将一个用户可读的只读内存映射（USYSCALL）添加到进程页表内？以及如何删除该映射？

​        前言和注意事项：在xv6当中的有关进程的创建/释放，进程页表的创建/释放的过程都在kernel/proc.h,并且按照官网的说法，我们需要将进程的pid存放到内存当中，这样在调用gitpid系统调用时，则直接选择从内存空间当中读取该pid，大大提高了执行效率，并且不用陷入到内核态；这就意味着我们需要在进程的结构体当中添加一个成员用于指向存放当前进程的pid的空间，为了之后的读取。
​        一、分配物理内存：
​                前面提到过，进程的结构体成员当中有指向进程pid的指针(struct usyscall *)，因此，我们需要先给他分配物理内存（由内核分配）。

1. p->usyscall = (struct usyscall *)kalloc(); //分配物理内存

复制代码

​        二、初始化内容：
​                将当前进程的pid存放到刚才的指针p->usyscall所指向的空间中。

1. p->usyscall->pid = p->pid;
3. // 以下是xv6提前写好的，改进后的ugetpid方法
4. int
5. ugetpid(void)
6. {
7.   struct usyscall *u = (struct usyscall *)USYSCALL;  //通过虚拟地址USYSCALL访问特点内存
8.   return u->pid;
9. }

复制代码

​                为什么我们必须通过struct usyscall *来访问，而不是直接返回进程结构体当中的pid呢？
​                答：首先，xv6有内核页表和用户页表，并且用户态下的进程只能看得见内存。因为进程的结构体存放在内核页表当中，在用户态下我们只能访问到用户页表，所以准确来说我们只能通过虚拟内存搭配页表机制的方式来访问存放在该物理空间当中内容。我们在内核态下通过p->usyscall = (struct usyscall *)kalloc(); 分配的内存似乎也是被内核所管理，但是我们将USYSCALL这个虚拟地址和物理地址相映射了起来，因此我们可以通过在用户态下访问该虚拟地址的方式下访问到具体的物理地址当中的值。
​        三、创建用户页表：
​                众所周知，OS当中的进程采用页表机制来将进程的虚地址映射到物理地址上，所以说无论我们是否要添加映射到页表中，我们都必不可免地要创建一个用户页表。

1. p->pagetable = proc_pagetable(p);

复制代码

​        四、建立虚拟地址  到  物理地址映射:
​                说白了就是在用户页表中添加一个新的页表项，所以这一步的操作要在页表的相关逻辑当中进行，该页表项用于映射到刚才分配的物理内存。在kernel/defs.h当中，我们可以看到mappages的声明（该函数用于添加映射到页表）。
​                注意：页表机制是将进程的虚拟地址映射为内存中真实的物理地址，所以在添加新的映射时，要一并给出这些参数以及映射大小和权限。

1. // 映射 USYSCALL
2.   if(mappages(pagetable,
3.               USYSCALL,  //虚拟地址
4.               PGSIZE,  // 映射大小
5.               (uint64)p->usyscall, //物理地址
6.               PTE_R | PTE_U | PTE_V) < 0){  // 官网要求设置的权限
7.     uvmfree(pagetable, 0);
8.     return 0;
9.   }

复制代码

​                xv6的权限（添加权限的目的是防止“篡改”，“非法访问”等等操作）：
位含义PTE_R用户可读PTE_W防止用户写PTE_X防止执行PTE_U用户态可访问PTE_V映射有效​        五、删除/释放映射:
​                首先在页表释放的相关逻辑当中进行释放映射的操作，在kernel/defs.h当中，我们可以看到uvmunmap的声明（该函数用于删除/释放映射到页表）。

1. uvmunmap(pagetable, USYSCALL, 1, 0); //释放USYSCALL

复制代码

​                之后在进程释放的相关逻辑进行释放之前访问的物理空间的操作，在kernel/defs.h当中，我们可以看到kfree的声明（该函数用于释放分配的内存）。

1. kfree(p->usyscall);

复制代码

​        六、深入了解进程和页表的底层逻辑：
函数（kernel/proc.c）负责什么allocproc分配“进程资源”（pid、usyscall、trapframe、kstack）(第一，二，三步在此进行)freeproc释放“进程资源” （第五步后半部分在此进行）proc_pagetable构造页表结构 （第五步前半部分在此进行）proc_freepagetable拆除页表结构 （第四步在此进行）​                由此我们可以得知页表的生命周期几乎伴随整个进程。
代码的相关内容：

1. /* kernel/proc.c */
2. static struct proc*
3. allocproc(void)
4. {
5.   struct proc *p;
7.   for(p = proc; p < &proc[NPROC]; p++) {
8.     acquire(&p->lock);
9.     if(p->state == UNUSED) {
10.       goto found;
11.     } else {
12.       release(&p->lock);
13.     }
14.   }
15.   return 0;
17. found:
18.   p->pid = allocpid();
19.   p->state = USED;
20.   // 分配物理内存
21.   p->usyscall = (struct usyscall *)kalloc();
22.   if(p->usyscall == 0){
23.     freeproc(p);
24.     release(&p->lock);
25.     return 0;
26.   }
27.   // 初始化内容
28.   p->usyscall->pid = p->pid;
30.   // Allocate a trapframe page.
31.   if((p->trapframe = (struct trapframe *)kalloc()) == 0){
32.     freeproc(p);
33.     release(&p->lock);
34.     return 0;
35.   }
37.   // An empty user page table.
38.   p->pagetable = proc_pagetable(p);
39.   if(p->pagetable == 0){
40.     freeproc(p);
41.     release(&p->lock);
42.     return 0;
43.   }
45.   // Set up new context to start executing at forkret,
46.   // which returns to user space.
47.   memset(&p->context, 0, sizeof(p->context));
48.   p->context.ra = (uint64)forkret;
49.   p->context.sp = p->kstack + PGSIZE;
51.   return p;
52. }
54. // free a proc structure and the data hanging from it,
55. // including user pages.
56. // p->lock must be held.
57. static void
58. freeproc(struct proc *p)
59. {
60.   // 释放之前分配的物理内存
61.   if(p->usyscall){
62.     kfree((void*)p->usyscall);
63.     p->usyscall = 0;
64.   }
65.   if(p->trapframe)
66.     kfree((void*)p->trapframe);
67.   p->trapframe = 0;
68.   if(p->pagetable)
69.     proc_freepagetable(p->pagetable, p->sz);
70.   p->pagetable = 0;
71.   p->sz = 0;
72.   p->pid = 0;
73.   p->parent = 0;
74.   p->name[0] = 0;
75.   p->chan = 0;
76.   p->killed = 0;
77.   p->xstate = 0;
78.   p->state = UNUSED;
79. }
81. // Create a user page table for a given process, with no user memory,
82. // but with trampoline and trapframe pages.
83. pagetable_t
84. proc_pagetable(struct proc *p)
85. {
86.   pagetable_t pagetable;
88.   // An empty page table.
89.   pagetable = uvmcreate();
90.   if(pagetable == 0)
91.     return 0;
93.   // 映射 USYSCALL（也是关键部分）
94.   if(mappages(pagetable,
95.               USYSCALL,  //虚拟地址
96.               PGSIZE,  // 映射大小
97.               (uint64)p->usyscall,  //物理地址
98.               PTE_R | PTE_U | PTE_V) < 0){ // 权限
99.     uvmfree(pagetable, 0);
100.     return 0;
101.   }
102.   
104.   // map the trampoline code (for system call return)
105.   // at the highest user virtual address.
106.   // only the supervisor uses it, on the way
107.   // to/from user space, so not PTE_U.
108.   if(mappages(pagetable, TRAMPOLINE, PGSIZE,
109.               (uint64)trampoline, PTE_R | PTE_X) < 0){
110.     uvmfree(pagetable, 0);
111.     return 0;
112.   }
114.   // map the trapframe page just below the trampoline page, for
115.   // trampoline.S.
116.   if(mappages(pagetable, TRAPFRAME, PGSIZE,
117.               (uint64)(p->trapframe), PTE_R | PTE_W) < 0){
118.     uvmunmap(pagetable, TRAMPOLINE, 1, 0);
119.     uvmfree(pagetable, 0);
120.     return 0;
121.   }
123.   return pagetable;
124. }
126. // Free a process's page table, and free the
127. // physical memory it refers to.
128. void
129. proc_freepagetable(pagetable_t pagetable, uint64 sz)
130. {
131.   uvmunmap(pagetable, USYSCALL, 1, 0);  //释放/删除USYSCALL对应的映射
132.   uvmunmap(pagetable, TRAMPOLINE, 1, 0);
133.   uvmunmap(pagetable, TRAPFRAME, 1, 0);
134.   uvmfree(pagetable, sz);
135. }

复制代码

Print a page table （简单）

​        这个lab要求我们实现一个打印页表的函数，同时也能帮助我们理解xv6当中，页表是如何实现的。在本次实验前，这门课程的作者已经将kpgtbl（）这个系统调用添加到内核当中了，现在我们要做的就是完善kernel/vm.c当中的vmprint()函数，这个函数接收一个pagetable_t（页表类型）的参数。
xv6当中的页表是怎样的？

​        零、专业词汇阐述
名称含义VA虚拟地址（CPU 使用）PTE页表项（映射 + 权限）PA物理地址（RAM 索引）PPN物理页号（PA 的高位）​        一、虚拟地址va的结构和xv6当中的三级页表
​                根据本课程对应的课本xv6 book 当中的第三章，我们可以得知在xv6当中，虚拟地址va的位数为64位，并且我们只使用低39位，高25位用于扩展。相信你在看到这里时肯定学过操作系统这门课程，在任何一本操作系统的教科书当中，对于虚拟地址va的构成的描述都是低n位是页内偏移地址，用于定位某页内的页表项，剩下的高位都是索引，用于定位到某一页。
​                在xv6当中，页表的每页大小为4096B，每个页表项（PTE）的大小为8B，所以一个页表的当中有4096/8 = 512个PTE。所以39位的虚拟地址va当中，低12位为页内偏移量，省下的27位用于索引页表。
​                xv6采用三级页表，也就是说27位的索引地址，每9位构成一个层级，类似一个树。以下内容是39位虚拟地址的构成。
​                PS：（床图网站随时可能失效，所以下面我尽量使用文字来进行描述）。

1. |VPN[2] | VPN[1] | VPN[0]|页内偏移|
2.   9        9        9                12       共39位
3. 一级索引  二级索引  三级索引  页内偏移量   总位数
4.   根                叶子

复制代码

​                寻址时，先访问VPN[2]当中的某个PTE，该PTE指向VPN[1]，之后从VPN[1]中选取新的PTE，再次通过新的PTE寻址VPN[0]，用VPN[0]获得最终的PTE后即可获得PNN（物理页号）。最后通过对PNN操作得到PA（物理地址）。整个过程类似寻找树的叶子结点那样，一层一层向下寻找。
​        二、为什么xv6采用三级页表？
​                 进程在创建之初，必须且至少拥有一个页表。
如果采用一级页表设计，为了满足这一必须的条件，操作系统必须一次性分配一张覆盖整个虚拟地址空间的页表，即使进程只使用其中极小的一部分（大部分内存空间会浪费掉），也必须遵守该规定。
​                而在采用三级页表的设计中，进程创建时只需要分配一个 4KB 的根页表页，其余页表页在虚拟地址空间被实际使用时才按需分配。
​        二、PTE的内容
​                已知每个PTE的大小为8B，即一共64位。其中低10位（90位）为flags（权限位/标记），剩下的高位（5310位共44bit）为PNN（物理页框号，分配内存之时，OS从空闲页框表当中的表头取下来的）。最后的10位（63~54位）暂时未用，置为0。
​                flags的内容：
位含义V是否有效R可读W可写X可执行U用户可访问A/D硬件访问/修改标记​        当一个 PTE 的 R/W/X 任一位为 1 时，该 PTE 是叶子结点，指向真实物理页；
​        若 R/W/X 全为 0 且 V=1，则该 PTE 指向下一级页表。
​        页表的本质除了指明虚拟地址映射到哪里外，还可以决定这个地址是否可读，是否可写，是否可执行，是否可用户态访问/执行。
三、PNN如何转为物理地址
​                xv6当中规定物理地址的位数为56位，由PNN和va的低12位拼接而成，具体操作手法如下：
​                1、首先讲PTE右移10位，这样低10位的flags会消失。
​                2、之后讲PTE左移12位，这样低12位的空白正好可以由虚拟地址的低12位偏移量进行填补。
​                3、我们现在需要将虚拟地址va的第12位进行填补，所以我们将va和0xFFF相与，这样va就只剩下了第12位的偏移量。
​                4、将PTE和va相加或着进行“逻辑或”操作，这样就拼接好了一个完整的物理地址。
​                注意：在xv6当中，以上的操作都有着对应的宏，在编码时可以直接使用宏操作。
该lab的实现和代码相关内容

​        一、个人的解析和官网提示

• 打印格式：第一行显示 vmprint 的参数。之后，每个页表项（PTE）对应一行，包括那些指向树中更深层次页表页的页表项。每个页表项行都缩进若干个 “..”，以表示其在树中的深度。每个页表项行都会显示其虚拟地址、页表项位以及从该页表项中提取的物理地址。不要打印无效的页表项。
  
• 在kernel/riscv.h的文件末尾，有关于va转pa的宏。
  
• freewalk这个函数也许会带来启发。
  
• 在printf调用中使用%p，以官网上示例所示的方式打印完整的64位十六进制页表项（PTE）和地址。
  

​        二、代码相关内容

1. ##在kernel/vm.c文件内：
3. static void
4. vmprint_walk(pagetable_t pagetable, int level, uint64 va){
5.   //每个页表521个PTE
6.   for(int i = 0; i < 512; i++){
7.     pte_t pte = pagetable[i];
8.     // pte有效 并且 V位为1则不是叶子结点
9.     if((pte & PTE_V) == 0)
10.       continue;
11.     // 将传入的PA物理地址（此时PA第12位为空）和偏移量相加合并为完整的物理地址
12.     uint64 newva = va | ((uint64)i << (12 + 9 * level));
14.     // 打印层级， depth = 2 - level
15.     for(int d = 0; d < 2 - level; d++)
16.       printf(" ..");
18.     printf("%p: pte %p pa %p\n",
19.            (void*)newva,
20.            (void*)pte,
21.            (void*)PTE2PA(pte));
23.     // 不是叶子结点则向下递归
24.     if((pte & (PTE_R | PTE_W | PTE_X)) == 0){
25.       // PTE2PA是将pte转为了物理地址PA（此时低12位为空）
26.       pagetable_t child = (pagetable_t)PTE2PA(pte);
27.       vmprint_walk(child, level - 1, newva);
28.     }
29.   }
31. }
33. #if defined(LAB_PGTBL) || defined(SOL_MMAP) || defined(SOL_COW)
34. void
35. vmprint(pagetable_t pagetable) {
36.   // your code here
37.   // 打印第一行，之后递归进行遍历
38.   printf("page table %p\n", pagetable);
39.   vmprint_walk(pagetable, 2, 0);
40.   
41. }
42. #endif

复制代码

​        5、修改mappages函数。

1. |VPN[2] | VPN[1]（包含VPN[0]）|页内偏移|
2.   9        9        9                   12       共39位
3. 一级索引         二级索引      页内偏移量   总位数
4.   根              叶子
5. ===============================
6. level-2 (512GB)
7.   |
8. level-1 (2MB)   ← ★ superpage 在这里（第一层）
9.   |
10. level-0 (4KB)   ← 普通的页面在这里（第0层）

复制代码

​        8、添加uvmcopy函数。

1. struct {
2.   struct spinlock lock;
3.   struct run *freelist;
4.   struct run *superfreelist;   // 仿照上面的freelist
5. } kmem;
7. void
8. freerange(void *pa_start, void *pa_end)
9. {
10.   char *p;
11.   p = (char*)PGROUNDUP((uint64)pa_start);
12. #ifndef LAB_PGTBL
13.   for(; p + PGSIZE <= (char*)pa_end; p += PGSIZE)
14.     kfree(p);
15. #else
16.   int superpg_num = 10;
17.   // 计算超级页的起始地址，从 pa_end 向下对齐到超级页边界
18.   char *superp = (char*)SUPERPGROUNDUP((uint64)pa_end - superpg_num * SUPERPGSIZE);
19.   // 先释放普通页面部分
20.   for(; p + PGSIZE <= superp; p += PGSIZE)
21.     kfree(p);
22.    // 再释放超级页部分
23.   for(; superp + SUPERPGSIZE <= (char*)pa_end; superp += SUPERPGSIZE)
24.     superfree(superp);
25. #endif
26. }
28. #ifdef LAB_PGTBL
29. // 超级页释放函数
30. void
31. superfree(void *pa)
32. {
33.   struct run *r;
34.   // 参数验证：确保 pa 对齐到超级页大小且在合法内存范围内
35.   if(((uint64)pa % SUPERPGSIZE) != 0 || (char*)pa < end || (uint64)pa >= PHYSTOP)
36.     panic("superfree");
37.   
38.   memset(pa, 1, SUPERPGSIZE);
39.   r = (struct run*)pa;
40.   //加锁
41.   acquire(&kmem.lock);
42.   r->next = kmem.superfreelist;
43.   // 将超级页插入空闲链表头部
44.   kmem.superfreelist = r;
45.   //解锁
46.   release(&kmem.lock);
47. }
49. // 超级页分配函数
50. void *
51. superalloc(void)
52. {
53.   struct run *r;
54.   acquire(&kmem.lock);
55.   // 从空闲链表中取出一个超级页
56.   r = kmem.superfreelist;
57.   if(r)
58.     kmem.superfreelist = r->next;
59.   release(&kmem.lock);
60.   if(r)
61.     memset((char*)r, 5, SUPERPGSIZE);
62.    // 返回分配的超级页地址
63.   return (void*)r;
64. }
65. #endif

复制代码

写在后面

​        这一lab，尤其是最后的用户页表lab确实非常难，一开始花费了好长时间都没做出来，好在网络上有很多大佬对该lab进行了讲解和提供了成品代码，使得本人在后续的研究中才得以明白该lab的底层逻辑。

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！

感谢分享，学习下。

不错，里面软件多更新就更好了

用心讨论，共获提升！

这个好，看起来很实用

yyds。多谢分享

谢谢楼主提供！

yyds。多谢分享

喜欢鼓捣这些软件，现在用得少，谢谢分享！

谢谢分享，辛苦了

谢谢分享，试用一下

新版吗？好像是停更了吧。