[MIT 6.1810]Lab3 page tables

1 Inspect a user-process page table (easy)

PTE 逻辑内容 权限位
va 0x0 pte 0x21FC885B pa 0x87F22000 perm 0x5B text AUXRV
va 0x1000 pte 0x21FC7C17 pa 0x87F1F000 perm 0x17 data UWRV
va 0x2000 pte 0x21FC7807 pa 0x87F1E000 perm 0x7 guard page WRV
va 0x3000 pte 0x21FC74D7 pa 0x87F1D000 perm 0xD7 stack DAUWRV
va 0x4000 pte 0x0 pa 0x0 perm 0x0 unused
va 0x5000 pte 0x0 pa 0x0 perm 0x0 unused
va 0x6000 pte 0x0 pa 0x0 perm 0x0 unused
va 0x7000 pte 0x0 pa 0x0 perm 0x0 unused
va 0x8000 pte 0x0 pa 0x0 perm 0x0 unused
va 0x9000 pte 0x0 pa 0x0 perm 0x0 unused
va 0xFFFF6000 pte 0x0 pa 0x0 perm 0x0 unused
va 0xFFFF7000 pte 0x0 pa 0x0 perm 0x0 unused
va 0xFFFF8000 pte 0x0 pa 0x0 perm 0x0 unused
va 0xFFFF9000 pte 0x0 pa 0x0 perm 0x0 unused
va 0xFFFFA000 pte 0x0 pa 0x0 perm 0x0 unused
va 0xFFFFB000 pte 0x0 pa 0x0 perm 0x0 unused
va 0xFFFFC000 pte 0x0 pa 0x0 perm 0x0 unused
va 0xFFFFD000 pte 0x0 pa 0x0 perm 0x0 unused
va 0xFFFFE000 pte 0x21FD08C7 pa 0x87F42000 perm 0xC7 trapframe DAWRV
va 0xFFFFF000 pte 0x2000184B pa 0x80006000 perm 0x4B trampoline AXRV

2 Speed up system calls (easy)

Some operating systems (e.g., Linux) speed up certain system calls by sharing data in a read-only region between userspace and the kernel. This eliminates the need for kernel crossings when performing these system calls. To help you learn how to insert mappings into a page table, your first task is to implement this optimization for the getpid() system call in xv6.

When each process is created, map one read-only page at USYSCALL (a virtual address defined in memlayout.h). At the start of this page, store a struct usyscall (also defined in memlayout.h), and initialize it to store the PID of the current process. For this lab, ugetpid() has been provided on the userspace side and will automatically use the USYSCALL mapping. You will receive full credit for this part of the lab if the ugetpid test case passes when running pgtbltest.

这道题目要求我们在创建一个进程的时候，将一个只读的物理页映射到虚拟地址 USYSCALL ，这样可以在内核和用户空间之间共享一些数据（内核将指定的数据暴露给用户，使得可以在用户空间内访问）。通过在用户空间提供相应的接口，可以完成一些简单的系统调用而无需进行用户到内核的切换。

大致的思路如下：

在创建进程的时候申请物理内存，销毁进程的时候释放物理内存，创建页表的时候进行映射，销毁页表的时候取消映射。

  1. 在proc结构体中添加一个 struct usyscall *usyscall 用来存放该页面

    1
    2
    3
    4
    5
    6
    7
    8
    // Per-process state
    struct proc {
      // ...
        
      struct usyscall *usyscall;   // shared data between kernel and user
      
      // ...
    };

  2. 在创建进程的过程中，申请一个物理页，参考trapframe.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    // kernel/proc.c

    // Allocate a usyscall page.
    // 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;
        }
        p->usyscall->pid = p->pid;
        
        // ...
    }

  3. 在创建页表时将该物理页映射到虚拟地址 USYSCALL，权限位设置为 PTE_U | PTE_R.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    // kernel/proc.c

    // 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)
    {
      	// ...

        // map the usyscall page just below the trapframe page 
        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;
        }
        
    	// ...
    }

  4. 释放页表的时候取消映射

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    //kernel/proc.c

    // 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);
    }

  5. 在销毁进程的时候，将该页内存释放

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    // free a proc structure and the data hanging from it,
    // including user pages.
    // p->lock must be held.
    static void
    freeproc(struct proc *p)
    {
    	// ...
        
        if(p->usyscall)
        	kfree((void*)p->usyscall);
        p->usyscall = 0;
       	
        // ...
    }

3 Print a page table (easy)

We added a system call kpgtbl(), which calls vmprint() in vm.c. It takes a pagetable_t argument, and your job is to print that pagetable in the format described below.

这题通过递归实现，参考freewalk。注意虚拟地址va，当遍历3级页表的时候，每遍历一个页表项，va变化512*512*PGSIZE，2级1级以此类推。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void
vmprinthelper(pagetable_t pagetable, int level, uint64 va)
{
  uint64 sz = 0;
  if (level == 2) sz = 512 * 512 * PGSIZE;
  else if (level == 1) sz = 512 * PGSIZE;
  else sz = PGSIZE;
  for(int i = 0; i < 512; i++, va += sz){
    pte_t pte = pagetable[i];
    if ((pte & PTE_V) == 0) continue;
    for (int j = 0; j < 3 - level; ++j) printf(" ..");
    printf("%p: ", (void*)va);
    printf("pte %p pa %p\n", (void*)pte, (void*)PTE2PA(pte));
    if ((pte & (PTE_R|PTE_W|PTE_X)) == 0)
      vmprinthelper((void*)PTE2PA(pte), level - 1, va);
  }
}

void
vmprint(pagetable_t pagetable) {
  // your code here
  printf("page table %p\n", pagetable);
  vmprinthelper(pagetable, 2, 0);
}

4 Use superpages (moderate)/(hard)

Your job is to modify the xv6 kernel to use superpages. In particular, if a user program calls sbrk() with a size of 2 megabytes or more, and the newly created address range includes one or more areas that are two-megabyte-aligned and at least two megabytes in size, the kernel should use a single superpage (instead of hundreds of ordinary pages). You will receive full credit for this part of the lab if the superpg_test test case passes when running pgtbltest.

本题要求实现superpage

  • 修改内存布局，在可供分配的物理内存中预留出一块区域用于superpage

    1
    2
    3
    4
    // memlayout.h
    #define KERNBASE 0x80000000L
    #define SUPERBASE (KERNBASE + 112*1024*1024)
    #define PHYSTOP (KERNBASE + 128*1024*1024)

  • 修改kallo.c中的代码，在初始化 kmem 的时候预留出一定物理空间给superpage

    1
    2
    3
    4
    5
    6
    7
    8
    // kallo.c
    void
    kinit()
    {
      initlock(&kmem.lock, "kmem");
      freerange(end, (void*)SUPERBASE);
      superinit();
    }

  • 增加一个 supermem 链表，用于管理所有空闲的superpage，并进行相应的初始化工作（参考kmem）

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    // kalloc.c
    struct {
      struct spinlock lock;
      struct run *freelist;
    } kmem, supermem;

    void
    superinit()
    {
      initlock(&supermem.lock, "supermem");
      char *p = (char*) SUPERPGROUNDUP(SUPERBASE);
      for (; p + SUPERPGSIZE <= (char*)PHYSTOP; p += SUPERPGSIZE)
        superfree(p);
    }

  • 添加 superalloc 和 superfree 函数，用于分配和释放superpage

    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
    34
    35
    36
    37
    void
    superfree(void *pa)
    {
      struct run *r;

      if(((uint64)pa % SUPERPGSIZE) != 0 || (char*)pa < (char*)SUPERBASE || (uint64)pa >= PHYSTOP)
        panic("superfree");

      // Fill with junk to catch dangling refs.
      memset(pa, 1, SUPERPGSIZE);

      r = (struct run*)pa;

      acquire(&supermem.lock);
      r->next = supermem.freelist;
      supermem.freelist = r;
      release(&supermem.lock);
    }

    // Allocate one 2MB page of physical memory.
    // Returns a pointer that the kernel can use.
    // Returns 0 if the memory cannot be allocated.
    void *
    superalloc(void)
    {
      struct run *r;

      acquire(&supermem.lock);
      r = supermem.freelist;
      if(r)
        supermem.freelist = r->next;
      release(&supermem.lock);

      if(r)
        memset((char*)r, 5, SUPERPGSIZE); // fill with junk
      return (void*)r;
    }

  • 用户在调用 sbrk 系统调用的时候，实际会去调用 uvmalloc 函数，因此，我们需要修改 uvmalloc 函数，根据参数进行不同的分配策略。具体的，我们先分配普通的page，直到虚拟地址对齐到了2MB的位置上，然后我们尽可能多的分配superpage，最后有可能还会剩下一些需要分配的内存，但是不足一个superpage，或者我们已经没有superpage可供分配了，我们继续分配普通的page，直到满足用户需求。

    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
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    // Allocate PTEs and physical memory to grow process from oldsz to
    // newsz, which need not be page aligned.  Returns new size or 0 on error.
    uint64
    uvmalloc(pagetable_t pagetable, uint64 oldsz, uint64 newsz, int xperm)
    {
      char *mem;
      uint64 a;
      int sz;

      if(newsz < oldsz)
        return oldsz;
      // page ... page superpage ... superpage page ... page
      oldsz = PGROUNDUP(oldsz);
      
      // 分配page直到对齐
      for(a = oldsz; a < SUPERPGROUNDUP(oldsz) && a < newsz; a += sz){
        sz = PGSIZE;
        mem = kalloc();
        if(mem == 0){
          uvmdealloc(pagetable, a, oldsz);
          return 0;
        }
    #ifndef LAB_SYSCALL
        memset(mem, 0, sz);
    #endif
        if(mappages(pagetable, a, sz, (uint64)mem, PTE_R|PTE_U|xperm) != 0){
          kfree(mem);
          uvmdealloc(pagetable, a, oldsz);
          return 0;
        }
      }
    	
      // 尽可能多的分配superpage
      for (; a + SUPERPGSIZE < newsz; a += sz)
      {
        sz = SUPERPGSIZE;
        mem = superalloc();
        if (mem == 0){
          break;
        }
        memset(mem, 0, sz);
        if (mappages(pagetable, a, sz, (uint64)mem, PTE_R|PTE_U|xperm) != 0){
          superfree(mem);
          uvmdealloc(pagetable, a, oldsz);
          return 0;
        }
      }
      
      // 为剩余内存分配page
      for(; a < newsz; a += sz){
        sz = PGSIZE;
        mem = kalloc();
        if(mem == 0){
          uvmdealloc(pagetable, a, oldsz);
          return 0;
        }
        memset(mem, 0, sz);
        if(mappages(pagetable, a, sz, (uint64)mem, PTE_R|PTE_U|xperm) != 0){
          kfree(mem);
          uvmdealloc(pagetable, a, oldsz);
          return 0;
        }
      }
      return newsz;
    }

  • 在 uvmalloc 中申请到内存之后，我们需要在页表中添加对应的页表项。superpage只需要在一级页表中设置即可，因为一个一级页表对应512个页，即2MB。因此，我们需要修改 mappages 函数，来进行相应的映射。我们根据pa的值来区分当前映射的是page还是superpage，并且我们需要相应的 superwalk 来获取superpage 对应的页表项，walk 获得的页表项是0级页表中的，superwalk 获得1级页表中的页表项。

    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
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    pte_t *
    superwalk(pagetable_t pagetable, uint64 va, int alloc)
    {
      if(va >= MAXVA)
        panic("superwalk");

      pte_t *pte = &pagetable[PX(2, va)];
      if(*pte & PTE_V) {
        pagetable = (pagetable_t)PTE2PA(*pte);
        return &pagetable[PX(1, va)];
      } else {
        if(!alloc || (pagetable = (pde_t*)kalloc()) == 0)
          return 0;
        memset(pagetable, 0, PGSIZE);
        *pte = PA2PTE(pagetable) | PTE_V;
        return &pagetable[PX(1, va)];
      }
    }
    // Create PTEs for virtual addresses starting at va that refer to
    // physical addresses starting at pa.
    // va and size MUST be page-aligned.
    // Returns 0 on success, -1 if walk() couldn't
    // allocate a needed page-table page.
    int
    mappages(pagetable_t pagetable, uint64 va, uint64 size, uint64 pa, int perm)
    {
      uint64 a, last;
      uint64 pgsize;
      pte_t *pte;
      if (pa >= SUPERBASE) pgsize = SUPERPGSIZE;
      else pgsize = PGSIZE;
      if((va % pgsize) != 0)
        panic("mappages: va not aligned");

      if((size % pgsize) != 0)
        panic("mappages: size not aligned");

      if(size == 0)
        panic("mappages: size");
      
      a = va;
      last = va + size - pgsize;
      for(;;){
        if(pgsize == PGSIZE && (pte = walk(pagetable, a, 1)) == 0)
          return -1;
        if (pgsize == SUPERPGSIZE && (pte = superwalk(pagetable, a, 1)) == 0)
          return -1;
        if(*pte & PTE_V)
          panic("mappages: remap");
        *pte = PA2PTE(pa) | perm | PTE_V;
        if(a == last)
          break;
        a += pgsize;
        pa += pgsize;
      }
      return 0;
    }

  • 分配完了内存，我们也需要处理释放内存。释放内存调用 uvmdealloc ，该函数调用 uvmunmap 函数去进行实际的释放操作。我们同样根据获得的pa来判断当前释放的是page还是superpage。这里获取va对应的页表项可以统一用 walk ，因为 walk 遇到叶子结点的时候会直接返回。

    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
    34
    35
    36
    // Remove npages of mappings starting from va. va must be
    // page-aligned. The mappings must exist.
    // Optionally free the physical memory.
    void
    uvmunmap(pagetable_t pagetable, uint64 va, uint64 npages, int do_free)
    {
      uint64 a;
      pte_t *pte;
      int sz;

      if((va % PGSIZE) != 0)
        panic("uvmunmap: not aligned");

      for(a = va; a < va + npages*PGSIZE; a += sz){
        sz = PGSIZE;
        if((pte = walk(pagetable, a, 0)) == 0)
          panic("uvmunmap: walk");
        if((*pte & PTE_V) == 0) {
          printf("va=%ld pte=%ld\n", a, *pte);
          panic("uvmunmap: not mapped");
        }
        if(PTE_FLAGS(*pte) == PTE_V)
          panic("uvmunmap: not a leaf");
        uint64 pa = PTE2PA(*pte);
        if (pa >= SUPERBASE){
          a += SUPERPGSIZE;
          a -= sz;
        }
        if(do_free){
          uint64 pa = PTE2PA(*pte);
          if (pa >= SUPERBASE) superfree((void*)pa);
          else kfree((void*)pa);
        }
        *pte = 0;
      }
    }

  • 执行 fork 的时候会拷贝内存，调用的是 uvmcopy ，因此我们需要进行相应的修改。其实就是遍历父进程用户空间的内存，根据内存的pa判断该页是page还是superpage，然后进行相应的申请并复制，最后在新进程的页表中添加相应的页表项即可。

    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
    34
    35
    36
    37
    38
    39
    40
    41
    42
    // Given a parent process's page table, copy
    // its memory into a child's page table.
    // Copies both the page table and the
    // physical memory.
    // returns 0 on success, -1 on failure.
    // frees any allocated pages on failure.
    int
    uvmcopy(pagetable_t old, pagetable_t new, uint64 sz)
    {
      pte_t *pte;
      uint64 pa, i;
      uint flags;
      char *mem;
      int szinc;
      for(i = 0; i < sz; i += szinc){
        szinc = PGSIZE;
        if((pte = walk(old, i, 0)) == 0)
          panic("uvmcopy: pte should exist");
        if((*pte & PTE_V) == 0)
          panic("uvmcopy: page not present");
        pa = PTE2PA(*pte);
        flags = PTE_FLAGS(*pte);
        if (pa >= SUPERBASE){
          szinc = SUPERPGSIZE;
          if ((mem = superalloc()) == 0)
            goto err;
        }
        else if ((mem = kalloc()) == 0) 
          goto err;
        memmove(mem, (char*)pa, szinc);
        if(mappages(new, i, szinc, (uint64)mem, flags) != 0){
          if (szinc == PGSIZE) kfree(mem);
          else superfree(mem);
          goto err;
        }
      }
      return 0;

     err:
      uvmunmap(new, 0, i / PGSIZE, 1);
      return -1;
    }

    5 测试结果

操作系统
#MIT 6.1810
[MIT 6.1810]Lab3 page tables
https://erlsrnby04.github.io/2024/10/05/MIT-6-1810-Lab3-page-tables/
作者
ErlsrnBy04
发布于
2024年10月5日
许可协议