xv6-Lab3

First Post:

Last Update:

Word Count:
1.8k

Read Time:
8 min

Lab3 page tables

Speed up system calls

主要思路

根据题中所给的Hints以及参考书的Chapter 3,要实现对getpid()的加速，就是将进程的pid信息存放在内核和用户共用的一片存储空间中，从而在ugetpid()的时候程序不用陷入内核态，实现对getpid()的加速。
实现流程如下：

  • 首先在kernel/proc.h中添加如下代码来作为上述共享空间：
    1
    struct usyscall *usyspage;   // 用户与内核共享页
  • 接着在kernel/proc.c中添加如下代码来为这个页面分配空间并将目标值装入页面：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    static struct proc*
    allocproc(void)
    {
      ...
      // Allocate a trapframe page.
      if((p->trapframe = (struct trapframe *)kalloc()) == 0){
        freeproc(p);
        release(&p->lock);
        return 0;
      }

      // 给共享页分配空间(add)
      if((p->usyspage = (struct usyscall *)kalloc()) == 0){
        freeproc(p);
        release(&p->lock);
        return 0;
      }
      p->usyspage->pid = p->pid;

      ...

      return p;
    }
  • 在销毁进程时要记得将页面空间释放并避免野指针(kernel/proc.c)：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    static void
    freeproc(struct proc *p)
    {
     ...

      if(p->usyspage)
        kfree((void*)p->usyspage);
      p->usyspage = 0;

      ...
    }
  • 在页表中建立映射(kernel/proc.c),注意题中要求，该页的权限为用户只读:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    // Create a user page table for a given process, with no user memory,
    // but with trampoline and trapframe pages.
    pagetable_t
    proc_pagetable(struct proc *p)
    {
      ...

      // 建立从USYSCALL到p->usyspage的映射，权限为用户只读
      if(mappages(pagetable, USYSCALL, PGSIZE,
                  (uint64)(p->usyspage), PTE_R | PTE_U) < 0){
        uvmfree(pagetable, 0);
        return 0;
      }

      // map the trampoline code (for system call return)
      // at the highest user virtual address.
      // only the supervisor uses it, on the way
      // to/from user space, so not PTE_U.
      ...
    }
  • 同样在进程结束释放页表的时候要记得取消映射(kernel/proc.c)：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    // Free a process's page table, and free the
    // physical memory it refers to.
    void
    proc_freepagetable(pagetable_t pagetable, uint64 sz)
    {
      ...

      uvmunmap(pagetable, USYSCALL, 1, 0);
      uvmfree(pagetable, sz);
    }

    Q:Which other xv6 system call(s) could be made faster using this shared page? Explain how.

系统调用sys_sbrk也可以用此页来加速，因为该函数返回的是myproc()->sz,因此我们可以将myproc()->sz也在进程初始化的时候存在该页中，就像存进程的pid一样，用同样的原理可以加速此系统调用。

Print a page table

主要思路

根据Hints来写，首先要输出所有页表项我们需要对三层页表进行遍历，页表是树状结构，遍历的历程参考Hints给出的freewalk()函数。

  • 在kernel/defs.h中定义vmprint函数：
    1
    void            vmprint(pagetable_t);
  • 在kernel/exec.c中添加题目要求的代码：
    1
    2
    3
    4
    ...
    if(p->pid==1) vmprint(p->pagetable);
    return argc; // this ends up in a0, the first argument to main(argc, argv)
    ...
  • 接着在kernel/vm.c中实现vmprint函数(仿照freewalk函数)：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    static uint64 depth = 0; // 来记录递归搜索深度
    void
    vmprint(pagetable_t page)
    {
      if(depth == 0)           // 根地址打印
      {
        printf("page table %p\n", page);
      }
      for(int i = 0; i < 512; ++i)  // 遍历页面上的页表项
      {
        pte_t pte = page[i];   
        if(pte & PTE_V)        // 页表项有效
        {
          for(int j = 0; j <= depth; ++j)
          { 
            printf(" ..");
          }
          printf("%d: pte %p pa %p\n", i, (uint64)pte, (uint64)PTE2PA(pte));  // 分别打印虚拟地址和物理地址

          if(depth < 2) // 一级或二级页表递归搜索子页表项
          {
            depth ++;
            vmprint((pagetable_t)PTE2PA(pte));
            depth --;
          }
        } 
      }
    }

Q: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?

Figure 3.4如下：

Figure 3.4

对于三层页表的存储内容，我们需要对exec函数进行分析，因为页表在这里被创建。
首先我们可以看到exec函数中与内存操作相关的第一处是如下代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// Load program into memory.
for(i=0, off=elf.phoff; i<elf.phnum; i++, off+=sizeof(ph)){
  if(readi(ip, 0, (uint64)&ph, off, sizeof(ph)) != sizeof(ph))
    goto bad;
  if(ph.type != ELF_PROG_LOAD)
    continue;
  if(ph.memsz < ph.filesz)
    goto bad;
  if(ph.vaddr + ph.memsz < ph.vaddr)
    goto bad;
  if(ph.vaddr % PGSIZE != 0)
    goto bad;
  uint64 sz1;
  if((sz1 = uvmalloc(pagetable, sz, ph.vaddr + ph.memsz, flags2perm(ph.flags))) == 0)
    goto bad;
  sz = sz1;
  if(loadseg(pagetable, ph.vaddr, ip, ph.off, ph.filesz) < 0)
    goto bad;
}

由此page 0所存储的应该是这些数据，如代码段，数据段等.

接着涉及内存操作的代码如下：

1
2
3
4
5
6
7
8
9
10
11
// Allocate two pages at the next page boundary.
// Make the first inaccessible as a stack guard.
// Use the second as the user stack.
sz = PGROUNDUP(sz);
uint64 sz1;
if((sz1 = uvmalloc(pagetable, sz, sz + 2*PGSIZE, PTE_W)) == 0)
  goto bad;
sz = sz1;
uvmclear(pagetable, sz-2*PGSIZE);
sp = sz;
stackbase = sp - PGSIZE;

这段代码申请了两页的空间，其中第一页page 1作为Figure 3.4中guard page段,第二页作为Figure 3.4中stack段。

由函数uvmclear的定义，page 1的PTE_U位被置为0,因此用户程序无法访问page 1。

由Figure 3.4，第三页到最后一页包括了heap,unused,trapframe,trampoline.

Detect which pages have been accessed

主要思路

本题要求我们对给定的有限个数的页面，程序可以检查这些页面是否被访问过，并且将结果编成bitmask输出到用户空间的指定地址。

首先需要确定怎么去查询一个页面是否被访问：参考RISC-V privileged instructions中的Figure 4.18：

Figure 4.18

以及page 81的如下描述：

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.The D bit indicates
the virtual page has been written since the last time the D bit was cleared.

我们知道可以用PTE_A作为页面是否被访问的标志，它的值是PTE的第六位(从零开始)，因此我们在kernel/riscv.h中添加如下代码：

1
#define PTE_A (1L << 6)

若PTE & PTE_A == 1,则说明此页面在检查前被访问过。

如何去得到一页中的PTE呢？根据Hints,我们可以用walk函数，它可以找到一个虚拟地址对应的PTE，返回其physical address。

再根据Hints的第8条，我们需要在检查完毕后将PTE_A位置零，因为检查本身相当于一次访问，若不置零则PTE_A位必然是1，下一次进行检查时就可能出现页面并未被访问但是PTE_A位为1的情况。这要求我们在检查完一个页面后就将PTE的第六位置零，参考如何将一个二进制值的指定位设置为指定的值,将二进制数x的第n位设置为a的公式为x = ((x&(1 << n)) ^ x) ^ (a << n)。

在遍历的过程中如何设置bitmask呢？我采用如下代码：

1
2
3
4
if(PTE_FLAGS(*pte) & PTE_A)  // 访问位为1，代表被访问过
{
  maskbits |= (1L << i);
}

这样maskbits的第i位为1则表示第i页被访问过。

综合以上分析以及Hints中所给的其他的提示，最终补全sys_pgaccess代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
int
sys_pgaccess(void)
{
  // lab pgtbl: your code here.
  uint64 base;        // 待检查页面起始地址
  int pagenum;        // 待检查页面数
  uint64 usraddr;     // 等待输出结果的用户空间地址

  // 获取参数
  argaddr(0, &base);
  argint(1, &pagenum);
  argaddr(2, &usraddr);

  // bitmask
  uint64 maskbits = 0;
  struct proc* p = myproc();

  for(int i = 0; i < pagenum; ++i)
  {
    pte_t* pte = walk(p->pagetable, base + i * PGSIZE, 0);  // 获取第i页的第0个页表项映射的物理地址
    if(pte == 0)  panic("page not exist!");
    if(PTE_FLAGS(*pte) & PTE_A)  // 访问位为1，代表被访问过
    {
      maskbits |= (1L << i);
    }
    *pte = ((*pte & PTE_A) ^ *pte) ^ 0;  // 将PTE_A置零
  }
  
  if (copyout(p->pagetable, usraddr, (char *)&maskbits, sizeof(maskbits)) < 0) // 将bitmask的结果输出到用户空间
    panic("sys_pgacess copyout error");
  
  return 0;
}

Lab3参考链接

≡