页表

1.实验目标

  了解xv6内核当中页表的实现原理，修改页表，使内核更方便地进行用户虚拟地址的翻译。

2.实验过程记录

(1).增加打印页表函数

操作内容: 在VS Code中修改代码，增加打印页表函数
  首先打开kernel/defs.h文件，找到// vm.c部分增加一个函数声明：

// vm.c
void            kvminit(void);
void            kvminithart(void);
uint64          kvmpa(uint64);
void            kvmmap(uint64, uint64, uint64, int);
int             mappages(pagetable_t, uint64, uint64, uint64, int);
pagetable_t     uvmcreate(void);
void            uvminit(pagetable_t, uchar *, uint);
uint64          uvmalloc(pagetable_t, uint64, uint64);
uint64          uvmdealloc(pagetable_t, uint64, uint64);
// + vmprint declaration
void            vmprint(pagetable_t);

  在增加了函数声明之后，在exec.c文件中对exec函数也增加一个对应打印页表信息的操作（这里忽略了增加代码前后的部分信息）：

int exec(char *path, char **argv) {
  …
  // + Use vmprint to print page info
  if (p->pid == 1) {
    vmprint(p->pagetable);
  }
  return argc;  // this ends up in a0, the first argument to main(argc, argv)

bad:
  …
}

  之后，就要具体实现vmprint函数了，在这里采取如同实验指导中一样的vmprint与一个对应的print_pgtbl递归函数的实现方式，因此需要在vm.c文件的最后加上这样一系列代码：

// + print_pgtbl definition
void print_pgtbl(pagetable_t pgtbl, int depth, long virt) {
  virt <<= 9; // + 拿到上一层的虚拟地址，需要先左移9位，方便加上下一级页表号
  for (int i = 0; i < 512; i++) {
    pte_t pte = pgtbl[i]; // 获取每一条pte
    if (pte & PTE_V) { // 如果pte有效
      uint64 pa = PTE2PA(pte); // 求出pa
      char prefix[16] = "||";
      int str_end = 2;
      for (int j = depth; j > 0; j--) {
        prefix[str_end] = ' ';
        prefix[str_end + 1] = '|';
        prefix[str_end + 2] = '|';
        str_end += 3;
      }
      printf(prefix);
      if (depth == 2) {
        // + 虚拟地址加上最后一级页表号，之后再左挪12位
        printf("idx: %d: va: %p -> pa: %p, flags: ", i, 
((virt + i) << 12), pa);
      }
      else {
        printf("idx: %d: pa: %p, flags: ", i, pa);
      }
      
      // + 增加BIT_MACRO和symbol数组用于打印flags
      long BIT_MACRO[4] = {PTE_R, PTE_W, PTE_X, PTE_U};
      char symbol[][4] = {"r", "w", "x", "u"};
      for (int i = 0; i < 4; i++) {
        if ((pte & BIT_MACRO[i]) != 0) {
          printf("%s", symbol[i]);
        }
        else {
          printf("-");
        }
      }
      printf("\n");
      if ((pte & (PTE_R | PTE_W | PTE_X)) == 0) {
        print_pgtbl((pagetable_t)pa, depth + 1, virt + i);
      }
    }
  }
}

// + vmprint definition
void vmprint(pagetable_t pgtbl) {
  printf("page table %p\n", pgtbl);
  // 递归打印pte和pa
  print_pgtbl(pgtbl, 0, 0L);
}

  在实验手册中给出的vmprint与print_pgtbl两个函数实例实际上还有一些区别，因为要求最终输出的内容中包含转换前的虚拟地址，因此需要增加一个计算虚拟地址的内容，并且由于实验还需要增加对于页面的访问属性的检测，因此还需要增加一个flags部分用于输出，在这里我采用了一个一个long数组加一个字符串数组的实现方式，对于每一个有效的页面都会通过直接for循环检测对应的属性是否满足，之后输出对应的字符，从而就实现了合法的页表打印。
  在完成了代码编写之后首先直接使用make qemu编译运行xv6内核，可以发现启动的时候已经打印出了对应的内容

  之后使用grade-lab-pgtbl脚本进行测试，可以发现，第一个打印页表项的实验已经顺利通过了：

(2).独立内核页表

操作内容: 修改代码，使用全局页表，为每个进程分配独立页表
  首先打开kernel/proc.h，找到struct proc的定义，增加两个字段：

// Per-process state
struct proc {
  struct spinlock lock;

  // p->lock must be held when using these:
  enum procstate state;        // Process state
  struct proc *parent;         // Parent process
  void *chan;                  // If non-zero, sleeping on chan
  int killed;                  // If non-zero, have been killed
  int xstate;                  // Exit status to be returned to parent's wait
  int pid;                     // Process ID

  // these are private to the process, so p->lock need not be held.
  uint64 kstack;               // Virtual address of kernel stack
  uint64 sz;                   // Size of process memory (bytes)
  pagetable_t pagetable;       // User page table
  struct trapframe *trapframe; // data page for trampoline.S
  struct context context;      // swtch() here to run process
  struct file *ofile[NOFILE];  // Open files
  struct inode *cwd;           // Current directory
  char name[16];               // Process name (debugging)
  // + k_pagetable, kstack_pa
  pagetable_t k_pagetable;
  uint64 kstack_pa;
};

  为了实现独立内核页表，在defs.h当中首先添加两个独立内核页表相关的函数声明：

// + kvminit_for_each_process, kvmmap_for_each_process declaration
pagetable_t     kvminit_for_each_process(void);
void            kvmmap_for_each_process(pagetable_t, uint64, uint64, uint64, int);

  在添加完函数声明之后，就可以在vm.c的合适位置加上函数的定义了，kvminit_for_each_process和kvmmap_for_each_process两个函数要仿照kvminit和kvmmap两个函数来实现：

// + kvminit_for_each_process definition
pagetable_t kvminit_for_each_process() {
  pagetable_t k_pagetable = (pagetable_t)kalloc();
  memset(k_pagetable, 0, PGSIZE);
  // uart registers
  kvmmap_for_each_process(k_pagetable, UART0, UART0, PGSIZE, PTE_R | PTE_W);
  // virtio mmio disk interface
  kvmmap_for_each_process(k_pagetable, VIRTIO0, VIRTIO0, PGSIZE, PTE_R | PTE_W);
  // 不映射CLINT
  // PLIC
  kvmmap_for_each_process(k_pagetable, PLIC, PLIC, 0x400000, PTE_R | PTE_W);
  // map kernel text executable and read-only.
  kvmmap_for_each_process(k_pagetable, KERNBASE, KERNBASE, (uint64)etext - KERNBASE, PTE_R | PTE_X);
  // map kernel data and the physical RAM we'll make use of.
  kvmmap_for_each_process(k_pagetable, (uint64)etext, (uint64)etext, PHYSTOP - (uint64)etext, PTE_R | PTE_W);
  // map the trampoline for trap entry/exit to
  // the highest virtual address in the kernel.
  kvmmap_for_each_process(k_pagetable, TRAMPOLINE, (uint64)trampoline, PGSIZE, PTE_R | PTE_X);
  return k_pagetable;
}

// + kvmmap_for_each_process definition
void kvmmap_for_each_process(pagetable_t k_pagetable, uint64 va, uint64 pa, uint64 sz, int perm) {
  if (mappages(k_pagetable, va, sz, pa, perm) != 0) {
    panic("kvmmap");
  }
}

  之后需要修改proc.c中定义的procinit函数，将内核栈的物理地址pa拷贝到PCB的新成员kstack_pa当中：

// initialize the proc table at boot time.
void procinit(void) {
  struct proc *p;
 
  initlock(&pid_lock, "nextpid");
  for (p = proc; p < &proc[NPROC]; p++) {
    initlock(&p->lock, "proc");
 
    // Allocate a page for the process's kernel stack.
    // Map it high in memory, followed by an invalid
    // guard page.
    char *pa = kalloc();
    if (pa == 0) panic("kalloc");
    uint64 va = KSTACK((int)(p - proc));
    kvmmap(va, (uint64)pa, PGSIZE, PTE_R | PTE_W);
    p->kstack = va;
    // + 将内核栈的物理地址pa拷贝到kstack_pa当中
    p->kstack_pa = (uint64)pa; 
  }
  kvminithart();
}

  之后同时也需要更改allocproc函数从而完成页表k_pagetable的映射，在这里忽略了allocproc函数的其他部分代码，代码中主要添加了两个部分，首先是创建内核页表，如果创建失败则释放对应的进程块，之后再将内核栈通过kvmmap_for_each_process函数映射到页表k_pagetable当中：

static struct proc *allocproc(void) {
  …
found:
  p->pid = allocpid();

  // Allocate a trapframe page.
  if ((p->trapframe = (struct trapframe *)kalloc()) == 0) {
    release(&p->lock);
    return 0;
  }
  
  // + 为每一个找到的空闲进程创建内核页表
  p->k_pagetable = kvminit_for_each_process();
  if (p->k_pagetable == 0) {
    freeproc(p);
    release(&p->lock);
    return 0;
  }

  // + 将创建的内核栈映射到页表k_pagetable中
  kvmmap_for_each_process(p->k_pagetable, p->kstack, p->kstack_pa, PGSIZE, PTE_R | PTE_W);

  // An empty user page table.
  …
}

  之后需要修改调度器，首先给vm.c增加将内核页表放入satp寄存器的函数，首先依旧是在defs.h中增加函数声明：

// + kvminithart_for_each_process declaration
void            kvminithart_for_each_process(pagetable_t);

  之后是增加函数定义（写法只需仿照kvminithart完成即可）：

// + kvminithart_for_each_process definition
void kvminithart_for_each_process(pagetable_t k_pagetable) {
  w_satp(MAKE_SATP(k_pagetable));
  sfence_vma();
}

  之后修改scheduler完成内核页表的切换操作（这里同样忽略了部分没有变化的代码）：

void scheduler(void) {
…
        c->proc = p;
        // + 在上下文切换前切换到当前进程的页表，放入satp中：
        kvminithart_for_each_process(p->k_pagetable);

        swtch(&c->context, &p->context);

        // Process is done running for now.
        // It should have changed its p->state before coming back.
        c->proc = 0;

        // + 如果目前没有进程运行，则让satp载入全局内核页表
        kvminithart();

        found = 1;
      }
…
}

  在defs.h中增加free_pagetable_except_for_leaf的函数声明：

// + free_pagetable_except_for_leaf declaration
void            free_pagetable_except_for_leaf(pagetable_t);

  再仿照freewalk在vm.c当中实现一个释放所有非叶子页表的函数：

// + free_pagetable_except_for_leaf definition
void free_pagetable_except_for_leaf(pagetable_t pagetable) {
  for (int i = 0; i < 512; i++) {
    pte_t pte = pagetable[i]; // 获取当前页表pte
    // pte有效且为根/次页表的目录项
    if ((pte & PTE_V) && (pte & (PTE_R|PTE_W|PTE_X)) == 0) {
      uint64 pa = PTE2PA(pte);
      free_pagetable_except_for_leaf((pagetable_t)pa);
      pagetable[i] = 0;
    }
    pagetable[i] = 0;
    // 对于叶子页表不能释放物理页，直接置零即可
  }
  // 释放物理内存
  kfree((void*)pagetable);
}

  然后修改proc.c当中的freeproc函数，使之正常释放独立内核页表：

// + Use free_pagetable_except_for leaf to release k_pagetable
  if (p->k_pagetable) {
    free_pagetable_except_for_leaf(p->k_pagetable);
  }

在修改完上述所有代码之后，在目录下使用make qemu编译，在内核中使用kvmtest进行测试，可以看到：

  再使用grade-lab-pgtbl进行测试，可以发现独立内核页表的测试这一次也顺利通过了：

(3).简化软件模拟地址翻译

操作内容: 修改代码，在独立内核页表上加上用户地址空间映射，避免花费大量时间进行软件模拟便利页表
  首先打开kernel/defs.h，添加首先需要完成的将进程的用户页表映射到内核页表的sync_pagetable函数：

// + sync_pagetable declaration
int  sync_pagetable(pagetable_t, pagetable_t, uint64, uint64);

  之后在vm.c中实现这个函数：

// + sync_pagetable definition
int sync_pagetable(pagetable_t old, pagetable_t new, uint64 sz, uint64 sz_n) {
  pte_t* pte;
  uint64 pa, i;
  uint flags;
  sz = PGROUNDUP(sz);
  for (i = sz; i < sz_n; i += PGSIZE) {
    if ((pte = walk(old, i, 0)) == 0) {
      panic("sync_pagetable:pte should exist");
    }
    if ((*pte & PTE_V) == 0) {
        panic("sync_pagetable:page not present");
    }
    pa = PTE2PA(*pte);
    // 允许内存访问
    flags = PTE_FLAGS(*pte) & (~PTE_U); // 对第四位为1的掩码取反
    if (mappages(new, i, PGSIZE, (uint64)pa, flags) != 0) { // 创建页表项
      // 移除映射
      goto err;
    }
  }
  return 0;

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

  之后利用vmcopyin.c当中定义的copyin_new函数直接替代掉copyin()的内容，这里我没有删除代码，只是将之前实现的部分进行了注释：

int copyin(pagetable_t pagetable, char *dst, uint64 srcva, uint64 len) {
//   uint64 n, va0, pa0;

//   while (len > 0) {
//     va0 = PGROUNDDOWN(srcva);
//     pa0 = walkaddr(pagetable, va0);
//     if (pa0 == 0) return -1;
//     n = PGSIZE - (srcva - va0);
//     if (n > len) n = len;
//     memmove(dst, (void *)(pa0 + (srcva - va0)), n);

//     len -= n;
//     dst += n;
//     srcva = va0 + PGSIZE;
//   }
  // + Use copyin_new directly replace copyin definition
  return copyin_new(pagetable, dst, srcva, len); 
}

  在这里我忘了提前把函数声明加上，于是回到vm.c中增加了两个会用到的copyin函数的声明：

// vmcopyin.c
int       copyin_new(pagetable_t, char*, uint64, uint64);
int       copyinstr_new(pagetable_t, char*, uint64, uint64);

  然后进行copyinstr的修改，修改的操作和copyin是一致的：

int copyinstr(pagetable_t pagetable, char *dst, uint64 srcva, uint64 max) {
//   uint64 n, va0, pa0;
//   int got_null = 0;

//   while (got_null == 0 && max > 0) {
//     va0 = PGROUNDDOWN(srcva);
//     pa0 = walkaddr(pagetable, va0);
//     if (pa0 == 0) return -1;
//     n = PGSIZE - (srcva - va0);
//     if (n > max) n = max;

//     char *p = (char *)(pa0 + (srcva - va0));
//     while (n > 0) {
//       if (*p == '\0') {
//         *dst = '\0';
//         got_null = 1;
//         break;
//       } else {
//         *dst = *p;
//       }
//       --n;
//       --max;
//       p++;
//       dst++;
//     }

//     srcva = va0 + PGSIZE;
//   }
//   if (got_null) {
//     return 0;
//   } else {
//     return -1;
//   }
  // + Use copyinstr_new to replace copyinstr
  return copyinstr_new(pagetable, dst, srcva, max);
}

  这里对比一下两个新函数的差距：

// Copy from user to kernel.
// Copy len bytes to dst from virtual address srcva in a given page table.
// Return 0 on success, -1 on error.
int copyin_new(pagetable_t pagetable, char *dst, uint64 srcva, uint64 len) {
  struct proc *p = myproc();

  if (srcva >= p->sz || srcva + len >= p->sz || srcva + len < srcva) return -1;
  memmove((void *)dst, (void *)srcva, len);
  stats.ncopyin++;  // XXX lock
  return 0;
}

int copyin(pagetable_t pagetable, char *dst, uint64 srcva, uint64 len) {
  uint64 n, va0, pa0;

  while (len > 0) {
    va0 = PGROUNDDOWN(srcva);
    pa0 = walkaddr(pagetable, va0);
    if (pa0 == 0) return -1;
    n = PGSIZE - (srcva - va0);
    if (n > len) n = len;
    memmove(dst, (void *)(pa0 + (srcva - va0)), n);

    len -= n;
    dst += n;
    srcva = va0 + PGSIZE;
}
return 0; 
}

  原先的copyin函数是通过walkaddr软件模拟转换页表实现的，它的实现需要很长一段时间的遍历，而copyin_new直接通过硬件方式完成了内存的拷贝，此时就无需进行遍历实现，效率明显提高，而copyinstr和copyinstr_new的区别也是类似的：

// Copy a null-terminated string from user to kernel.
// Copy bytes to dst from virtual address srcva in a given page table,
// until a '\0', or max.
// Return 0 on success, -1 on error.
int copyinstr_new(pagetable_t pagetable, char *dst, uint64 srcva, uint64 max) {
  struct proc *p = myproc();
  char *s = (char *)srcva;

  stats.ncopyinstr++;  // XXX lock
  for (int i = 0; i < max && srcva + i < p->sz; i++) {
    dst[i] = s[i];
    if (s[i] == '\0') return 0;
  }
  return -1;
}

  这里没有附上copyinstr的代码，它的实现基本也是一致的，只是因为字符串类型相对比较特别，所以需要一个拷贝的最大字符，以及对于0字符的特别判断等操作，但是除此之外的操作基本上是如同copyin一样的，它也直接通过for循环的方式完成了字节的拷贝，而没有使用walkaddr的方式来进行软件模拟，从而提升了效率。
  之后修改proc.c中fork、exec和growproc三个函数的定义，首先对于growproc，增加n < 0时对于独立内核页表的释放操作：

int growproc(int n) {
  uint sz;
  struct proc *p = myproc();

  sz = p->sz;
  if (n > 0) {
    if ((sz = uvmalloc(p->pagetable, sz, sz + n)) == 0) {
      return -1;
    }
    sync_pagetable(p->pagetable, p->k_pagetable, p->sz, p->sz + n);
  } else if (n < 0) {
    sz = uvmdealloc(p->pagetable, sz, sz + n);
    // + 用户删内核也删，如果这里释放物理内存可能导致重复回收
    uvmdealloc_u_in_k(p->k_pagetable, p->sz, p->sz + n);
  }
  p->sz = sz;
  return 0;
}

  之后增加fork函数最后调用sync_pagetable函数：

int fork(void) {
  …
  np->state = RUNNABLE;
  // + fork也会产生子进程
  sync_pagetable(np->pagetable, np->k_pagetable, 0, np->sz);
  release(&np->lock);
  return pid;
}

  然后就是在exec.c当中修改exec函数的代码（没有变更的部分省略）：

int exec(char *path, char **argv) {
  …
  // Commit to the user image.
  oldpagetable = p->pagetable;
  p->pagetable = pagetable;

  // + 释放oldpagetable映射，建立新的pagetable映射
  uvmdealloc_u_in_k(p->k_pagetable, p->sz, 0);
  sync_pagetable(p->pagetable, p->k_pagetable, 0, sz);

  p->sz = sz;
  p->trapframe->epc = elf.entry;  // initial program counter = main
…
}

  然后分别在defs.h和vm.c当中添加先前用到的uvmdealloc_u_in_k函数的声明与定义：

// + uvmdealloc_u_in_k declaration
uint64          uvmdealloc_u_in_k(pagetable_t, uint64, uint64);
// + uvmdealloc_u_in_k definition
uint64 uvmdealloc_u_in_k(pagetable_t pagetable, uint64 oldsz, uint64 newsz) {
  if (newsz >= oldsz) return oldsz;
  if (PGROUNDUP(newsz) < PGROUNDUP(oldsz)) {
    int npages = (PGROUNDUP(oldsz) - PGROUNDUP(newsz)) / PGSIZE;
    uvmunmap(pagetable, PGROUNDUP(newsz), npages, 0); // 释放物理内存会报错
  }
  return newsz;
}

  在proc.c当中为第一个进程创建用的userinit也增加用户页表映射的过程：

void userinit(void) {
  struct proc *p;
  p = allocproc();
  initproc = p;
  // allocate one user page and copy init's instructions
  // and data into it.
  uvminit(p->pagetable, initcode, sizeof(initcode));
  p->sz = PGSIZE;
  // + 用户初始化进程映射到内核页表中
sync_pagetable(p->pagetable, p->k_pagetable, 0, p->sz);
…
}

  最终使用make qemu编译，运行stats，可以看到copyin和copyinstr的次数都不为0了：

  之后在终端中运行grade-lab-pgtbl，可以看到结果为100分，所有测试均能够通过：

3.实验问题及相应解答

问题1

问题: 将自己电脑上输出的三层页表绘制成图
解决: 利用工具将输出的两个三层页表绘制成为下面的图，第一个是对于第一组三个PTE的页表示意图：

  下面是第二组两个PTE的页表示意图：

问题2

问题: 查阅资料，简要阐述页表机制为什么会被发明，它有什么好处？
解决：
页表机制的必要性：

• 正如操作系统理论课上说的，内存管理会随着计算机的广泛应用变得越来越复杂，首先不同进程之间如果直接使用物理内存可能会导致相互之间无法隔离，一个进程可以比较轻松地入侵另外一个进程的地址空间，这是一件很危险的事情；
• 二来是内存线性分配可能会导致很多外部碎片，这样可用的内存可能会随着计算机的运行越变越少。
• 第三是多任务操作的需求，传统的线性内存管理机制无法满足进程之间的内存冲突和数据泄露的问题，因此综上所述，页表机制是必备的。

页表机制的好处：

• 通过页表，操作系统可以灵活地分配和管理内存。页表允许非连续的内存分配，使得操作系统可以更高效地利用内存，减少内存碎片。例如，一个进程可以分配多个不连续的物理内存页，而这些页在虚拟地址空间中表现为连续的。
• 页表机制是虚拟内存的重要组成部分。虚拟内存允许操作系统使用磁盘空间来扩展物理内存的容量。页表记录了哪些虚拟地址映射到物理内存，哪些映射到磁盘。当程序访问不在物理内存中的页面时，会触发页面置换机制，将所需页面从磁盘调入内存。这种机制大大扩展了程序可以使用的内存容量，使得运行大型程序成为可能。
• 页表可以包含每个页面的权限标志，如只读、可写和可执行。这使得操作系统可以精细地控制每个页面的访问权限，防止程序执行未授权的操作。例如，代码段通常被标记为只读和可执行，数据段被标记为可读写但不可执行。这种细粒度的权限控制增强了系统的安全性。

问题3

问题: xv6本会在 procinit()中分配内核栈的物理页并在页表建立映射。但是现在，应该在allocproc()中实现该功能。这是为什么？
解决: procinit函数的作用是在操作系统启动的初始化阶段对整个PCB表进行初始化，这个时段会完成所有PCB的基本资源的申请，如果在这个阶段就分配内核栈的物理页并在页表建立映射就可能会在很多PCB没有使用的情况下造成大量资源浪费。
  而allocproc函数会在每一个PCB真正创建的时候再去分配相应的资源，所以将分配物理页建立映射的操作放在allocproc，也就是创建进程真实需要用到资源的时候再完成操作。

问题4

问题: 为什么像kminithart_for_each_process这种函数，我们需要重写，实现的逻辑与原本的函数却是一样的，那重写的意义在哪里，或者如果不重写，能不能直接使用原本的函数。（为什么不能直接用原来的函数）
解决: xv6 中，kvminithart 函数用于初始化和设置全局内核页表。这个全局页表用于所有进程的内核态切换。然而，当引入独立内核页表的机制时，每个进程都有自己的内核页表，而不是共享一个全局内核页表。因此，kvminithart 函数需要进行相应的修改以支持独立内核页表。
  如果直接修改 kvminithart 函数来支持独立内核页表，意味着所有调用 kvminithart 的地方都需要进行相应的修改和调整。这会导致代码的改动范围非常大，增加了引入新错误的风险，并且会对现有功能的稳定性造成影响。
  所以重写一个新的函数实际上反而要比进行修改会更加简单，在已经存在大量使用到某个函数的逻辑的情况下，写一个新的实现不同的功能相比于队原来的函数逻辑修改的开发效率会明显更高。

实验小结

• 1、阅读了xv6内核中关于页表等的代码，了解了xv6是如何进行页表地址转换等一系列操作的。
• 2、本次实验完成了对于xv6内核页表结构的打印，给进程添加了独立内核页表，并在之后优化了代码使得地址转换不再通过软件模拟的方式实现，提升了效率。