Page tables

Paging hardware

为什么需要页表

将主存储器以及各种外设接口卡里面内置的存储器连接起来，就形成了内存地址空间。内存地址空间中的地址是真实的物理地址。RISC-V架构的指令使用的地址是虚拟地址。为了通过指令中的虚拟地址访问到真实的物理内存，需要进行从虚拟地址到物理地址的转换。从虚拟地址到物理地址的转换，就需要通过页表来实现。

页表如何运作

在RISC-V指令集中，当我们需要开启页表服务时，我们需要将我们预先配置好的页表首地址放入 satp 寄存器中。从此之后， 计算机硬件 将把访存的地址 均视为虚拟地址 ，都需要通过硬件查询页表，将其 翻译成为物理地址 ，然后将其作为地址发送给内存进行访存。

xv6采用的指令集标准为RISC-V标准，其中页表的标准为SV39标准，也就是虚拟地址最多为39位。

虚实地址翻译流程：

  1. 获得一个虚拟地址。根页表基地址已经被装填至寄存器 satp 中。
  2. 通过 satp 找到根页表的物理页帧号，转成物理地址（Offset为0），通过虚拟地址的L2索引，找到对应的页表项。
  3. 通过页表项可以找到找到 次页表 的物理页帧号，转成物理地址（Offset为0），通过虚拟地址的L1索引，找到对应的页表项。
  4. 通过页表项可以找到找到 叶子页表 的物理页帧号，转成物理地址（Offset为0），通过虚拟地址的L0索引，找到对应的页表项。
  5. 通过页表项可以找到找到 物理地址 的物理页帧号，通过虚拟地址的Offset，转成物理地址（Offset和虚拟地址Offset相同）。

页表组成

页表项

页表由页表项PTE（Page Table Entries）构成，每个页表项由44位的PPN（Physical Page Number）和一些参数flag组成。

image-20230109153937459

Each PTE contains flflag bits that tell the paging hardware how the associated virtual address is allowed to be used. PTE_V indicates whether the PTE is present: if it is not set, a reference to the page causes an exception (i.e. is not allowed). PTE_R controls whether instructions are allowed to read to the page. PTE_W controls whether instructions are allowed to write to the page. PTE_X controls whether the CPU may interpret the content of the page as instructions and execute them. PTE_U controls whether instructions in user mode are allowed to access the page; if PTE_U is not set, the PTE can be used only in supervisor mode.

这个表项的几个参数定义在kernel/riscv.h中的341行左右。

虚拟地址有64bit，其中25bits未使用，39bits包含了27位的PTE索引号以及12位的offset。

物理地址有56位，由PPN和offset拼接组成。

单页表和多级页表

以单页表为例，物理地址形成过程如下图所示。

image

每个页表项PTE索引着一页。因而，每一页的大小为2^12=4096B。单页表中PTE的索引号有2^27个，因而单页表中表项有134217728个，即可以代表134217728页。页表实际上也是以页的形式存储的。因而单页表需要的存储空间为(2^27x7)/2^12=2^15x7=229376页。

RISC-V架构中真实情况是会有三级页表。三级页表结构相比于单级页表结构，会占据更多的物理存储空间。

image-20230109151346780

每个页表项PTE索引着一页，这一页可能代表着另一个页表，也可能代表着内存中需要的指令和数据。因而，每一页的大小为2^12=4096B。三页表中，一级页表中PTE的索引号有512个，可以代表的物理内存页数有512x515x512=2^27页，即可以代表134217728页。页表实际上也是以页的形式存储的，一个页表有2^9x7个字节，可以存储在1页中。因而三页表需要的存储空间为1+2^9+2^18 = 262657页。

三级页表结构相比于单级页表结构，可以节省更多内存空间。

参考：页表是啥以及为啥多级页表能够节省空间

考虑到这样一个进程：

watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Z1eXVhbmRl,size_16,color_FFFFFF,t_70

进程使用页表时，需要将整个页表读入内存。

如果使用单级页表，尽管一个进程仅使用到页表中的某两项，也需要把整个页表都读入内存，光是页表就占据了2^15x7x4k/2^20 约为1G的内存空间。

如果使用三级页表，一个进程需要用到某两页。假设这两页存储在不同的二级页表中，则只需要读入1+2+2=5页 约为20K的内存空间。

两者相对比，显然用三级页表比单级页表顶多了。三级页表相较于一级页表，多用了13%的物理空间，却可以节省99.998%的空间。

页表使用

每个进程会保留自己的一份用户级别的页表地址。当轮到自己使用CPU时，会将CPU的satp寄存器更换为自己的页表地址。

Kernel address space

介绍了xv6中内核的页表结构。

这里为了方便，就把三级页表省略了，只留下va和pa的对比

每个进程都有一个用户级别的页表。xv6给内核提供了一个单独的内核地址空间的页表。其层级映射关系如下：

p3

在kernel/memlayout.h中正记录了这些参数：

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
// Physical memory layout

// qemu -machine virt is set up like this,
// based on qemu's hw/riscv/virt.c:
//
// 00001000 -- boot ROM, provided by qemu
// 02000000 -- CLINT
// 0C000000 -- PLIC
// 10000000 -- uart0 
// 10001000 -- virtio disk 
// 80000000 -- boot ROM jumps here in machine mode
//             -kernel loads the kernel here
// unused RAM after 80000000.

// the kernel uses physical memory thus:
// 80000000 -- entry.S, then kernel text and data
// end -- start of kernel page allocation area
// PHYSTOP -- end RAM used by the kernel

// qemu puts UART registers here in physical memory.
#define UART0 0x10000000L
#define UART0_IRQ 10

// virtio mmio interface
#define VIRTIO0 0x10001000
#define VIRTIO0_IRQ 1

// core local interruptor (CLINT), which contains the timer.
// ...

由图可知，一直从0x0到0x86400000，都是采取的直接映射的方式，虚拟地址=物理地址，这段是内核使用的空间。在0x0-0x800000000阶段，物理地址代表着各种IO设备的存储器。

但是注意，在0x86400000（PHYSTOP）以上的地址都不是直接映射，这些非直接映射的层级包含两类：

  1. trampoline

    It is mapped at the top of the virtual address space; user page tables have this same mapping.

    它有一点很特殊的是，它实际对应的物理内存是0x80000000开始的一段。也就是说，0x80000000开始的这段内存，既被直接映射了，也被trampoline通过虚拟地址映射了。它被映射了两次。

  2. 内核栈

    Each process has its own kernel stack, which is mapped high so that below it xv6 can leave an unmapped guard page. The guard page’s PTE is invalid (i.e., PTE_V is not set), so that if the kernel overflflows a kernel stack, it will likely cause an exception and the kernel will panic.

    guard page可以用来防止内核栈溢出。

内核使用PTE_R和PTE_X权限映射trampoline和kernel text。这表明这份内存段可以读，可以被当做指令块执行，但不能写。其他的块都是可读可写的，除了guard page被设置为不可访问。

Code: creating an address space

vm.c

操作地址空间和页表部分的代码都在kernel/vm.c中。代表页表的数据结构是pagetable_t。

vm.c的主要函数有walk、mappages等。walk用来在三级页表中找到某个虚拟地址表项，或者创建一个新的表项。mappages用来新建一个表项，主要用到了walk函数。

vm.c中，以kvm开头的代表操纵内核页表，以uvm开头的代表操纵进程里的用户页表。

以初始化为例介绍各个函数

创建页表

一开始操作系统初始化时，会调用vm.c中的kvminit来创建内核页表。主要就是在以内核地址空间的页表结构在填写页表。

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
void
kvminit(void)
{
  kernel_pagetable = kvmmake();
}
// Make a direct-map page table for the kernel.
pagetable_t
kvmmake(void)
{
  //内核页表
  pagetable_t kpgtbl;
  //申请新的一页
  kpgtbl = (pagetable_t) kalloc();
  memset(kpgtbl, 0, PGSIZE);

  //给内核页表初始化表项，结构详见上面的内核地址空间部分
  // uart registers
  kvmmap(kpgtbl, UART0, UART0, PGSIZE, PTE_R | PTE_W);

  // virtio mmio disk interface
  kvmmap(kpgtbl, VIRTIO0, VIRTIO0, PGSIZE, PTE_R | PTE_W);

  // PLIC
  kvmmap(kpgtbl, PLIC, PLIC, 0x400000, PTE_R | PTE_W);

  // map kernel text executable and read-only.
  kvmmap(kpgtbl, KERNBASE, KERNBASE, (uint64)etext-KERNBASE, PTE_R | PTE_X);

  // map kernel data and the physical RAM we'll make use of.
  kvmmap(kpgtbl, (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(kpgtbl, TRAMPOLINE, (uint64)trampoline, PGSIZE, PTE_R | PTE_X);

  // allocate and map a kernel stack for each process.
  proc_mapstacks(kpgtbl);
  
  return kpgtbl;
}

其中，kvmmap用来在内核页表中添加一个新的表项。其函数形式为

1
2
3
4
5
6
7
8
9
// add a mapping to the kernel page table.
// only used when booting.
// does not flush TLB or enable paging.
void
kvmmap(pagetable_t kpgtbl, uint64 va, uint64 pa, uint64 sz, int perm)
{
  if(mappages(kpgtbl, va, sz, pa, perm) != 0)
    panic("kvmmap");
}

实现主要逻辑的是mappages函数

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
// Create PTEs for virtual addresses starting at va that refer to
// physical addresses starting at pa. va and size might not
// 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;
  pte_t *pte;

  if(size == 0)
    panic("mappages: size");
  
  a = PGROUNDDOWN(va);
  last = PGROUNDDOWN(va + size - 1);
  for(;;){
    //walk函数通过虚拟地址新建一个第三级页表的表项并返回其指针，之后只需要填这个表项即可
    if((pte = walk(pagetable, a, 1)) == 0)
      return -1;
    //如果pte存在并且标记为已使用，说明该虚拟地址映射已经存在
    if(*pte & PTE_V)
      panic("mappages: remap");
    //填写表项：物理地址 flags
    *pte = PA2PTE(pa) | perm | PTE_V;
    if(a == last)
      break;
    //每两个表项间隔PGSIZE个字节
    a += PGSIZE;
    pa += PGSIZE;
  }
  return 0;
}

通过虚拟地址获取表项主要是通过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
37
// Return the address of the PTE in page table pagetable
// that corresponds to virtual address va.  If alloc!=0,
// create any required page-table pages.
//
// The risc-v Sv39 scheme has three levels of page-table
// pages. A page-table page contains 512 64-bit PTEs.
// A 64-bit virtual address is split into five fields:
//   39..63 -- must be zero.
//   30..38 -- 9 bits of level-2 index.
//   21..29 -- 9 bits of level-1 index.
//   12..20 -- 9 bits of level-0 index.
//    0..11 -- 12 bits of byte offset within the page.
// 虚拟地址的格式：UNUSED 页表索引 offset，其中页表索引在三级页表中被划分为了三个，分别是
// level0-level2，分别代表了第三级、第二级、第一级页表的索引【具体可见页表组成中的图】
// walk的目的就是要在这三级页表中找到虚拟地址对应的页表项。当alloc!=0时，则要求找不到就新建一个
pte_t *
walk(pagetable_t pagetable, uint64 va, int alloc)
{
  if(va >= MAXVA)
    panic("walk");

  for(int level = 2; level > 0; level--) {
    pte_t *pte = &pagetable[PX(level, va)];
    if(*pte & PTE_V) {
      // 取出PTE中表示下一级页表地址的字节
      pagetable = (pagetable_t)PTE2PA(*pte);
    } else {
      // 页表不存在的情况，要么返回0，要么新建一页
      if(!alloc || (pagetable = (pde_t*)kalloc()) == 0)
        return 0;
      memset(pagetable, 0, PGSIZE);
      *pte = PA2PTE(pagetable) | PTE_V;
    }
  }
  // 最终返回第三级页表的对应表项
  return &pagetable[PX(0, va)];
}
装上页表

使用的是kvminithart函数。它将内核页表的root page table的物理地址写入了satp寄存器。从这个函数之后，就开启了内存映射。

1
2
3
4
5
6
7
8
9
10
11
12
13
// Switch h/w page table register to the kernel's page table,
// and enable paging.
void
kvminithart()
{
  // wait for any previous writes to the page table memory to finish.
  sfence_vma();

  w_satp(MAKE_SATP(kernel_pagetable));

  // flush stale entries from the TLB.
  sfence_vma();
}

其中sfence_vma()的用途是强制更新TLB的旧页表，类似于Java volatile的作用。

疑问

附上书里的详细解释：

image-20230109222917346

TLB与页表类似于cache与主存的关系。TLB保存了页表的一部分。

我的错误想法

我怎么感觉怪怪的啊？因为TLB既然是高速缓存，那么读写页表也应该优先从TLB读写【注：应该就是从这里开始错的hhh写应该是直接写入页表】。所以说，会陈旧的应该是主存中的页表，而不是TLB中的页表。但是，书里是说，改完页表必须通知TLB更改。也就是说，读写页表不是从TLB读写的，那该是从哪里？是TLB以外的free memory吗？

不过，要是从多CPU的角度思考，说不定他这个意思是某个CPU的TLB变了，需要通知其他所有CPU的TLB也变。虽然不同CPU当前执行的进程是不一样的，使用的页表项不一样，切换进程的时候也会把用户地址空间的页表项flush掉。但是内核地址空间的页表项一般是不会随着进程切换而flush掉的。所以内核页表修改就需要手动多CPU同步。

我认为多CPU角度考虑更加合理，因为它最后说了，xv6会在内核页表init后flush，以及在从内核态切换回用户态的时候flush。这两个（好像）都影响内核页表比较多，所以就需要手动flush一下。

解答

之后学了缺页异常后，可以发现这里其实是没问题的。

计算机体系结构 – 虚拟内存

v2-e15454bf032baa4dc088b6e41ed4f4a4_1440w

页表的管理（创建、更新、删除等）是由操作系统负责的。地址转换时，页表检索是由硬件内存管理单元（Memory Management Unit, MMU）负责的。MMU通常由两部分构成：表查找单元（Table Walk Unit, TWU）和转换旁路缓冲（Translation Lookaside Buffer, TLB）[2]。TWU负责链式的访问PDE、PTE，完成上述的查表过程。

应用多级页表之后，想要完成一次地址转换，需要访问多级目录和页表，这么多次的内存访问会严重降低性能。

为了优化地址转换速度，人们在MMU中增加了一块高速cache，专门用来缓存虚拟地址到物理地址的映射，这块cache就是TLB[7][8]。MMU在做地址转换的时候，会先检索TLB，如果命中则直接返回对应的物理地址，如果不命中则会调用TWU查找页表。

TLB中缓存的是虚拟地址到物理地址映射。然而，多级页表的查找是一个链式的过程，对于在虚拟地址空间中连续的两个页，它们的各级目录项可能都是一样的，只有最后一级页号不一样。查找完第一个虚拟页之后，我们可以将相同的前级目录项都缓存起来。查找第二个虚拟页时，可以直接使用缓存好的前几级目录项，节省查找时间。这种缓存叫做Page Structure Cache[9]。

而当TLB和MMU中都没有该物理页，就会发生缺页异常。但是操作系统仅会对页表更新，而不会被TLB更新。故而，TBL中数据可能陈旧，需要手动flush。

Physical memory allocation

在内核运行的时候，需要申请很多空间用来存放各种数据。

The kernel must allocate and free physical memory at run-time for page tables, user memory, kernel stacks, and pipe buffers.

用的是这段空闲内存：

image-20230109225700837

It keeps track of which pages are free by threading a linked list through the pages themselves.

kalloc.c中就是这么实现的。

Code: Physical memory allocator

内核运行时申请释放空闲物理空间是通过kernel/kalloc.c完成的。它为内核栈、用户进程、页表和管道buffer服务。

kalloc.c用来在运行时申请分配新的一页，上面的vm.c正是用了kalloc申请一页，要么作为页表，要么作为存储数据的第三级页表指向的物理内存。

最后应该会在空闲内存内形成这样的结构：

内存分成一页一页的，每页内存中的前几个字节存储着其对应队列中下一块内存的物理地址。不一定是从小地址到大地址顺序连接。

It store each free page’s run structure in the free page itself, since there’s nothing else stored there. 

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
// Physical memory allocator, for user processes,
// kernel stacks, page-table pages,
// and pipe buffers. Allocates whole 4096-byte pages.

#include "types.h"
#include "param.h"
#include "memlayout.h"
#include "spinlock.h"
#include "riscv.h"
#include "defs.h"

// 释放在这范围内的物理内存空间
void freerange(void *pa_start, void *pa_end);

// 也就是上面说的free memory的起始位置
extern char end[]; // first address after kernel.
                   // defined by kernel.ld.

// run代表的是一页内存
struct run {
  struct run *next;
};

// 代表了整个内核空闲的物理空间
struct {
  struct spinlock lock;
  struct run *freelist;
} kmem;

void
kinit()
{
  initlock(&kmem.lock, "kmem");
  // init的时候先清空空闲空间，建立空闲页队列
  freerange(end, (void*)PHYSTOP);
}

void
freerange(void *pa_start, void *pa_end)
{
  char *p;
  // PGROUNDUP和PGROUNDDOWN是用于将地址四舍五入到PGSIZE
  p = (char*)PGROUNDUP((uint64)pa_start);
  for(; p + PGSIZE <= (char*)pa_end; p += PGSIZE)
    kfree(p);
}

// Free the page of physical memory pointed at by pa,
// which normally should have been returned by a
// call to kalloc().  (The exception is when
// initializing the allocator; see kinit above.)
void
kfree(void *pa)
{
  struct run *r;

  // pa得是整数页，并且得在内核物理内存范围之间
  if(((uint64)pa % PGSIZE) != 0 || (char*)pa < end || (uint64)pa >= PHYSTOP)
    panic("kfree");

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

  // 之后将在pa对应的那一页的前几个字节写入next字段
  r = (struct run*)pa;

  // 这意思就是在空闲内存的链表队列中新增一块
  acquire(&kmem.lock);
  r->next = kmem.freelist;
  kmem.freelist = r;
  release(&kmem.lock);
}

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

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

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

Process address space

当用户进程叫xv6分配内存时，xv6会用kalloc去取，然后登记在页表上。

The stack is a single page, and is shown with the initial contents as created by exec. Strings containing the command-line arguments, as well as an array of pointers to them, are at the very top of the stack. Just under that are values that allow a program to start at main as if the function main(argc, argv) had just been called.

image-20230109234930690

Code: sbrk

Sbrk is the system call for a process to shrink or grow its memory. The system call is implemented by the function growproc (kernel/proc.c:239).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// Grow or shrink user memory by n bytes.注意单位是bytes，grow n+，shrink n-
// Return 0 on success, -1 on failure.
// 主要逻辑还是通过vm.c实现
int
growproc(int n)
{
  uint64 sz;//size
  struct proc *p = myproc();

  sz = p->sz;
  if(n > 0){
    if((sz = uvmalloc(p->pagetable, sz, sz + n, PTE_W)) == 0) {
      return -1;
    }
  } else if(n < 0){
    sz = uvmdealloc(p->pagetable, sz, sz + n);
  }
  p->sz = sz;
  return 0;
}
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
// 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;

  if(newsz < oldsz)
    return oldsz;

  // oldsz向上取整
  oldsz = PGROUNDUP(oldsz);
  // 每页alloc
  for(a = oldsz; a < newsz; a += PGSIZE){
    mem = kalloc();
    if(mem == 0){
      // 说明失败，恢复到原状
      // 这里不用像下面一样kfree是因为这里压根没有alloc成功
      uvmdealloc(pagetable, a, oldsz);
      return 0;
    }
    // 除去junk data
    memset(mem, 0, PGSIZE);
    // 放入页表
    if(mappages(pagetable, a, PGSIZE, (uint64)mem, PTE_R|PTE_U|xperm) != 0){
      // 不成功
      // dealloc原理是顺着页表一个个free的。由于mem此处没有成功放入页表，所以就得单独free掉
      kfree(mem);
      uvmdealloc(pagetable, a, oldsz);
      return 0;
    }
  }
  return newsz;
}

Code:exec

Exec is the system call that creates the user part of an address space. It initializes the user part of an address space from a fifile stored in the fifile system.

exec是创建地址空间的用户部分的系统调用。它使用一个存储在文件系统中的文件初始化地址空间的用户部分。

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
int
exec(char *path, char **argv)
{
  char *s, *last;
  int i, off;
  uint64 argc, sz = 0, sp, ustack[MAXARG], stackbase;
  struct elfhdr elf;
  struct inode *ip;
  struct proghdr ph;
  pagetable_t pagetable = 0, oldpagetable;
  struct proc *p = myproc();

  //开始打开文件的意思吧（
  begin_op();

  //ip是一个inode
  //打开路径为path的文件
  if((ip = namei(path)) == 0){
    end_op();
    return -1;
  }
  //暂时锁住文件，别人不许动
  ilock(ip);

  //之后应该就是把文件读入内存吧
  // Check ELF header
  if(readi(ip, 0, (uint64)&elf, 0, sizeof(elf)) != sizeof(elf))
    goto bad;

  if(elf.magic != ELF_MAGIC)
    goto bad;

  //分配新页表
  if((pagetable = proc_pagetable(p)) == 0)
    goto bad;

  //elfhd应该指的是可执行文件头
  // 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;
  }
  //在这里解锁
  iunlockput(ip);
  end_op();
  ip = 0;

  p = myproc();
  uint64 oldsz = p->sz;

  //读完文件，开始造一个新的用户栈【fork之后用户栈是不会清空的】
  // 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;
  // mark a PTE invalid for user access.造guard page
  uvmclear(pagetable, sz-2*PGSIZE);
  // sp为栈顶
  sp = sz;
  // 应该指的是栈尾
  stackbase = sp - PGSIZE;

  // 开始往栈中填入执行参数
  // Push argument strings, prepare rest of stack in ustack.
  for(argc = 0; argv[argc]; argc++) {
    if(argc >= MAXARG)
      goto bad;
    sp -= strlen(argv[argc]) + 1;
    sp -= sp % 16; // riscv sp must be 16-byte aligned
    if(sp < stackbase)
      goto bad;
    //argv来自用户空间，所以需要使用copyout
    if(copyout(pagetable, sp, argv[argc], strlen(argv[argc]) + 1) < 0)
      goto bad;
    //这什么东西
    //exec一次将参数中的一个字符串复制到栈顶，并在ustack中记录指向它们的指针
    ustack[argc] = sp;
  }
  //放置空指针
  ustack[argc] = 0;

  // push the array of argv[] pointers.
  sp -= (argc+1) * sizeof(uint64);
  sp -= sp % 16;
  if(sp < stackbase)
    goto bad;
  if(copyout(pagetable, sp, (char *)ustack, (argc+1)*sizeof(uint64)) < 0)
    goto bad;

  // arguments to user main(argc, argv)
  // argc is returned via the system call return
  // value, which goes in a0.
  p->trapframe->a1 = sp;

  // Save program name for debugging.
  for(last=s=path; *s; s++)
    if(*s == '/')
      last = s+1;
  safestrcpy(p->name, last, sizeof(p->name));
   
  //只有成功了才会来到这，才会覆盖掉旧的内存镜像
  // Commit to the user image.
  oldpagetable = p->pagetable;
  p->pagetable = pagetable;
  p->sz = sz;
  p->trapframe->epc = elf.entry;  // initial program counter = main
  p->trapframe->sp = sp; // initial stack pointer
  proc_freepagetable(oldpagetable, oldsz);

  return argc; // this ends up in a0, the first argument to main(argc, argv)

 bad:
  //释放新镜像，不改变旧镜像
  if(pagetable)
    proc_freepagetable(pagetable, sz);
  if(ip){
    iunlockput(ip);
    end_op();
  }
  return -1;
}

Real world

image-20230110010651653

xv6内核缺少一个类似malloc可以为小对象提供内存的分配器，这使得内核无法使用需要动态分配的复杂数据结构。【确实，感觉一分配就是一页（】

内存分配是一个长期的热门话题，基本问题是有效使用有限的内存并为将来的未知请求做好准备。今天，人们更关心速度而不是空间效率。此外，一个更复杂的内核可能会分配许多不同大小的小块，而不是（如xv6中）只有4096字节的块；一个真正的内核分配器需要处理小分配和大分配。

Lab：Pagetable

In this lab you will explore page tables and modify them to to speed up certain system calls and to detect which pages have been accessed.

不过遗憾的是usertests还有好几个没通过，具体都标注了。

Speed up system calls

When each process is created, map one read-only page at USYSCALL (a VA 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.

参考文章：MIT 6.S081 2021: Lab page tables

感想

乌龙

这里好像是因为实验改版了，我下的是2020年的实验包，在memlayout压根找不到USYSCALL和struct usyscall这俩东西。最后翻了下网上的总算找到了。

我一开始没找到，还以为USYSCALL以及usyscall这两个都得自己写在memlayout里面，想了很久都没想出来USYSCALL的值应该设置为多少。我认为只需满足两个条件即可：1.所处内存段应该是free memory那段，也即自kernel结束（PHYSTOP）到MAXVA这一大块。2.得确保能被用户和内核都能访问到。

前者意为虚拟地址在MAXVA和PHYSTOP之间，后者意为那段内存应该标记为PTE_U。这个范围是很宽泛的，我实在不知道要分配这期间的哪块内存，感觉也不大可能是真的自由度那么大。所以我就偷偷看了hints【悲】，想看它对这个USYSCALL应该写什么值有没有建议。结果发现这东西是实验给我们定的。遂去网上找到了它给的真正的USYSCALL值。

1
2
3
4
5
#define USYSCALL (TRAPFRAME - PGSIZE)

struct usyscall{
  int pid;
};

用户的ugetpid只找到了一个截图：

v2-0c2603da4c8102e46ae390a0d0b1191d_1440w

恕我愚钝实在不知道该把这段代码放在哪orz于是接下来写的东西就没有自测。

panic:freewalk leaf

一开始写好代码准备启动xv6的时候爆出了这么一个panic，搜了一下得到如下解答：

来源：MIT-6.S081-2020实验（xv6-riscv64）十：mmap

这时运行会发现freewalk函数panic：freewalk: leaf，这是因为freewalk希望所有虚拟地址已经被解绑并释放对应的物理空间了，该函数只负责释放页表。

让我得知freewalk在vm.c下面【吐槽，我一开始还以为是自由自在地走（，看到这个才反应过来是free walk，跟页表有关的】。结合freewalk的代码

image-20230110225359361

可以知道，造成这个panic的原因是需要手动释放页表项。而在这里

1
2
3
4
// in proc.c  freeproc()
if(p->usyscall)
    kfree((void*)p->usyscall);
  p->usyscall = 0;

仅仅是释放掉了对应的物理页，页表项并没有被释放。

对比了一下别人写的，才发现原来这里也需要修改：

1
2
3
4
5
6
7
8
9
10
11
// 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);
}

这样一来，问题就解决了。

总结

因而，可以看到，如果进程想使用页的话，需要经历以下四步：

  1. 通过kalloc获取物理页地址（可以通过该地址对页进行读写），并且记录在进程proc结构中（否则之后就获取不了了）
  2. 建立mappages映射
  3. 释放物理页
  4. 释放PTE映射

可见12和34都是分别一一对应的。

代码

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
// 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)
{
  struct proc *p;

  //有线程池那味了
  for(p = proc; p < &proc[NPROC]; p++) {
    acquire(&p->lock);
    if(p->state == UNUSED) {
      goto found;
    } else {
      release(&p->lock);
    }
  }
  return 0;

found:
  p->pid = allocpid();

  // Allocate a trapframe page.
  if((p->trapframe = (struct trapframe *)kalloc()) == 0){
    release(&p->lock);
    return 0;
  }
  // Allocate a usyscall page.
  if((p->usyscall = (struct usyscall *)kalloc()) == 0){
    release(&p->lock);
    return 0;
  }
  //在USYSCALL写入usyscall结构体
  p->usyscall->pid = p->pid;

  // 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.
  memset(&p->context, 0, sizeof(p->context));
  p->context.ra = (uint64)forkret;
  p->context.sp = p->kstack + PGSIZE;

  return p;
}

// 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->trapframe)
    kfree((void*)p->trapframe);
  p->trapframe = 0;
  if(p->pagetable)
    proc_freepagetable(p->pagetable, p->sz);
  p->pagetable = 0;
  if(p->usyscall)
    kfree((void*)p->usyscall);
  p->usyscall = 0;
  p->sz = 0;
  p->pid = 0;
  p->parent = 0;
  p->name[0] = 0;
  p->chan = 0;
  p->killed = 0;
  p->xstate = 0;
  p->state = UNUSED;
}

// 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_t pagetable;

  // An empty page table.
  pagetable = uvmcreate();
  if(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.
  if(mappages(pagetable, TRAMPOLINE, PGSIZE,
              (uint64)trampoline, PTE_R | PTE_X) < 0){
    uvmfree(pagetable, 0);
    return 0;
  }

  // map the trapframe just below TRAMPOLINE, for trampoline.S.
  if(mappages(pagetable, TRAPFRAME, PGSIZE,
              (uint64)(p->trapframe), PTE_R | PTE_W) < 0){
    uvmunmap(pagetable, TRAMPOLINE, 1, 0);
    uvmfree(pagetable, 0);
    return 0;
  }

 // 映射USYSCALL
  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;
}

// 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的父子进程用shared page共享页表应该会节省很多时间和空间，用个读时写。其他的倒是想不到了。不过这题会不会问的是那些在内核态和用户态穿梭频繁的system call呢？这个的话我就想不出来了。

Print a page table

write a function that prints the contents of a page table.

Define a function called vmprint().

It should take a pagetable_t argument, and print that pagetable in the format described below.

Insert if(p->pid==1) vmprint(p->pagetable) in exec.c just before the return argc, to print the first process’s page table.

image-20230110231020570

The first line displays the argument to vmprint. After that there is a line for each PTE, including PTEs that refer to page-table pages deeper in the tree. Each PTE line is indented by a number of " .." that indicates its depth in the tree.

Each PTE line shows the PTE index in its page-table page, the pte bits, and the physical address extracted from the PTE. Don’t print PTEs that are not valid.

In the above example, the top-level page-table page has mappings for entries 0 and 255. The next level down for entry 0 has only index 0 mapped, and the bottom-level for that index 0 has entries 0, 1, and 2 mapped.

感想

image-20230111000329475

很可惜，我在上面检索freewalk leaf到底是什么东西的时候，不小心看到了这题需要去参照freewalk这个提示【悲】其实我觉得这点还是需要绕点弯才能想到的，可能直接想到有点难【谁知道呢，世界线已经变动了】。

它这个打印页表其实最主要是考查如何遍历页表，这让人想起了walk这样的东西。但是walk是根据虚拟地址一级级找PTE的，中间很多地方会被跳过。有没有一个过程会在做事的时候遍历整个页表呢？答案是，这个过程就是释放页表的过程。释放页表才会一个个地看是否需要释放。释放页表的函数是freewalk，因而这道题参考freewalk的代码即可。

我觉得从“遍历页表”联想到“释放页表”这点是很巧的。不过也不会很突兀，毕竟学数据结构时就知道释放就需要遍历，逆向思维有点难但问题不大。

其他的就都挺简单的，不多赘述。

代码

记得在defs.h中添加声明

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
//在vm.c下
void
vmprint_helper(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 & PTE_V){
      for(int j=0;j<level;j++){
		printf(" ..");
      }
      printf("%d: pte %p pa %p\n",i,(uint64)pte,(uint64)(PTE2PA(pte)));
      if((pte & (PTE_R|PTE_W|PTE_X)) == 0){
        // this PTE points to a lower-level page table.
        uint64 child = PTE2PA(pte);
        vmprint_helper((pagetable_t)child,level+1);
      }
    }
  }
}

// 打印页表
void
vmprint(pagetable_t pagetable)
{
  // typedef uint64 *pagetable_t;所以pagetable可以以%p形式打印
  printf("page table %p\n",(uint64)pagetable);
  vmprint_helper(pagetable,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?

从上面操作系统的启动来看，进程1应该是在main.c中的userinit()中创建的进程，也是shell的父进程。【确实，经实践可得shell的pid为2】

可以来看一下userint的代码：

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
userinit(void)
{
  struct proc *p;

  p = allocproc();
  initproc = p;
  
  // 申请一页，将initcode的指令和数据放进去
  // allocate one user page and copy initcode's instructions
  // and data into it.
  /*
  uvminit的注释：
  	// Load the user initcode into address 0 of pagetable,
	// for the very first process.
	// sz must be less than a page.
  */
  uvminit(p->pagetable, initcode, sizeof(initcode));
  p->sz = PGSIZE;

  //为内核态到用户态的转变做准备
  // prepare for the very first "return" from kernel to user.
  /*
  Trap Frame是指中断、自陷、异常进入内核后,在堆栈上形成的一种数据结构
  */
  p->trapframe->epc = 0;      // user program counter
  p->trapframe->sp = PGSIZE;  // user stack pointer

  // 修改进程名
  safestrcpy(p->name, "initcode", sizeof(p->name));
  p->cwd = namei("/");

  //这个也许是为了能被优先调度
  p->state = RUNNABLE;

  release(&p->lock);
}

可见，page0是initcode的代码和数据，page1和page2用作了进程的栈，其中page1应该是guard page，page2是stack。

不过这里从exec的角度解释其实更通用：

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
exec(char *path, char **argv)
{
  //分配新页表
  if((pagetable = proc_pagetable(p)) == 0)
    goto bad;

  //elfhd应该指的是可执行文件头
  // Load program into memory.
  for(i=0, off=elf.phoff; i<elf.phnum; i++, off+=sizeof(ph)){
	//...
    //总之顺利读到了
    uint64 sz1;
    //读到了就给它分配新空间并且填入页表
    if((sz1 = uvmalloc(pagetable, sz, ph.vaddr + ph.memsz, flags2perm(ph.flags))) == 0)
      goto bad;
    sz = sz1;
  }

  //读完文件，开始造一个新的用户栈【fork之后用户栈是不会清空的】
  sz = PGROUNDUP(sz);
  uint64 sz1;
  if((sz1 = uvmalloc(pagetable, sz, sz + 2*PGSIZE, PTE_W)) == 0)
    goto bad;
  sz = sz1;
  // mark a PTE invalid for user access.造guard page
  uvmclear(pagetable, sz-2*PGSIZE);
  // sp为栈顶
  sp = sz;
  // 应该指的是栈尾
  stackbase = sp - PGSIZE;
  //...
}

page0就填程序。这里重点说明一下为什么page1和page2分别是guard page和stack。

按照它的那个算术关系，stack和guard page的虚拟内存位置关系应该是这样的：

image-20230111004330079

那为什么最后在页表中，变成了page1是gurad page，page2是stack这样上下颠倒了呢？看vm.c中的uvmalloc就能明白。

image-20230111004500827

在253行设置了新映射。可以看到，这里设置映射的顺序是sz->sz+PGSIZE，也即先设置guard page的映射，再设置stack的映射。所以，这两位才会上下颠倒了。

Detecting which pages have been accessed

Some garbage collectors (a form of automatic memory management) can benefit from information about which pages have been accessed (read or write). In this part of the lab, you will add a new feature to xv6 that detects and reports this information to userspace by inspecting the access bits in the RISC-V page table. The RISC-V hardware page walker marks these bits in the PTE whenever it resolves a TLB miss.

Your job is to implement pgaccess(), a system call that reports which pages have been accessed.

The system call takes three arguments. First, it takes the starting virtual address of the first user page to check. Second, it takes the number of pages to check. Finally, it takes a user address to a buffer to store the results into a bitmask (a datastructure that uses one bit per page and where the first page corresponds to the least significant bit).

You will receive full credit for this part of the lab if the pgaccess test case passes when running pgtbltest.

感想

实验内容：

实现void pgaccess(uint64 sva,int pgnum,int* bitmask);，一个系统调用。在这里面，我们要做的是，访问从sva到sva+pgnum*PGSIZE这一范围内的虚拟地址对应的PTE，然后查看PTE的标记项是否有PTE_A。有的话则在bitmask对应位标记为1.

应该注意的点：

1.需要进行内核态到用户态的参数传递 2.需要进行系统调用的必要步骤 3.PTE_A需要自己定义

以上是初见。做完了发现，确实就是那么简单，我主要时间花费在下的实验版本不对，折腾来折腾去了可能有一个小时，最后还是选择了直接把测试函数搬过来手工调用。已经换到正确的年份版本了【泪目】

有一点我忽视了，看了提示才知道：

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

也就是说每次检查到一个，就需要手动清除掉PTE_A标记。

还有一点以前一直没注意到的，头文件的引用需要注意次序。比如说要是把spinlock.h放在proc.h后面，就会寄得很彻底。

代码

那些系统调用的登记步骤就先省略了。

1
2
3
4
5
6
7
8
9
10
11
12
// kernel/sysproc.c
uint64
sys_pgaccess(void)
{
  uint64 sva;
  int pgnum;
  uint64 bitmask;

  if(argaddr(0,&sva) < 0 || argint(1, &pgnum) < 0 || argaddr(2, &bitmask) < 0)
    return -1;
  return pgaccess((void*)sva,pgnum,(void*)bitmask);
}
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
// kernel/pgaccess.c
#include "types.h"
#include "param.h"
#include "memlayout.h"
#include "riscv.h"
#include "spinlock.h"
#include "defs.h"
#include "proc.h"
int
pgaccess(void* sva,int pgnum,void* bitmask){
    if(pgnum > 32){
        printf("pgaccess: range too big.\n");
		exit(1);
    }
    int kmask = 0;
    struct proc* p = myproc();
    for(int i=0;i<pgnum;i++){
        pte_t* pte = walk(p->pagetable,(uint64)sva+i*PGSIZE,0);
        // 映射不存在，或者没有被访问过
        if(!pte || !(*pte & PTE_A)){
            continue;
        }
        kmask = (kmask | (1<<i));
        *pte = (*pte & (~PTE_A));
    }
    copyout(p->pagetable,(uint64)bitmask,(char*)(&kmask),sizeof(int)); 
    return 1;
}

A kernel page table per process

The goal of this section and the next is to allow the kernel to directly dereference user pointers.

Your first job is to modify the kernel so that every process uses its own copy of the kernel page table when executing in the kernel.

Modify struct proc to maintain a kernel page table for each process, and modify the scheduler to switch kernel page tables when switching processes. For this step, each per-process kernel page table should be identical to the existing global kernel page table. You pass this part of the lab if usertests runs correctly.

感想

这个其实平心而论不难，思路很简单。写着不难是不难，但想明白花费了我很多时间。

它这个要求我们修改kernel，使得每个进程都有一份自己的kernel page。至于要改什么，围绕着proc.c中，参照pagetable的生命周期摁改就行。还有一个地方它也提示了，就是要在swtch之前更换一下satp的值。

接下来，我说说我思考的几个点以及犯错的地方。

为什么要这么干

看完题目，我的第一印象是，这么干有啥用。。。因为我觉得以前那个所有进程共用内核页表确实很好了，没有必要每个进程配一个后来才发现，这个跟下面那个是连在一起的，目的是 allow the kernel to directly dereference user pointers.。所以，我们下面会把用户的pgtbl和这里dump出来的kpgtbl合在一起。

具体来说：

通常，进行地址翻译的时候，计算机硬件（即内存管理单元MMU）都会自动的查找对应的映射进行翻译（需要设置satp寄存器，将需要使用的页表的地址交给该寄存器）。

然而，在xv6内核需要翻译用户的虚拟地址时，因为内核页表不含对应的映射，计算机硬件不能自动帮助完成这件事。因此，我们需要先找到用户程序的页表，仿照硬件翻译的流程，一步一步的找到对应的物理地址，再对其进行访问。【walkaddr】这也就会导致copyin之类需要涉及内核和用户态交互的函数效率低下。

为了解决这个问题，我们尝试将用户页表也囊括进内核页表映射来。但是，如果将所有进程的用户页表都合并到同一个内核全局页表是不现实的。因而，我们决定换一个角度，让每个进程都仅有一张内核态和用户态共用的页表，每次切换进程时切换页表，这样就构造出了个全局的假象。

这两次实验就是为了实现该任务。在本次实验中，我们首先先实现内核页表的分离。

关于myproc()

在allocproc中初始化的时候，我一开始是这么写的：

1
2
// in proc.c allocproc()
perproc_kvminit();
1
2
3
4
5
6
7
8
9
10
11
12
13
// in vm.c
pagetable_t
perproc_kvminit()
{
  struct proc* p = myproc();
  p->kpgtbl = (pagetable_t) kalloc();
  memset(p->kpgtbl, 0, PGSIZE);

  // uart registers
  pkvmmap(p->kpgtbl,UART0, UART0, PGSIZE, PTE_R | PTE_W);
  // ...
  return pt;
}

这样会死得很惨，爆出如下panic：

image-20230114011100370

通过hints的调试贴士

A missing page table mapping will likely cause the kernel to encounter a page fault. It will print an error that includes sepc=0x00000000XXXXXXXX. You can find out where the fault occurred by searching for XXXXXXXX in kernel/kernel.asm.

我发现程序在这里绷掉了：

1
p->kpgtbl = (pagetable_t) kalloc();

而且显而易见，是系统启动时崩的。

经过了漫长的思考，我震惊地发现了它为什么崩了（）

首先，这段代码语法上是没有问题的。它固然犯了发布未初始化完成的对象这样的并发错误【我有罪】，也破坏了proc的封装性【proc中的很多私有属性本来应该作用域仅在proc.c中的。此处为了能让vm.c访问到proc中的属性，不得不给vm.c添上了proc.h的头文件】，但是它并不是语法错误，还是能用的。我做了这样的测试样例证明它没有问题：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <stdio.h>
#define MAX 10
typedef int pagetable_t;

struct proc{
	pagetable_t kpgtbl;
}; 

struct proc processes[MAX];

struct proc* myproc(){
	return &processes[0];
};

void kvminit(){
	myproc()->kpgtbl = 1;
}

int main(){
	struct proc* p = &processes[0];
	kvminit();
	printf("%d",p->kpgtbl);
	return 0;
}

我一路顺着os启动的路径找，也想不出来这能有什么错，因而非常迷茫。

此时我灵光一闪，会不会是myproc()在os刚启动的时候是发挥不了作用的？于是我一路顺着myproc的代码看下去：

1
2
3
4
5
6
7
8
struct proc*
myproc(void) {
  push_off();
  struct cpu *c = mycpu();
  struct proc *p = c->proc;
  pop_off();
  return p;
}

那么，mycpu()获得的cpu的proc是怎么得到的呢？

我搜寻了一下os启动代码，发现了cpu的proc得到的路径。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void
main()
{
  if(cpuid() == 0){
    consoleinit();
    printfinit();
    printf("\n");
    printf("xv6 kernel is booting\n");
    printf("\n");
	//...很多很多init
    userinit();      // first user process
    __sync_synchronize();
    started = 1;
  } else {
	// ...
  }

  //调度执行第一个进程
  scheduler();        
}

创建完进程后，就进入scheduler进行进程的调度：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void
scheduler(void)
{
  struct proc *p;
  struct cpu *c = mycpu();
  // ...
    int found = 0;
    for(p = proc; p < &proc[NPROC]; p++) {
		// ...
        //在这里！！！！
        c->proc = p;
        swtch(&c->context, &p->context);

        c->proc = 0;
// ...

因而，c->proc是在创建进程的第一次调度后初始化的，也即，myproc只有在执行第一次scheduler之后才可以调用。而！！！

当执行调度前的userinit时：

1
2
3
4
5
6
7
void
userinit(void)
{
  struct proc *p;

  p = allocproc();
  initproc = p;

它进行了allocproc。我们亲爱的allocproc接下来就会调用perproc_kvminit，然后perproc_kvminit中调用myproc。此时尚未进行初次调度，因而c->proc未初始化，myproc返回的是0，也即null。这样一来，myproc()->kpgtbl就发生了空指针异常，也即scause = 15——写入页错误。

因而，对于myproc()的调用需要慎之又慎。

系统调用

系统调用时，是如何知道要用的是p中的内核页表而非global内核页表呢？

依然还是从os的启动说起。

在main.c中，kvminithart开启了页表，此时的页表为全局的内核页表：

1
2
3
4
5
6
7
8
// Switch h/w page table register to the kernel's page table,
// and enable paging.
void
kvminithart()
{
  w_satp(MAKE_SATP(kernel_pagetable));
  sfence_vma();
}

当userinit被调度时，全局的内核页表被换成了proc中的内核页表：

1
2
3
4
5
6
// in proc.c scheduler()
p->state = RUNNING;
w_satp(MAKE_SATP(p->kpgtbl));
sfence_vma();
c->proc = p;
swtch(&c->context, &p->context);

但是这样还没有结束。因为我们除了得更换目前的页表，还得更换trapframe中的内核页表相关的东西：

1
2
3
4
struct trapframe {
  /*   0 */ uint64 kernel_satp;   // kernel page table
  /*   8 */ uint64 kernel_sp;     // top of process's kernel stack
}

为啥还要更换trapframe中的呢？因为以后系统调用的时候，uservec是从这里读取值来作为内核栈和内核页表的来源的：

1
2
3
4
5
6
7
8
9
10
# in uservec
		# restore kernel stack pointer from p->trapframe->kernel_sp
        # 完成了内核栈的切换
        ld sp, 8(a0)

		# 完成了页表的切换
        # restore kernel page table from p->trapframe->kernel_satp
        ld t1, 0(a0)
        csrw satp, t1
        sfence.vma zero, zero

所以，为了以后系统调用能顺利自发进行，我们需要把栈帧也一起换掉。怎么换呢？我们是否还要在一些地方人工把trapframe的值设置为我们自己的内核栈内核页表？答案是，不用！这些会由其他代码自动完成。

前面说到userinit的进程p被调度，satp换成了我们自己的内核页表。那么，在之后的内核态，satp都将保持我们自己的内核页表。当要返回用户态时，会执行如下代码：

1
2
3
4
// in usertrapret
  // 重置trapframe
  p->trapframe->kernel_satp = r_satp();         // kernel page table
  p->trapframe->kernel_sp = p->kstack + PGSIZE; // process's kernel stack

satp内的值为我们自己的内核页表，而非全局页表。因而这样栈帧中的页表就会被自然而然地写入为进程的内核页表。之后返回用户态，以及之后之后的各种中断，就都会一直使用自己的内核页表了。【试了一下，这里如果改成非即时从satp读，而是默认的kernel_pagetable的话，会一直死循环】

不得不说，真是设计精妙啊！！！不过我觉得，要是这里写成kernel_pagetable，然后让我们自己改的话将是薄纱（。当然它应该也不会这么做，因为，kernel_pagetable事实上是不对外发布的。它这里这么写热读，最直接的原因还是因为读不到kernel_pagetable。这算是无心插柳柳成荫吗233

释放页表但不释放物理内存

其实答案就在它给的proc_freepagetable里。

1
2
3
4
5
6
7
8
9
// 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);
  uvmfree(pagetable, sz);
}

uvmfree遍历页表，对每个存在的页表项，都试图找到其物理内存，并且释放物理内存和表项。如果页表项存在，但页表项对应的物理内存不存在，就会抛出freewalk leaf的异常。

uvmunmap会释放掉参数给的va的页表项，最后一个参数表示释放or不释放。

在这里，使用这两个的组合技，就可以达到不释放TRAMPOLINE和TRAPFRAME的物理内存，又不会让uvmfree出错的效果。

代码

初始化

初始化kpgtbl。由于现在内核栈存在各自的内核页表而非global内核页表中，所以在procinit中的对内核栈的初始化也得放在这：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// in proc.c allocproc()
  // An empty user page table.
  p->pagetable = proc_pagetable(p);
  if(p->pagetable == 0){
    freeproc(p);
    release(&p->lock);
    return 0;
  }

  p->kpgtbl = perproc_kvminit();

  char *pa = kalloc();
  if(pa == 0)
    panic("kalloc");
  uint64 va = KSTACK((int) (p - proc));
  pkvmmap(p->kpgtbl,va, (uint64)pa, PGSIZE, PTE_R | PTE_W);
  p->kstack = va;
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
// in vm.c
pagetable_t
perproc_kvminit()
{
  pagetable_t pt = (pagetable_t) kalloc();
  memset(pt, 0, PGSIZE);

  // uart registers
  pkvmmap(pt,UART0, UART0, PGSIZE, PTE_R | PTE_W);

  // virtio mmio disk interface
  pkvmmap(pt,VIRTIO0, VIRTIO0, PGSIZE, PTE_R | PTE_W);

  // CLINT
  pkvmmap(pt,CLINT, CLINT, 0x10000, PTE_R | PTE_W);

  // PLIC
  pkvmmap(pt,PLIC, PLIC, 0x400000, PTE_R | PTE_W);

  // map kernel text executable and read-only.
  pkvmmap(pt,KERNBASE, KERNBASE, (uint64)etext-KERNBASE, PTE_R | PTE_X);

  // map kernel data and the physical RAM we'll make use of.
  pkvmmap(pt,(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.
  pkvmmap(pt,TRAMPOLINE, (uint64)trampoline, PGSIZE, PTE_R | PTE_X);
  return pt;
}
1
2
3
4
5
6
7
8
// in vm.c
void
pkvmmap(pagetable_t pgtbl,uint64 va, uint64 pa, uint64 sz, int perm)
{
  // 当第一个进程开始时，mycpu->proc = null,所以这里不能调用myproc
  if(mappages(pgtbl, va, sz, pa, perm) != 0)
    panic("kvmmap");
}
swtch时切换页表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// in proc.c scheduler()
p->state = RUNNING;
w_satp(MAKE_SATP(p->kpgtbl));
sfence_vma();
c->proc = p;
swtch(&c->context, &p->context);

//...

	#if !defined (LAB_FS)
    if(found == 0) {
      // 没有进程运行时使用全局kernel_pagetable
      kvminithart();
      intr_on();
      asm volatile("wfi");
    }
修改kvmpa
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include "spinlock.h"
#include "proc.h"

uint64
kvmpa(uint64 va)
{
  uint64 off = va % PGSIZE;
  pte_t *pte;
  uint64 pa;

  pte = walk(myproc()->kpgtbl, va, 0);
  if(pte == 0)
    panic("kvmpa");
  if((*pte & PTE_V) == 0)
    panic("kvmpa");
  pa = PTE2PA(*pte);
  return pa+off;
}
释放
1
2
3
4
// in kernel.proc.c freeproc()
  if(p->kpgtbl)
    proc_freekpgtbl(p->kpgtbl,p->kstack);
  p->kpgtbl = 0;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
extern char etext[];  // kernel.ld sets this to end of kernel code.

void
proc_freekpgtbl(pagetable_t pagetable,uint64 stack )
{
  uvmunmap(pagetable, UART0, 1, 0);
  uvmunmap(pagetable, VIRTIO0, 1, 0);
  uvmunmap(pagetable, CLINT, 0x10000/(uint64)PGSIZE, 0);
  uvmunmap(pagetable, PLIC, 0X400000/(uint64)PGSIZE, 0);
  uvmunmap(pagetable, KERNBASE, (uint64)((uint64)etext-KERNBASE)/PGSIZE, 0);
  uvmunmap(pagetable, (uint64)etext,(PHYSTOP-(uint64)etext)/PGSIZE, 0);
  //kvmmap(KERNBASE, KERNBASE, (uint64)etext-KERNBASE, PTE_R | PTE_X);
  uvmunmap(pagetable, TRAMPOLINE, 1, 0);
  uvmunmap(pagetable, stack, 1,1 );
  uvmfree(pagetable, 0);
}

Simplify copyin/copyinstr

参考：

6.S081学习记录-lab3

The kernel’s copyin function reads memory pointed to by user pointers. It does this by translating them to physical addresses, which the kernel can directly dereference. It performs this translation by walking the process page-table in software. Your job in this part of the lab is to add user mappings to each process’s kernel page table (created in the previous section) that allow copyin (and the related string function copyinstr) to directly dereference user pointers.

Replace the body of copyin in kernel/vm.c with a call to copyin_new (defined in kernel/vmcopyin.c); do the same for copyinstr and copyinstr_new. Add mappings for user addresses to each process’s kernel page table so that copyin_new and copyinstr_new work.

感想

这题很直观的思路是，在每个user pagetable添加映射的地方也添加kpgtbl的映射。但问题是，“每个user pagetable添加映射的地方”都是哪？

误入幻想

我一开始想着偷偷懒，直接在proc.c和vm.c中每个操纵pagetable的地方都加上对kpgtbl的操纵。但很快我就给搞晕了。这时候，我心中萌生一计【PS：下面说的最后都没成功】：我直接快进到把proc结构中的pagetable属性给删了，然后每个出现p->pagetable的地方，都用p->kpgtbl代替，直接让两表合为一表，然后之后make的时候哪里报错改哪里，这不就一劳永逸地把所有出现pagetable的地方都改为kpgtbl了嘛。我振奋地去试了一下，将所有地方出现的pagetable都替换成了kpgtbl，把proc.c中的proc_pagetable()和proc_freepagetable()的出现的地方都换成了perproc_kvminit()以及proc_freekpgtbl()，还做了一个小细节，就是在userinit中调用的uvminit中，我把这样：

1
2
3
4
5
6
7
8
9
10
11
12
void
uvminit(pagetable_t pagetable, uchar *src, uint sz)
{
  char *mem;

  if(sz >= PGSIZE)
    panic("inituvm: more than a page");
  mem = kalloc();
  memset(mem, 0, PGSIZE);
  mappages(pagetable, 0, PGSIZE, (uint64)mem, PTE_W|PTE_R|PTE_X|PTE_U);
  memmove(mem, src, sz);
}

换成了这样：

1
2
3
4
5
6
7
8
9
10
11
12
void
uvminit(struct proc* p, uchar *src, uint sz)
{
  char *mem;

  if(sz >= PGSIZE)
    panic("inituvm: more than a page");
  mem = kalloc();
  memset(mem, 0, PGSIZE);
  mappages(p->kpgtbl, 0, PGSIZE, (uint64)mem, PTE_W|PTE_R|PTE_X|PTE_U);
  memmove(mem, src, sz);
}

最后，在启动的时候，卡在了初次调度切换不到initcode这边，没有调用exec。没有panic，似乎只在死循环。我也实在想不出是什么原因，最后把代码删了【悲】想想我应该用git保存一下改前改后的。这下实在是难受了，我的想法也暂时没有机会实践了。等到明年大三说不定还得再交一次这玩意，到时候再探究探究吧hhh

走上正途

发现这个最后没成还改了半天的我最后非常沮丧地去看了hints【又一心浮气躁耐心不足的表现，但确实绷不住了】，发现它居然说只用修改三个地方：fork、exec以及sbrk。

我把kernel/下的每个文件都搜了一遍，发现确实，只有这三个，以及proc.c，vm.c，涉及到对页表项的增删。而在用户态中，想要对进程的内存进行管理，似乎只能通过系统调用sbrk。而proc.c和vm.c中确实没什么好改的。因为里面增加的映射，都是trapframe、trampoline、inicode这种不会一般在copyin中用到的虚拟地址。所以，要改的地方，确确实实，只有fork、exec以及sbrk。

Xv6 applications ask the kernel for heap memory using the sbrk() system call.

很悲伤，我的初见思路是错误的（）

而这三个地方的共同点，就是都会对页表进行大量的copy。

1
2
3
4
5
6
7
//in proc.c fork()
  // Copy user memory from parent to child.
  if(uvmcopy(p->pagetable, np->pagetable, p->sz) < 0){
    freeproc(np);
    release(&np->lock);
    return -1;
  }
1
2
3
4
//in exec.c
  // Commit to the user image.
  oldpagetable = p->pagetable;
  p->pagetable = pagetable;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//in syscall.c
uint64
sys_sbrk(void)
{
  int addr;
  int n;

  if(argint(0, &n) < 0)
    return -1;
  addr = myproc()->sz;
  if(growproc(n) < 0)
    return -1;
  return addr;
}
//in proc.c growproc()
uvmalloc(p->pagetable, sz, sz + n)) == 0

所以，我们要做的事情很简单：写一个坐收渔翁之利的函数，内容为把一个页表的所有内容复制到另一个页表。然后再在这几个地方调用这个函数即可。

代码

注意：由于我写得实在是太烦了，已经思考不下去了。为了放过我自己，我写了个虽然能过得去测试但是其实毛病重重的代码。垃圾点为以下几点：

  1. 需要去掉freewalk中的panic

    我的kvmcopy的实现是，user pagetable（下面简称up）和tp的相同虚拟地址共用同一页物理内存。也就是说，页表不一样，但所指向的物理内存是同一个。这样设计的目的是为了能够让tp及时用到up的更新后的数据。

    这会导致啥呢？在进程释放时，需要一起调用proc_freepagetable和proc_freekpgtbl。proc_freepagetable调用完后，所指向的那堆物理内存已经寄完了，如果再调用proc_freekpgtbl，显然，就会发生页表未释放但页表对应内存已经释放的问题，freewalk就会panic。因此，我简单粗暴地直接把freewalk的panic删掉了【抖】也许有别的解决方法，但我真是烦得不想想了放过我吧（

  2. 好像暂时没有第二点了（）

渔翁之利函数
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
// in vm.c
// 效仿的是vm.c中的uvmcopy
int
kvmcopy(pagetable_t up, pagetable_t kp, uint64 sz)
{  
  pte_t *pte;
  uint64 pa, i;
  uint flags;

  for(i = 0; i < sz; i += PGSIZE){ 
    if((pte = walk(up, i, 0)) == 0 || (*pte & PTE_V) == 0){
        if(walk(kp,i,0) == 0){
            //如果up不存在此项，kp存在，就直接删了
            uvmunmap(kp,i,PGSIZE,0);
        }
        continue;
    }
    pa = PTE2PA(*pte);
    flags = PTE_FLAGS(*pte);
    // 注意去除PTE_U，否则内核态无法访问
    flags = (flags & (~PTE_U));
    if(mappages(kp, i, PGSIZE, pa, flags) != 0){
      goto err;
    }
  }
  return 0;

 err:
  uvmunmap(kp, 0, i / PGSIZE, 1);
  return -1;
}
修改fork、exec、sbrk
fork
1
2
3
4
5
6
7
8
9
10
11
12
// in proc.c fork()
  // Copy user memory from parent to child.
  if(uvmcopy(p->pagetable, np->pagetable, p->sz) < 0){
    freeproc(np);
    release(&np->lock);
    return -1;
  }
  if(kvmcopy(np->pagetable, np->kpgtbl, p->sz) < 0){
    freeproc(np);
    release(&np->lock);
    return -1;
  }
exec
1
2
3
4
5
6
7
8
9
10
11
12
// in exec.c
  // Commit to the user image.
  oldpagetable = p->pagetable;
  p->pagetable = pagetable;

  p->sz = sz;
  p->trapframe->epc = elf.entry;  // initial program counter = main
  p->trapframe->sp = sp; // initial stack pointer
  proc_freepagetable(oldpagetable, oldsz);

  // 添上此句
  kvmcopy(p->pagetable, p->kpgtbl, p->sz);
sbrk
1
2
3
4
5
6
7
8
9
10
11
12
13
14
uint64
sys_sbrk(void)
{
  int addr;
  int n;

  if(argint(0, &n) < 0)
    return -1;
  addr = myproc()->sz;
  if(addr+n >= PLIC)    return -1;
  if(growproc(n) < 0)
    return -1;
  return addr;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// in proc.c
// Grow or shrink user memory by n bytes.
// Return 0 on success, -1 on failure.
int
growproc(int n)
{
  uint sz;
  struct proc *p = myproc();

  sz = p->sz;
  // ...
  p->sz = sz;
  // 加这个
  kvmcopy(p->pagetable, p->kpgtbl, p->sz);
  return 0;
}
userinit

这一步不能忽视，因为内核启动的时候就需要用到copyinstr。

1
2
3
4
5
// in proc.c userinit()
  uvminit(p->pagetable, initcode, sizeof(initcode));
  p->sz = PGSIZE;
  // 加这个！
  kvmcopy(p->pagetable, p->kpgtbl, p->sz);
删掉freewalk的panic（我特有的缺点）
1
2
3
4
5
6
// in vm.c freewalk()    
    if((pte & PTE_V) && (pte & (PTE_R|PTE_W|PTE_X)) == 0){
      // ...
    } else if(pte & PTE_V){
      //panic("freewalk: leaf");
    }