0.Briefly Speaking

这篇博客是完成6.S081第三个实验之前的准备环节，主要内容是阅读相关的源码。之前提过xv6最宝贵的部分是内核源码，这些是完成实验之前必备的基础，也是学习这门课的精髓所在，所以我准备再开一个系列博客专门用来记录xv6源码阅读的环节。

这些阅读源码的部分一定会需要查询很多的资料，零零碎碎地容易遗忘。另外，挑选这些源码是因为xv6-book的阅读过程中有对应代码的提纲，我们就顺着它的建议一点点进行阅读。xv6的启动过程我们放到最后面来写，因为这需要很多的前备知识。

这篇文章中主要对实验三中需要深入理解的内核源码部分(虚拟内存部分代码)进行阅读和记录。本博客主要包含以下文件中源码的阅读(偶尔为了理解，也会短暂跳跃到其他代码)。

1.kernel/memorylayout.h
2.kernel/vm.c(434 rows)
3.kernel/kalloc.h
4.kernel/exec.c
5.kernel/riscv.h

1.kernel/vm.c

首先来看整个虚拟内存系统中的最核心的代码，kernel/vm.c包含了xv6中绝大部分用于操控地址空间和页表的代码。注意vm.c中uvm开头的函数用来操纵用户态地址空间，kvm开头的函数用来操纵内核地址空间，这是在xv6 book中已经指明的，但是要注意它们都在内核态中运行，使用的都是内核页表。
接下来看看源码的细节。

1.1 三个全局变量

// 在vm.c的开头就是三个全局变量，如下所示，在这里一一来分析它们的含义
/*
 * the kernel's page table.
 */
pagetable_t kernel_pagetable;

extern char etext[];  // kernel.ld sets this to end of kernel code.

extern char trampoline[]; // trampoline.S

首先看第一个全局变量，kernel_pagetable，它是一个pagetable_t类型的变量。索引到对应源代码可以看到如下的定义：

typedef uint64 pte_t;		 // 页表项的大小是64位，所以定义为uint64类型
typedef uint64 *pagetable_t; // 512 PTEs，一个级别页表含有512个PTE，正好对应4K的页大小

所以在xv6的定义中，一个目录项(page table entry, pte)的大小是64比特，即8个字节，故一个4k大小的页正好对应512个PTE。事实上，采用多级页表结构的最重要的原因就是节约因为存储页表而耗费的内存页。我们确定要设置多少级页表时，要尽可能地保证一级虚拟地址正好映射到一个页表内，不要超出或浪费，详见OSTEP中的讲解。

PTR的具体格式在xv6-book中有所介绍，如下所示：

相对应的，pagetable_t就是指向uint64的指针，它本质上指向了内核页表的根目录页表(root page-table page)的物理地址，事实上当使用MMU进行虚拟地址转换时，这个地址会被存放在SATP寄存器上，这就是第一个变量的全部含义。

再来看第二个全局变量：

extern char etext[];  // kernel.ld sets this to end of kernel code.

据注释所说，etext将会被链接脚本放置在内核代码的结束位置，我们去看看链接脚本(kernel/kernel.ld)的对应段是怎么写的：

# kernel/kernel.ld (12-20行)
# 链接脚本中.的含义是当前地址计数器，可以直接引用当前地址位置
.text : {
    *(.text .text.*)		# 将所有文件的text text.*全部放置在kernel的代码段
    . = ALIGN(0x1000);		# 对齐至0x1000(4096)，即新开一个页面
    _trampoline = .;		# trampoline放置在下一个页的开头位置
    *(trampsec)				# 放置trampsec段到此处，trampsec段就是trampoline开头声明的
    . = ALIGN(0x1000);		# 再新开一个页面
    ASSERT(. - _trampoline == 0x1000, "error: trampoline larger than one page");
    PROVIDE(etext = .);		# 定义一个全局标号etext，等于此处地址.
  }

所以这里其实定义了一个字节指针，指向内核代码部分的结束位置。

第三个全局变量是：

extern char trampoline[]; // trampoline.S

根据注释，这里的含义是它指向了trampoline代码的开始，至于trampoline代码的实现我们会在做下一个实验的时候仔细研究一下，这里不再展开细节。如果你打开trampoline.S这个汇编代码文件，在开头会有如下内容，它们定义了trampoline是一个全局标号，实际上指向代码的开始：

.section trampsec
.globl trampoline
trampoline:

下面准备开始介绍函数了，首先从最核心也是最底层的walk函数开始，再逐渐延伸到它们的调用者上去，这样自底向上地介绍会更加容易理解。

1.2 walk函数

walk函数的作用，如果简单来说的话就是：用软件来模拟硬件MMU查找页表的过程，返回以pagetable为根页表，经过多级索引之后va这个虚拟地址所对应的页表项，如果alloc != 0，则在需要时创建新的页表页，反之则不用。注意第一级根页表肯定是存在的，所以这个函数最多会创建两次新的页表页就已经到达了叶级页表(leaf page table)。根页表和中间级页表的有效位(valid bit)表示的是：对应页表页是否已经分配，而叶级页表有效位表示的是对应物理页是否已经被使用。

建议结合以下索引过程图来加深理解：

在下面直接给出walk函数含注释的源码：

// 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.
pte_t *
walk(pagetable_t pagetable, uint64 va, int alloc)
{
  if(va >= MAXVA)			// 如果虚拟地址超过了最大值，陷入错误
    panic("walk");
  
  // 模拟三级页表的查询过程，三级列表索引两次页表即可，最后一次直接组成物理地址
  for(int level = 2; level > 0; level--) {
  	// 索引到对应的PTE项
    pte_t *pte = &pagetable[PX(level, va)];
    // 确认一下索引到的PTE项是否有效(valid位是否为1)
    if(*pte & PTE_V) {
      // 如果有效接着进行下一层索引
      pagetable = (pagetable_t)PTE2PA(*pte);
    } else {
      // 如果无效(说明对应页表没有分配)
      // 则根据alloc标志位决定是否需要申请新的页表
      if(!alloc || (pagetable = (pde_t*)kalloc()) == 0)
        return 0;
      // 将申请的页表填满0
      memset(pagetable, 0, PGSIZE);
      // 将申请来的页表物理地址，转化为PTE并将有效位置1，记录在当前级页表
      // 这样在下一次访问时，就可以直接索引到这个页表项
      *pte = PA2PTE(pagetable) | PTE_V;
    }
  }
  return &pagetable[PX(0, va)];
}

阅读这段代码时还需要注意一个问题，这在xv6 book中已经指出了，那就是以上代码可以正常工作的前提是，我们在进行内核地址空间的映射时，物理内存和虚拟内存采用的是直接映射的方法。

事实上要有这样一个概念，我们在C语言程序中所使用的指针，本质上都是一个个虚拟地址，那么下面这段代码看上去就有些意思了，因为我们直接将物理地址赋值给了虚拟地址，这是因为内核地址空间中执行的是直接映射策略。还有一种情况下，这两者也是等价的，即处理器关闭分页机制时，物理地址也等于虚拟地址，这种情况在下面kvmmake时会发现，到时候会再提。

// 这行代码从PTE中提取出物理地址，直接赋值给pagetable指针(而它是一个虚拟地址)
// 这样赋值合理吗？只有在虚拟地址==物理地址时合理，即直接映射。
pagetable = (pagetable_t)PTE2PA(*pte);

最后，阅读这段代码时可以注意到有几个宏非常的有意思，我们来看一看它们的源代码，首先是宏定义PX(level, va)：

// extract the three 9-bit page table indices from a virtual address.
#define PXMASK          0x1FF // 9 bits
#define PXSHIFT(level)  (PGSHIFT+(9*(level)))
#define PX(level, va) ((((uint64) (va)) >> PXSHIFT(level)) & PXMASK)

据注释所说，PX的含义就是抽取出虚拟地址va在多级地址转换过程中对应的虚拟地址字段，这个字段将被会用来索引对应级别的页表。level表示当前翻译到第几级页表，va则表示对应的虚拟地址。

接下来是PA2PTE和PTE2PA，据名字可以看出它们实现的应该是页表项到物理地址之间的转换：

// shift a physical address to the right place for a PTE.
#define PA2PTE(pa) ((((uint64)pa) >> 12) << 10)
#define PTE2PA(pte) (((pte) >> 10) << 12)

这段代码的定义非常有意思，首先弄明白一个PTE和物理地址之间的对应关系，如下图所示。
当我们得到一个页表项PTE时，由于它的低十位是各种标记，所以要把低十位先右移出去，然后就得到了44位长的PPN，左移12位之后正好指向这个物理页的开始地址，这就是PTE2PA的逻辑。这个开始地址再和12位页内偏移拼接在一起就得到了完整的物理地址。

反过来就是PA2PTE的逻辑，这里不再赘述。

1.3 mappages函数

在理解了walk函数的基础上，接下来可以看另外一个核心函数mappages，它是用来装载一个新的映射关系(可能不止一个页面大小)的，首先给出完整的含中文注释的代码：

// 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)
{
  // a存储的是当前虚拟地址对应的页
  // last存放的是最后一个应设置的页
  // 当 a==last时，表示a已经设置完了所有页，完成了所有任务
  uint64 a, last;
  pte_t *pte;
  
  // 当要映射的页面大小为0时，这是一个不合理的请求，陷入panic
  if(size == 0)
    panic("mappages: size");
  
  // a,last向下取整到页面开始位置，设置last相当于提前设置好了终点页
  // PGROUNDDOWN这个宏在后面会详细讲解
  a = PGROUNDDOWN(va);
  last = PGROUNDDOWN(va + size - 1);
  // 开始迭代式地建立映射关系
  for(;;){
    // 调用walk函数，返回当前地址a对应的PTE
    // 如果返回空指针，说明walk没能有效建立新的页表页，这可能是内存耗尽导致的
    if((pte = walk(pagetable, a, 1)) == 0)
      return -1;
    // 如果找到了页表项，但是有效位已经被置位，表示这块物理内存已经被使用
    // 这说明原本的虚拟地址va根本不足以支撑分配size这么多的连续空间，陷入panic
    if(*pte & PTE_V)
      panic("mappages: remap");
    
    // 否则就可以安稳地设置PTE项，指向对应的物理内存页，并设置标志位permission
    *pte = PA2PTE(pa) | perm | PTE_V;
    // 设置完当前页之后看看是否到达设置的最后一页，是则跳出循环
    if(a == last)
      break;
    // 否则设置下一页
    a += PGSIZE;
    pa += PGSIZE;
  }
  return 0;
}

所以这个函数在理解了walk函数的基础上是比较容易分析的，但是这个函数还有一些需要格外注意的一些细节，比如PGROUNDDOWN宏，它和PGROUNDUP的定义一并展示如下：

// PGROUNDUP(sz)：sz大小的内存至少使用多少页才可以存下
// PGROUNDDOWN(a)：地址a所在页面是多少号页面，拉回所在页面开始地址
#define PGROUNDUP(sz)  (((sz)+PGSIZE-1) & ~(PGSIZE-1))
#define PGROUNDDOWN(a) (((a)) & ~(PGSIZE-1))

从定义上可以看出，这两个宏的适用对象不一样，PGROUNDDOWN(a)的使用对象是地址，PGROUNDUP(sz)的使用对象是内存大小，它们的含义我已经注释在了上面。如果还是很难理解它们的含义，不妨代入一些数字自己试试看，稍有基础的人应该很快就可以理解，示意图如下所示：

# PGSIZE - 1 = 4096 - 1 = 4095 = 0x1111 1111 1111
# ~(PGSIZE-1)相当于低12位全部取0，高于12位的部分保持不变
# a & ~(PGSIZE-1)相当于将虚拟地址a的低12位全部置为0

1.4 kvmmap函数

接下来就可以看看kvmmap函数的实现了，据源码注释所述这个函数负责在内核页表中添加一个映射项，且此函数仅在启动时初始化内核页表时使用。它仅仅是mappages函数薄薄的一层封装与调用，使用时将内核页表指针传入mappages函数的第一项即可。

// 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)
{
  // 判断mappages是否执行成功，不成功则陷入panic
  if(mappages(kpgtbl, va, sz, pa, perm) != 0)
    panic("kvmmap");
}

1.5 kvmmake函数

接下来，就可以看看kvmmake函数的实现了，这个函数主要调用的就是上面的kvmmap函数。这个函数的功能是为内核建立了一个直接映射的页表，如xv6 book中的示例图所示。除了trampoline和内核栈页面被映射到高地址空间以外(主要是为了设置守护页)，其他的部分全部是直接映射关系，这样的好处是方便内核的操作，直接将返回的物理地址当虚拟地址使用，就像上面的walk函数一样。

在阅读下面的代码时，请结合上图中的地址标注。

// Make a direct-map page table for the kernel.
pagetable_t
kvmmake(void)
{
  // 指向内核根页表的指针，也是本函数的返回值
  pagetable_t kpgtbl;
  
  // 为内核根页表分配一个完整的页面，并将页面初始化
  kpgtbl = (pagetable_t) kalloc();
  memset(kpgtbl, 0, PGSIZE);

  // 映射UART0，大小为一个页面
  kvmmap(kpgtbl, UART0, UART0, PGSIZE, PTE_R | PTE_W);

  // 映射VIRTIO disk，大小为一个页面
  kvmmap(kpgtbl, VIRTIO0, VIRTIO0, PGSIZE, PTE_R | PTE_W);

  // 映射PLIC(Platform-Level Interrupt Controller), 大小为0x40000
  // 这个大小可以由0x10000000 - 0x0C000000计算得到
  kvmmap(kpgtbl, PLIC, PLIC, 0x400000, PTE_R | PTE_W);

  // 映射内核代码到KERBASE位置，etext是我们上面已经介绍过的内核代码结尾标志
  // 用etext - KERBASE就是代码段长度
  kvmmap(kpgtbl, KERNBASE, KERNBASE, (uint64)etext-KERNBASE, PTE_R | PTE_X);

  // 将内核数据段和RAM直接映射过来
  // 使用PHYSTOP - etext就是这两段应该剩余的长度
  kvmmap(kpgtbl, (uint64)etext, (uint64)etext, PHYSTOP-(uint64)etext, PTE_R | PTE_W);

  // 将trampline页面映射到内核虚拟地址空间的最高一个页面
  // TRAMPOLINE的定义如下，就是最高虚拟地址减去一个页面大小
  // #define TRAMPOLINE (MAXVA - PGSIZE)
  // 注意阅读上面的链接脚本时，我们将trampsec段放置在了内核代码后面
  // 那其实也是trampoline的开头，也就是说我们其实映射了trampoline页面两次
  kvmmap(kpgtbl, TRAMPOLINE, (uint64)trampoline, PGSIZE, PTE_R | PTE_X);

  // 映射各个进程的内核栈到内核页表中
  proc_mapstacks(kpgtbl);
  
  // 返回映射好的内核页表
  return kpgtbl;
}

在阅读这段代码时，要注意一件事情。我们在前面所述的三个全局变量，包括etext和trampoline全部都在映射内核页表时使用到了，但是要注意它们本质都是虚拟地址(指针)，那么为什么可以将它们作为物理地址分配传递给kvmmap函数呢？

其实在执行上述代码的时候xv6的分页机制是关闭的(kernel/start.c 34-35行关闭了分页机制，这在xv6启动过程中会详细分析)，所以此代码中的所有指针，虽然是虚拟地址，但它们本质上也等于物理地址。如果你读得不仔细，可能领悟不到这一层的巧妙：)

1.6 kvminit函数

在理解了kvmmake函数的基础上，这个函数就非常简单了，它只是简单地调用了一下kvmmake函数，设置好内核地址空间之后，将返回的内核页表指针传递给了全局变量kernel_pagetable。

// Initialize the one kernel_pagetable
void
kvminit(void)
{
  kernel_pagetable = kvmmake();
}

1.7 kvminithart函数

正如在上一段中所说的，其实在调用kvmmake之前在start.c中关闭了分页机制。那么什么时候再次打开分页呢，就在这个函数kvminithart里了。

// Switch h/w page table register to the kernel's page table,
// and enable paging.
void
kvminithart()
{
  // 将kvminit得到的内核页表根目录地址放入SATP寄存器，相当于打开了分页
  w_satp(MAKE_SATP(kernel_pagetable));
  // 清除快表(TLB)
  sfence_vma();
}

函数非常简单，只有简单的两行，第一行是设置内核根页表寄存器的，一旦设置完毕之后相当于也打开了分页机制，自此之后虚拟地址就要经过MMU的翻译才可以转化为物理地址了，但是在内核态下因为大部分页面执行的还是直接映射，所以物理地址和虚拟地址本质上还是相等的(除了内核栈和trampoline页面)。MAKE_SATP是一个宏定义，定义如下：

// use riscv's sv39 page table scheme.
#define SATP_SV39 (8L << 60)
#define MAKE_SATP(pagetable) (SATP_SV39 | (((uint64)pagetable) >> 12))

要充分理解这段宏的概念，必须好好去阅读一下RISCV的SATP寄存器各字段含义，我已经截取了下来，如下图所示：
因为xv6基于RV64的体系结构，所以可以直接看下面的RV64寄存器字段。MODE表示使用的分页方案，xv6使用的是Sv39方案，所以应该将MODE域设置为8，这也就是宏SATP_SV39的含义，域ASID表示的是Address Space Identifier，地址空间标识符域。这个域用来加速上下文切换过程，是可选的，我们看到xv6没有使用这个域，而是直接将MODE和PPN做了或操作得到MAKE_SATP这个宏。

再看w_satp这个函数，它接收MAKR_SATP的返回结果(其实就是一个64位二进制数)作为参数。它的定义如下，调用了RISCV汇编来将x的值写入satp寄存器，如果你不理解C内嵌汇编的用法，可以去学习一下，这在内核开发中非常常见。下面的这条汇编可以作为一个小例子，我注释一下：

// supervisor address translation and protection;
// holds the address of the page table.
static inline void 
w_satp(uint64 x)
{
  // 格式[汇编代码模板:输出变量:输入变量:修改列表]
  // %0表示的是引用第一个变量，这里就是x，它被以寄存器的形式存放下来，写入satp
  asm volatile("csrw satp, %0" : : "r" (x));
}

最后再看一下sfence_vma这个函数，它的定义如下：

// flush the TLB.
static inline void
sfence_vma()
{
  // the zero, zero means flush all TLB entries.
  asm volatile("sfence.vma zero, zero");
}

从汇编中也可以看出，这行汇编代码的作用是完全刷新快表，因为我们重新设置了内核页表，所以之前的缓存必须全部清空，这非常合理。

哎呀，这篇文章好像写得太长了，如果还意犹未尽的话，请点击下方链接跳转到这个系列的下一篇，我已经按照顺序将它们编排好了，我会确保逻辑相关的博客之间都有相互跳转的超链接。

跳转到下一篇博客(如果没有链接表示还没有写完orz)