特色栏目： python 批处理 net编程 Javascript Php Asp Css Html5 Android seo centos

MIT6.S081-Lab3 Pgtbl

来源：互联网收集：自由互联发布时间：2022-05-30

开始日期： 22.3.27 操作系统： Ubuntu20.0.4 Link：Lab Pgtbl 个人博客：Memory Dot 目录 Lab Pgtbl 写在前面 ansewer-pgtbl.txt 调试的端口号被占用格式符 %p 在windos10和linux的区别补充 (参考)链接 Spee

开始日期：22.3.27

操作系统：Ubuntu20.0.4

Link：Lab Pgtbl

个人博客：Memory Dot

Lab Pgtbl
- 写在前面
  - ansewer-pgtbl.txt
  - 调试的端口号被占用
  - 格式符%p在windos10和linux的区别
  - 补充
  - (参考)链接
- Speed up system calls (easy)
- Print a page table (easy)
- Detecting which pages have been accessed (hard)
- 总结

Lab Pgtbl 写在前面 ansewer-pgtbl.txt

这里填写对问题一、二的回答，才能通过测试

调试的端口号被占用

我这里的qemu调试时的端口号是26000

*** Now run 'gdb' in another window.
qemu-system-riscv64 -machine virt -bios none -kernel kernel/kernel -m 128M -smp 3 -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

需要杀死占用端口号的进程，才能调试

sudo lsof -i tcp:26000 #查询使用26000的进程，打印对应的pid
sudo kill <pid> #将对应pid的进程杀死即可

格式符%p在windos10和linux的区别

如下程序段，在windos10和linux的输出是不同的
- win10中不会输出前缀0x，但Linux会输出前缀0x
- 这个区别会在Print a page table (easy)中用到
```
/* test.c */
#include <stdio.h>

int main(){
    printf("%p", 1111);
}
```

win10的输出

PS D:\VSCode\vscode_a\os> cd "d:\VSCode\vscode_a\os\xv6-labs-2021\" ; if ($?) { gcc test.c -o test } ; if ($?) { .\test }
0000000000000457

linux的输出

duile@ubuntu:~/Desktop/cpp$ ./test
0x457

补充

做题时当然是按照hints顺序来写的，本篇博客是总结整体思路，尽量按照流程来
头两个实验末尾时都会提出个问题，笔者也统一放在实验的末尾

(参考)链接

6.S081-2021FALL-Lab3:pgtbl
MIT6.S081的学习笔记
推荐一位pku前辈的学习路线：CS自学指南，笔者看到了一位热爱计算机的人

Speed up system calls (easy)

简述题意：给系统调用函数ugetpid()提速，方法是给每个进程的单独内存空间里添加一个USYSCALL页面，而里头存放一个系统函数会经常使用的数据，这里专指pid，而我们把pid存放在struct usyscall中。
- 通过上述方法，ugetpid()需要用到pid时，会在用户态使用USYSCALL页面直接调用，而不用切换到内核态
```
/* kernel/memlayout.h */
...
struct usyscall {
  int pid;  // Process ID
};
```
如何添加USYSCALL页面呢？首先找到位置，然后完成两步，第一步是完成页面映射；第二步是分配内存空间
参考一个单独进程的内存空间book-riscv-rev2.pdf所存储的内容（Figure 3.4）以及proc_pagetable.c(kernel/proc.c)，可以猜测，USYSCALL页面的位置在heap之前，trapfram之后

完成页面映射

参考TRAMPOLINE(蹦床)、TRAPFRAME(陷阱帧)页面的映射方式即可
USYSCALL允许用户read操作，所以mappages的最后参数使用PTE_R | PTE_U
如果映射失败，需要先将TRAMPOLINE以及TRAPFRAME页面解除映射，再将整个进程的内存空间释放掉（此时的pagetable就是这个程序的程序页面）

// Create a user page table for a given process,
// with no user memory, but with trampoline pages.
pagetable_t
proc_pagetable(struct proc *p)
{	
  pagetable = uvmcreate();
  if(pagetable == 0)
    return 0;
  ...
  // map the USYSCALL just below TRAMPOLINE and TRAPFRAME
   if(mappages(pagetable, USYSCALL, PGSIZE,
              (uint64)(p->usyscall), PTE_R | PTE_U) < 0){
    uvmunmap(pagetable, TRAMPOLINE, 1, 0);
    uvmunmap(pagetable, TRAPFRAME, 1, 0);
    uvmfree(pagetable, 0);
    return 0;
  }

  return pagetable;
}

分配内存空间

参考TRAPFRAME页面的分配内存方式即可，代码如下
- 注意最后要将pid返回到用户态，这样才能在用户态直接使用pid
- 记得结构体struct proc中需要多添加一条struct usyscall *usyscall
- 这里没有分配内存空间给TRAMPOLINE，因为事实上TRAMPOLINE已经映射到内核的内存空间了，没错，就是一开始xv6系统启动时的那个系统内核

// Look in the process table for an UNUSED proc.
// If found, initialize state required to run in the kernel,
// and return with p->lock held.
// If there are no free procs, or a memory allocation fails, return 0.
static struct proc*
allocproc(void)
{
 ... 
  // Allocate a USYSCALL page.
  if((p->usyscall = (struct usyscall *)kalloc()) == 0){
    freeproc(p);
    release(&p->lock);
    return 0;
  }
  
  // An empty user page table.
  p->pagetable = proc_pagetable(p);
  if(p->pagetable == 0){
    freeproc(p);
    release(&p->lock);
    return 0;
  }
  // Set up new context to start executing at forkret,
  // which returns to user space.
...
    p->context.sp = p->kstack + PGSIZE;
	p->usyscall->pid = p->pid;
  return p;
}

注意如果分配失败，会调用freeproc()，因此要比之前多释放掉一个p->usyscall参数，同时还会再调用proc_freepagetable，这里也需要多解除一个对USYSCALL页面的映射。

static void
freeproc(struct proc *p)
{
  if(p->trapframe)
    kfree((void*)p->trapframe);
  p->trapframe = 0;
  p->usyscall = 0;
  ...
    
// Free a process's page table, and free the
// physical memory it refers to.
void
proc_freepagetable(pagetable_t pagetable, uint64 sz)
{
  uvmunmap(pagetable, TRAMPOLINE, 1, 0);
  uvmunmap(pagetable, TRAPFRAME, 1, 0);
  uvmunmap(pagetable, USYSCALL, 1, 0);
  uvmfree(pagetable, sz);
}

Which other xv6 system call(s) could be made faster using this shared page? Explain how.
- 可以加速fork()，通过在struct usyscall中添加一个parent数据，以供child们需要的时候在用户态直接使用USYSCALL页面调用，而不用切换到内核态
```
/* kernel/memlayout.h */
...
struct usyscall {
  int pid;  // Process ID
  struct proc *parent  // Parent process 
};
```

Print a page table (easy)

简述题意：打印xv6系统的第一个页面的所有内容，方法是编写一个vmprint()函数，当第一个程序启动时执行该函数即可
- 这个第一个页面就是根页面
- 当然，这个第一个程序就是启动xv6系统

/* kernel/exec.c */
int
exec(char *path, char **argv)
{
 ... 
  if(p->pid==1) {
  	vmprint(p->pagetable);
  }
  return argc; // this ends up in a0, the first argument to main(argc, argv)
  ...

下面就是编写vmprint()了，主要参考了freewalk，我们先看看freewalk是怎么编写的。

// Recursively free page-table pages.
// All leaf mappings must already have been removed.
void
freewalk(pagetable_t pagetable)
{
  // there are 2^9 = 512 PTEs in a page table.dain
  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((pagetable_t)child);
      pagetable[i] = 0;
    } else if(pte & PTE_V){
      panic("freewalk: leaf");
    }
  }
  kfree((void*)pagetable);
}

可以看出，该函数主要功能是遍历所给页面的所有PTE(条目)，包括它子页面的所以PTE，同时将所以PTE置0
- 因为要进入到子页面所以使用了递归（Recurse）
  - 何时迭代呢？就是当该条目有效，但却无法读、写、执行的时候，说明这是一条指向子页面的PTE，即 if((pte & PTE_V) && (pte & (PTE_R|PTE_W|PTE_X)) == 0)
- 遇到leaf PTE的时候会报错
```
// All leaf mappings must already have been removed.
```
  - 显然，在执行freewalk之前，所有的叶PTE必须被移除

那么vmprint的功能就能想出来了，参照着格式来

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
 .. .. ..509: pte 0x0000000021fdd813 pa 0x0000000087f76000
 .. .. ..510: pte 0x0000000021fddc07 pa 0x0000000087f77000
 .. .. ..511: pte 0x0000000020001c0b pa 0x0000000080007000

我们多写一个辅助函数recurse_treepage来实现递归

页表是分为三层的，所以用level来标记到哪一次了
如果有效就立刻打印，同时在有效的情况下，无法读、写、执行该PTE就进入递归
注意，是有效时先立刻打印，不能先进入递归，否则会导致整个页面信息的输出顺序反了
- 如果先进入递归了，可以想象为创建了一个堆，最上层即第一次函数调用recurse_treepage放入堆的最底层，因为先进后出，第一层页面最后打印，第二层页面是中间打印，第三层页面最先打印，和我们想要的顺序相反了！

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

void
recurse_treepage(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_V is vaild, print infomation
    // level == 0 => top; level == 1 => middle; level == 2 => bottom;
    if(pte & PTE_V) {
      for(int j = 0; j <= level ; j++){
        if (j == 0)
          printf("..");
        else
          printf(" ..");
      }
      uint64 child = PTE2PA(pte);
      printf("%d: pte %p pa %p\n", i, pte, child);
      // this PTE points to a lower-level page table.
      if((pte & (PTE_R|PTE_W|PTE_X)) == 0)
        recurse_treepage((pagetable_t)child, level + 1);
    }     
  } 
}

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? What does the third to last page contain?
- FIG 3-4 就是book-riscv-rev2.pdf所存储的内容（Figure 3.4）
- 根据图片就可以回答问题了
```
page0: date and text of process
page1: guard page for protect stack by present page0 overflow
page2: stack of process
page3 to last page: heap, trapfram, trampoline
```
- 程序在用户态运行时是不能读/写page1（即guard page）的，它本身就是用来保护page2即（stack page）不被用户访问

Detecting which pages have been accessed (hard)

简述题意：编写sys_pgaccess()，检测页面是否被访问，这里需要注意两点，一是该函数的输入参数，二是该函数的输出结果。
输入参数有三个：第一个被检测页面的虚拟地址，被检测页面总数，输出结果的用户态地址
输出结果是通过copyout()从内核态传出到用户态的，自然需要一个用户态地址，同时需要注意的是，该结果是一个32bits的数据，我们也恰好要检测32个页面（参考user/pgtbltest.c/pgaccess_test()），第1个页面如果被访问了，就将0bit位设置为1；第2个页面如果被访问了，就将1bit位设置为1，以此类推，第32个页面对应31bit位。反之，没被访问就设置为0
eg. 第4，13，28bit位被访问了，其它没有被访问，图示如下
接下来我们进一步明晰整个检测过程
- 首先，用户先访问了一些页面，xv6系统会将被访问页面的PTV_A标志位设置为1
- 其次，用户调用pgaccess()，检测页面是否被访问
- 然后，pgaccess()返回结果，同时，将已被访问页面的PTV_A标志位设置为0，这是为了防止调用过一次pgaccess()之后，再也无法判断该页面是否已经被访问。（更切确地说，每一次调用pgaccess之前，用户都会访问一些页面，如果我们在上一次调用pgaccess时保持为1，就无法判断本次这些保持为1页面是否被访问）
  
  Be sure to clear PTE_A after checking if it is set. Otherwise, it won't be possible to determine if the page was accessed since the last time pgaccess() was called (i.e., the bit will be set forever).
- 图示如下
接下来就是参考代码的cv时间了，使用了walk，该函数是遍历三层页表树，通过va在当前页表中找出对应的pte地址，同时它还有一个alloc参数，如果这个参数不为0，它就会为找不到的对应pte地址的va额外申请一个页面来对应，反之alloc为0的话则不会。我们当然是设置为0，我们只是查询，不能去申请多的页面。
- 这里会有一个当前页面从哪里来的问题，后来看到pgaccess_test()就懂了，这是一整个测试程序，它会调用proccess()，在这个测试程序中就创建了32个页面，xv6系统会把部分页面设置为已被访问，而32个页面自然就存储在测试程序的程序页表中
- 贴一下pgaccess_test()
```
/* user/pgtbltest.c */
void
pgaccess_test()
{
  char *buf;
  unsigned int abits;
  printf("pgaccess_test starting\n");
  testname = "pgaccess_test";
  buf = malloc(32 * PGSIZE);
  if (pgaccess(buf, 32, &abits) < 0)
    err("pgaccess failed");
  buf[PGSIZE * 1] += 1;
  buf[PGSIZE * 2] += 1;
  buf[PGSIZE * 30] += 1;
  if (pgaccess(buf, 32, &abits) < 0)
    err("pgaccess failed");
  if (abits != ((1 << 1) | (1 << 2) | (1 << 30)))
    err("incorrect access bits set");
  free(buf);
  printf("pgaccess_test: OK\n");
}
```
然后主要参考了walkaddr来编写
- 从trapfram中获取参数需要用到agraddr，agrint，记得按参数顺序获取
- 如果总数越界，需要报错 if(len < 0 || len > 32) return -1;
  
  It's okay to set an upper limit on the number of pages that can be scanned.
- 注意我们不需要检测其它标志位，只检测PTE_A
- PTE_A的具体标志位位置需要根据riscv-privileged来，具体参考p77
  
  Each leaf PTE contains an accessed (A) and dirty (D) bit. The A bit indicates the virtual page has been read, written, or fetched from since the last time the A bit was cleared.
- 添加PTE_A
```
/* kernel/riscv.h */
...
#define PTE_U (1L << 4) // 1 -> user can access
#define PTE_A (1L << 6) // 1 -> page already be accessed
```
  - 核心部分需要用到一个for循环，跳到下个页面用va += PGSIZE即可
  - 如果已被访问，先添加到结果的对应bit位中，再置0
代码

#ifdef LAB_PGTBL
// Return bitmask to user by detecting which page have been accessed.
uint64
sys_pgaccess(void)
{ 
  uint64 va;
  int len;
  uint64 abits_addr;
  if(argaddr(0, &va) < 0)
    return -1;
  if(argint(1, &len) < 0)
    return -1;
  if(argaddr(2, &abits_addr) < 0)
    return -1;
  if(len < 0 || len > 32)
    return -1;
  
  uint32 ret = 0;
  pte_t *pte;
  struct proc *p = myproc();

  for(int i = 0; i < len; i++){
    if(va >= MAXVA)
      return -1;

    pte = walk(p->pagetable, va, 0);
    
    if(pte == 0)
      return -1;
    /* if pte has been accessed add bit of ret and clear*/
    if(*pte & PTE_A){
      ret |= (1 << i);
      *pte &= (~PTE_A);
    }
    /* va of next page */
    va += PGSIZE;    
  }

  if(copyout(p->pagetable, abits_addr, (char*)&ret, sizeof(ret)) < 0)
    return -1;
  return 0;
}
#endif

总结

完成日期22.4.1
笔者有个小bug其实很尴尬，就是一开始没把代码编到#ifdef LAB_PGTBL...#endif之间，找了我1个小时多。。。
参考测试程序来理清思路是很有用的，尤其是最后一个实验中的三个输入参数到底是啥
代码是可以很优雅，很艺术的，把计算机科学当作一门艺术来学，而不是技术。这门学科可以是目的，而不是所谓手段。我感觉我要爱上这门艺术了。（最近在看Crash Course Computer Science，我是把它当作计算机科学史来看的，无数的前辈是如此地热爱这门艺术）
最近在听电影《飞驰人生》的片尾曲：《奉献》

【文章原创作者：欧洲服务器 http://www.558idc.com/helan.html 复制请保留原URL】

上一篇：Dockerfile同时配置tomcat和jar包运行
下一篇：没有了

MIT6.S081-Lab3 Pgtbl

相关文章