[xv6]:内存管理

3.1 Page Table

下图展示了RISC-V页表真正的细节，它采用的是多级页表的方案，一共有三级，整体上是一个树形的结构。这种树形结构的多级页表节省了大量内存空间

为了跟踪装载页表的页是否有效，引入页目录PD(Page Directory，即高两级的页表，xv6并没有严格区分页目录和页表)

页目录指出装载页表或下一级页目录的物理页帧的位置；或者告诉我们页表或下一级页目录的整个页不包含有效页，这时页目录的页目录项PDE（Page Directory Entry）也不存在/无效。

1.png

每级页表的大小都被设计为4KB，刚好能装进一页物理帧内, 前面提过，PTE用uint64类型来保存，因此一个PTE占用8B的空间，所以一个页表可以包含512个PTE

在每一级页表中，都取27位索引的其中9位来找到对应的PTE。通过查找前两级页表的PTE，可以访问新的物理页帧，在该物理页帧内保存着下一级的页表。当查找最后一级页表的PTE时，才将PPN和Offset结合，得到虚拟地址所映射的真正物理地址，然后再访问用户或内核需要的内容。

整个查找页表的过程一共要遍历三层，如果这三次查找有任意一次没有命中，即对应PTE不存在，这种异常的情况称为缺页错误Page-Fault

现在我们来看一些PTE的标志位Flags，这些标志位告诉页表硬件，关于用户进程提供的虚拟地址的一些权限信息，这将指示页表硬件怎么对待这次地址转换。

  • PTE_V指示PTE是否存在/有效。如果不存在，尝试引用该页时就会引发一个缺页错误异常。
  • PTE_R指示这一页物理帧是否能被读。
  • PTE_W指示这一页物理帧是否能被写。
  • PTE_X指示这一页物理帧是否能被CPU看待并转换成指令来执行。
  • PTE_U指示这一页物理帧在用户模式下是否能访问。如果没有置位，则该一页物理帧只能在监管者模式下被访问。

在xv6内核的启动阶段时，页表是被禁用的, 为了告诉RISC-V的分页硬件，现在可以使用页表了，内核必须将根页表的物理地址写入到satp寄存器中

每个CPU都有自己的satp寄存器, CPU在执行指令时，将使用自己的satp寄存器里指向的根页表，完成指令中虚拟地址的转换, 正因为每个CPU有自己的satp寄存器，因此不同CPU可以使用不同的页表

最后我们再弄清楚一些概念，物理内存通常指的是DRAM中的存储单元，物理内存中的每一字节都对应一个物理地址。而指令由始至终只使用虚拟地址，位于MMU的分页硬件负责，将CPU传来的虚拟地址转换为物理地址，然后将物理地址发送到DRAM以读取或写入数据

3.2 Kernel Address Space

除了为每个用户进程都维护一个页表，xv6为内核也单独维护了一个页表。下图展示了内核的虚拟地址空间如何映射到实际的物理地址空间中。

2.png

QEMU仿真的RAM，将从物理地址0x80000000（KERNBASE）开始，至少到0x86400000为止（PHYSTOP，在kernel/memlayout.h中定义其值为0x88000000，所以xv6的RAM实际大小为128M）

QEMU同样也仿真了一些I/O设备，这些设备接口通过内存映射的方式，将设备的控制寄存器映射到物理内存中，位于KERNBASE下

内核只要读出或写入这些特殊的物理地址，就能直接读写设备的控制寄存器，从而直接地与设备进行通信。

1
2
3
4
5
6
// the kernel expects there to be RAM
// for use by the kernel and user pages
// from physical address 0x80000000 to PHYSTOP.
#define KERNBASE 0x80000000L
#define PHYSTOP (KERNBASE + 128*1024*1024)
// 这里 PHYSTOP = 0x88000000L

值得提醒的是，在上图右半部分的物理内存视图中，只有从KERNBASE到PHYSTOP才对应真正的DRAM芯片

位于PHYSTOP上方，未使用的空间是没有DRAM芯片与之对应的，通过放置新的DRAM芯片，这部分空间可以被扩展并使用。而位于KERNBASE下方，访问相应的物理地址，实际上是直接访问相关I/O设备的控制寄存器，而不是访问DRAM芯片。

  • 直接映射

    在内核未启用页表的时候，访问RAM以及经过内存映射的设备控制寄存器时，内核的虚拟地址将采用直接映射的方式进行转换，即虚拟地址与实际物理地址相同。这种直接映射，也会在初始化内核页表的过程中（kernel/vm.c的kvminit），记录到内核页表中，即使内核开始使用页表，这种直接映射的布局也被保留了下来

内核的虚拟地址空间中，也有一些部分不仅仅使用直接映射。上图的左半部分展示了，除了直接映射之外，还有一些额外的布局与设置，它们位于内核虚拟地址空间的顶部，在初始化了内核页表，并且启用页表之后，就可以正式使用这些布局设置。

1
2
3
4
5
6
7
// map the trampoline page to the highest address,
// in both user and kernel space.
#define TRAMPOLINE (MAXVA - PGSIZE)

// map kernel stacks beneath the trampoline,
// each surrounded by invalid guard pages.
#define KSTACK(p) (TRAMPOLINE - ((p)+1)* 2*PGSIZE)

  • trampoline

    它被映射到虚拟地址空间的顶端，用户和内核的页表里都有这一项映射，摆放的位置相同，trampoline页被映射了两次，一次映射到虚拟地址空间的顶端，一次是直接映射（trampoline页位于RAM中）。

  • 内核栈

    每个进程都对应一个内核栈, 更准确地说，每个进程在用户空间执行指令时使用的是用户栈，而在内核空间下执行时（一般称为这个用户进程的内核线程）使用的是内核栈，xv6内核是C代码，自然需要内核栈来保存关于函数调用等信息

    内核栈是一页页地被分配的，从靠近PHYSTOP的位置开始往下分配。因此这些内核栈也在RAM当中，自然会被直接映射到内核的虚拟地址空间里。现在我们再一次将这些内核栈映射到内核虚拟地址空间的高地址部分，这样就可以自然地在它们之间插入一些保护页guard page。保护页的PTE_V是无效的，访问它会引发缺页错误的异常，从而陷入内核，这样的设计可以防止内核栈溢出

对于内核代码和trampoline页，标志位PTE_R和PTE_X被设置，因此内核可以从这些页中读取内容并且直接当作指令运行。其它的页则设置标志位PTE_R和PTE_W，作为常规页进行读写。

3.3 Code: Creating an Address Space

与xv6虚拟内存系统密切相关的代码位于kernel/vm.c中，下面我们来分析其中一部分代码。

核心的函数是walk()和mappages(), walk为给定的虚拟地址，找到其相应的PTE，如果PTE不存在则新分配一页使之有效，它模仿的是真实分页硬件查找页表的过程，可以看成是查找页表的软件实现，在内核或进程的页表未初始化时，内核就用它来转换相关虚拟地址mappages()为给定输入的映射建立PTE，更新页表

以kvm开头的函数对内核页表进行操作，以uvm开头的函数对用户页表进行操作，函数copyout和copyin完成内核空间和用户空间之间的数据复制…

在内核启动阶段，main()(kernel/main.c)将调用kvminit(), 创建内核页表, 整个工作流程如下:

  1. 分配新的一页物理帧用于装载内核的根页表
  2. 调用kvmmap()，在即将装载的内核页表上建立一系列的直接映射，包括I/O设备、内核代码和数据、内核空闲内存段等
  3. 再把trampoline映射到内核虚拟地址的最顶端，完成了内核页表的初始化

内核利用以下函数初始化内核页表时，能够正常工作，是建立在内核虚拟地址空间被直接映射到物理内存的前提下

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
extern char etext[];  // kernel.ld sets this to end of kernel code.
extern char trampoline[]; // trampoline.S

// create a direct-map page table for the kernel.
void
kvminit(
{
  // allocates a page of physical memory to hold the root page-table page. 
  kernel_pagetable = (pagetable_t) kalloc();
  memset(kernel_pagetable, 0, PGSIZE);

  // include the kernel’s instructions and data, physical memory up to PHYSTOP, 
  // and memory ranges which are actually devices.
  // install mappings into a page table for a range of virtual addresses
  // to a corresponding range of physical addresses

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

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

  // CLINT
  kvmmap(CLINT, CLINT, 0x10000, PTE_R | PTE_W);

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

  // 大小为kernel text(code)的大小
  // map kernel text executable and read-only.
  kvmmap(KERNBASE, KERNBASE, (uint64)etext-KERNBASE, PTE_R | PTE_X);

  // 从kernel text之后到PHYSTOP之前的区域都是kernel data和free memory
  // xv6 uses the physical memory between the end of the kernel and PHYSTOP for run-time allocation. 
  // map kernel data and the physical RAM we'll make use of.
  kvmmap((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.
  // TRAMPOLINE = MAXVA - PGSIZE
  // 从最大虚拟地址向下分配一页给trampoline
  kvmmap(TRAMPOLINE, (uint64)trampoline, PGSIZE, PTE_R | PTE_X);
}
  • 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(uint64 va, uint64 pa, uint64 sz, int perm)
{
  if(mappages(kernel_pagetable, va, sz, pa, perm) != 0)
    panic("kvmmap");
}
  • mappages(): 建立映射关系的va和pa、映射的范围大小、以及PTE的权限
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
// 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)
{
  // installs PTEs for new mappings 
  // this mapping is separately for each virtual address in the range, at page intervals
  uint64 a, last;
  pte_t *pte;

  a = PGROUNDDOWN(va);
  last = PGROUNDDOWN(va + size - 1);
  // 为va的起始和终止地址分别向下向上取页大小4096的整
  for(;;){
    // calls walk to find the address of the PTE for that address
    if((pte = walk(pagetable, a, 1)) == 0)
      // walk为虚拟地址a分配PTE失败
      return -1;
    if(*pte & PTE_V)
      // 该PTE已经被别的va映射，有效位有效
      panic("remap");
    // 将物理地址pa的PPN提取出来，加上标志位信息perm和有效位
    // 然后将该条目放到PTE中
    *pte = PA2PTE(pa) | perm | PTE_V;
    if(a == last)
      // 分到了足够页数就返回
      break;
    a += PGSIZE;
    pa += PGSIZE;
    // 已经分配了一页，虚拟地址的起始位置和物理地址起始位置都加一页
  }
  return 0;
}
  • walk(): 为输入的va找到其对应的最后一级页表的PTE
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
// 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)
{
  // walk函数为给定va找到其对应的PTE
  // returns the address of the PTE in the lowest layer in the tree
  if(va >= MAXVA)
    panic("walk");

  for(int level = 2; level > 0; level--) {
    pte_t *pte = &pagetable[PX(level, va)];
    // 根据当前level，对va进行移位和掩码操作，得到当前level页表中的对应PTE条目
    // level=2时，向右移出12+2*9=30位，经掩码后得到9位level=2页表的PTE编号
    // level=1时，向右移出12+9=21位，经掩码后得到9位level=1页表的PTE编号
    if(*pte & PTE_V) {
      // 判断有效位
      pagetable = (pagetable_t)PTE2PA(*pte);
      // 提取物理地址，对应一个页的首地址
      // 将最右10位标志位移出，补充12位全0的偏移位，原44位PPN保留，得到指向下一层页表的物理地址
      // level=2时，pagetable指向level=1的页表
      // level=1时，pagetable指向level=0的页表
    } else {
      // 对应PTE不存在，且alloc被置位，则为该PTE指向的下一层页表分配一页
      if(!alloc || (pagetable = (pde_t*)kalloc()) == 0)
        return 0;
      // 一切清0，新分配的下一级页表的所有PTE也都是无效的
      memset(pagetable, 0, PGSIZE);
      // 更新PTE，将56位物理地址右移12位去掉偏移位，移进10位标志位，同时将PTE_V置1
      *pte = PA2PTE(pagetable) | PTE_V;
    }
  }
  // 跳出while后，此时pagetable指向level=0的页表
  return &pagetable[PX(0, va)];
  // level=0，向右移出12位，经掩码后得到9位level=0页表的PTE编号
  // 返回va对应的level=0页表中的对应PTE
}

kvminit()调用完成后，内核页表被初始化完毕，接着main()就调用kvminithart()装载内核页表

  • kvminithart(): 装载内核页表
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()
{
  // install the kernel page table
  // writes the physical address of the root page-table page into the register satp
  // After this the CPU will translate addresses using the kernel page table
  w_satp(MAKE_SATP(kernel_pagetable));
  // flushes the current CPU’s TLB
  // 此外，在trampoline中，switches to a user page table before returning to user space，也会刷新TLB
  sfence_vma();
}

还是在内核空间下，main()马上就调用procinit，为每个用户进程分配一个内核栈，该内核栈将被映射到内核虚拟地址空间的高地址部分，位于trampoline下方,更新了所有内核栈的PTE之后，最后调用kvminithart()更新一次satp寄存器，分页硬件就能使用新的内核页表

  • procinit(): 分配用户内核栈, 更新内核页表
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
// initialize the proc table at boot time.
void
procinit(void)
{
  struct proc *p;
  initlock(&pid_lock, "nextpid");

  // 开始时p=proc，即p的地址是proc数组的最开始位置
  // 每次遍历p就指向下一个进程结构
  for(p = proc; p < &proc[NPROC]; p++) {
      initlock(&p->lock, "proc");
      // Allocate a page for a kernel stack, for each process
      // Map it high in memory at the va generated by KSTACK, followed by an invalid guard page.
      char *pa = kalloc();
      if(pa == 0)
        panic("kalloc");
      // 指针相减就是地址相减，获取当前进程p和proc数组最开始位置的偏移量
      // 比如第一次，从p-proc=0开始，KSTACK生成虚拟地址: TRAMPOLINE - 2*PGSIZE
      // 因此TRAMPOLINE的下面第一页是guard page，第二页是kstack，也就是va指向的位置
      // 后面也以此类推，被跳过而未被处理的guard page，PTE_V是无效的
      uint64 va = KSTACK((int) (p - proc));
      // adds the mapping PTEs to the kernel page table
      // 内核栈可读可写，但在用户态不可访问，也不能直接执行
      kvmmap(va, (uint64)pa, PGSIZE, PTE_R | PTE_W);
      p->kstack = va;
  }
  // 将更新后的内核页表重新写入到satp中
  kvminithart();
}

3.4 Physical Memory Allocation

内核在运行时会分配和释放很多物理内存，xv6将一部分的物理内存，从kernel data结束开始，到PHYSTOP为止，这一部分称为free memory，用于运行时的内存分配

每次分配和回收都以页为单位，一页大小4KB，通过一个空闲物理帧链表free-list，将空闲的物理帧串起来保存

页表、用户内存、内核栈、管道缓冲区等操作系统组件需要内存时，内核就从free list上摘下一页或者多页分配给它们

在回收已经分配出去的内存时，这些被回收的物理帧，内核将它们一页页地重新挂到free list上。

3.5 Code: Physical Memory Allocator

现在我们来看看内核的内存分配器，该模块位于kernel/kalloc.c中。分配器使用的数据结构很简单，如下所示，就是一个struct kmem，有一把保护free-list的自旋锁，每一页物理帧都通过struct run串在一起，struct run被保存在每个空闲物理页内部

  • 链表节点
1
2
3
4
5
6
7
8
struct run {
  struct run *next;
};

struct {
  struct spinlock lock;
  struct run *freelist;
} kmem;

在main()中调用**kinit()**来完成内存分配器的初始化

  • kinit()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
extern char end[]; // first address after kernel.
                   // defined by kernel.ld.

//initialize the allocator
void
kinit()
{
  // initializes the free list to hold every page between the end of the kernel and PHYSTOP
  // xv6 assumes that the machine has 128MB of RAM
  initlock(&kmem.lock, "kmem");
  // kernel data之后到PHYSTOP之前都可以用于分配
  // add memory to the free list via per-page calls to kfree
  freerange(end, (void*)PHYSTOP);
}
  • freerange(): 回收物理内存
1
2
3
4
5
6
7
8
9
void
freerange(void *pa_start, void *pa_end)
{
  char *p;
  p = (char*)PGROUNDUP((uint64)pa_start);
  //kfree是头插法
  for(; p + PGSIZE <= (char*)pa_end; p += PGSIZE)
    kfree(p);
}
  • kfree(): 回收一页物理帧
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// Free the page of physical memory pointed at by v,
// 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;

  if(((uint64)pa % PGSIZE) != 0 || (char*)pa < end || (uint64)pa >= PHYSTOP)
    panic("kfree");

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

  // casts pa to a pointer to struct run, which records the old start of the free list in r->next,
  // and sets the free list equal to r
  r = (struct run*)pa;

  acquire(&kmem.lock);
  r->next = kmem.freelist;
  kmem.freelist = r;
  release(&kmem.lock);
}
  • kalloc(): 分配一个物理页
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 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)
{
  // removes and returns the first element in the free list.
  // When a process asks xv6 for more user memory, xv6 first uses kalloc to allocate physical pages.
  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;
}

3.6 Process Address Space

前面我们已经讨论过内核的虚拟地址空间，现在我们来看用户进程的虚拟地址空间，每个用户进程都有自己的页表，因此也有不同的虚拟地址空间。

用户进程的虚拟地址空间同样从0开始，一直到MAXVA（2^38-1），这其中有多达256GB的空间。一个用户进程如果在运行时需要额外内存，就向内核内存分配器发出请求，让kalloc分配一些物理页，然后内核会更新用户进程的页表，设置新的PTE（此前提到的5个标志位都被设置）。进程中间那些未使用的虚拟地址，只需要在页表中将相关的PTE标记为无效即可

  • 为什么使用页表
  1. 用户进程现在都有自己的页表，在进程之间提供了隔离性
  2. 用户的虚拟地址空间是连续的，而对应的物理帧分布可以是不连续的
  3. 通过页表，内核可以将trampoline页映射到用户虚拟地址空间的顶端，所有进程都可以看到这一页。

用户进程虚拟地址空间的布局如下图所示

3.png

  • stack

    为了防止用户栈溢出，在栈的下面也放置了一页保护页。栈溢出时会访问到该保护页，从而出现缺页错误异常，用户进程因此陷入内核并等待处理，内核可能会终止掉该进程。而现在的操作系统在这种情况下，一般都会自动地为用户栈分配更多的空间

    值得注意的地方有两点：

    1. 内核虚拟地址空间中那些内核栈之间的保护页有所不同。这里的保护页是有实际的物理帧对应的，即内核确实为用户进程分配这一页（标志位为RWV，没有U）
    2. 在内核空间下，内核栈之间的保护页PTE_V无效，并没有实际分配物理页

  • text， data段

    xv6为了简单起见，将它们放在了同一页内，实际上现在的操作系统都会将它们放在不同的页内，这一点也可以通过在编译时指定-N选项来强制实现

Stack

Stack的大体结构如上图所示，下面给出其具体结构

4.png

上图是一个典型的运行时(Calling)栈, xv6中，一个stack只有一个page大小, 当进程进行嵌套调用(如函数A调用函数B)时， 每个被调用的函数都会产生一个栈帧(Stack Frame), 每一个栈帧由四个部分组成

  • 返回地址(fp)
  • 上一个栈帧的fp寄存器的值(fp - 8)
  • 保存的寄存器(Caller)
  • 局部变量

对于每一个栈帧来说，寄存器fp/s0指向其栈帧的首部, 即栈帧的最大地址，寄存器sp指向栈帧的尾部, 即栈帧的最小地址

通常情况下，当申请一个新的栈帧时，会将sp - 16(至少-8， 因为可能没有上一个栈帧)

3.7 Code: Sbrk

Sbrk是一个系统调用，用户进程调用它以增加或减少自己拥有的物理内存（proc->sz）

  • sys_sbrk()
1
2
3
4
5
6
7
8
9
10
11
12
13
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;
}
  • growproc(): 更改物理内存大小
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// Grow or shrink user memory by n bytes.
// Return 0 on success, -1 on failure.
// Sbrk is implemented by the function growproc
int
growproc(int n)
{
  uint sz;
  struct proc *p = myproc();

  sz = p->sz;
  // 是从sz接着分配内存给增长需要的
  // 也就是紧接着user text、user data、guard page和user stack之后
  // 从那个虚拟地址继续开始分配
  if(n > 0){
    if((sz = uvmalloc(p->pagetable, sz, sz + n)) == 0) {
      return -1;
    }
  } else if(n < 0){
    sz = uvmdealloc(p->pagetable, sz, sz + n);
  }
  p->sz = sz;
  return 0;
}
  • uvmalloc()

uvmalloc通过调用kalloc来分配物理内存，并调用mappages来更新页表，并设置PTE的5个标志位都置位。

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
// 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)
{
  char *mem;
  uint64 a;

  if(newsz < oldsz)
    return oldsz;

  oldsz = PGROUNDUP(oldsz);
  for(a = oldsz; a < newsz; a += PGSIZE){
    // allocates physical memory with kalloc, and adds PTEs to the user page table with mappages
    mem = kalloc();
    if(mem == 0){
      uvmdealloc(pagetable, a, oldsz);
      return 0;
    }
    memset(mem, 0, PGSIZE);
    if(mappages(pagetable, a, PGSIZE, (uint64)mem, PTE_W|PTE_X|PTE_R|PTE_U) != 0){
      kfree(mem);
      uvmdealloc(pagetable, a, oldsz);
      return 0;
    }
  }
  return newsz;
}
  • uvmdealloc()

uvmdealloc调用uvmunmap来回收已分配的物理内存

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// Deallocate user pages to bring the process size from oldsz to
// newsz.  oldsz and newsz need not be page-aligned, nor does newsz
// need to be less than oldsz.  oldsz can be larger than the actual
// process size.  Returns the new process size.
uint64
uvmdealloc(pagetable_t pagetable, uint64 oldsz, uint64 newsz)
{
  if(newsz >= oldsz)
    return oldsz;

  if(PGROUNDUP(newsz) < PGROUNDUP(oldsz)){
    int npages = (PGROUNDUP(oldsz) - PGROUNDUP(newsz)) / PGSIZE;
    // calls uvmunmap, 
    // which uses walk to find PTEs and kfree to free the physical memory they refer to.
    uvmunmap(pagetable, PGROUNDUP(newsz), npages, 1);
  }

  return newsz;
}

  • uvmunmap()

    uvmunmap使用walk()找到相应的PTE，并且调用kfree回收相应的物理帧

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

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

  for(a = va; a < va + npages*PGSIZE; a += PGSIZE){
    if((pte = walk(pagetable, a, 0)) == 0)
      panic("uvmunmap: walk");
    if((*pte & PTE_V) == 0)
      // examination of the user page table
      // xv6 uses a process’s page table as the only record
      // of which physical memory pages are allocated to that process
      panic("uvmunmap: not mapped");
    if(PTE_FLAGS(*pte) == PTE_V)
      panic("uvmunmap: not a leaf");
    if(do_free){
      uint64 pa = PTE2PA(*pte);
      kfree((void*)pa);
    }
    *pte = 0;
  }
}

3.8 Code: Exec

现在我们来看最后一段代码，系统调用exec的实现（kernel/exec.c）

系统调用exec将存储在文件系统上的，新的用户程序装载进内存里，然后执行它

int exec(char *path, char **argv)

  • 读取文件的ELF Header

exec通过路径名打开文件，然后读取该文件的ELF Header（kernel/elf.h）, xv6的所有应用程序以通用的ELF格式来描述，一个ELF二进制文件大概这样组成：一个ELF Header，后面紧跟一系列的Program Section Headers

每个Program Section Header都对应一段需要加载到内存中的程序，xv6的应用程序只有一个Program Section Header，而在其它操作系统上可能有好几个。

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
// File header
struct elfhdr {
  uint magic;  // must equal ELF_MAGIC
  uchar elf[12];
  ushort type;
  ushort machine;
  uint version;
  uint64 entry;
  uint64 phoff;
  uint64 shoff;
  uint flags;
  ushort ehsize;
  ushort phentsize;
  ushort phnum;
  ushort shentsize;
  ushort shnum;
  ushort shstrndx;
};

// Program section header
struct proghdr {
  uint32 type;
  uint32 flags;
  uint64 off;
  uint64 vaddr;
  uint64 paddr;
  uint64 filesz;
  uint64 memsz;
  uint64 align;
};

// Format of an ELF executable file
#define ELF_MAGIC 0x464C457FU  // "\x7FELF" in little endian

// Values for Proghdr type
#define ELF_PROG_LOAD           1

// Flag bits for Proghdr flags
#define ELF_PROG_FLAG_EXEC      1
#define ELF_PROG_FLAG_WRITE     2
#define ELF_PROG_FLAG_READ      4

exec读取了文件系统上的文件之后，第一件事就是先检查该文件是否包含ELF二进制文件。

1
2
3
4
5
6
7
8
// Check ELF header
// exec的第一步是检查文件是否包ELF二进制文件。
// ELF二进制文件是以4个“magic number”开头的，即0x7F，“E”，“L”，“F”，即宏定义ELF_MAGIC。
// 如果ELF头中包含正确的magic number，exec就认为该ELF二进制文件的结构是正确的。
if(readi(ip, 0, (uint64)&elf, 0, sizeof(elf)) != sizeof(elf))
  goto bad;
if(elf.magic != ELF_MAGIC)
  goto bad;

  • 创建用户页表

    exec为用户进程调用proc_pagetable()，通过uvmcreate()创建一个空的用户页表，接着只在该页表上添加了trampoline和trapframe的映射，其它的虚拟地址空间都暂时为空

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
//exec通过proc_pagetable分配了一个没有用户部分映射的页表
if((pagetable = proc_pagetable(p)) == 0)
  goto bad;


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

  return pagetable;
}

// create an empty user page table.
// returns 0 if out of memory.
pagetable_t
uvmcreate()
{
  pagetable_t pagetable;
  pagetable = (pagetable_t) kalloc();
  if(pagetable == 0)
    return 0;
  memset(pagetable, 0, PGSIZE);
  return pagetable;
}

  • 将程序由文件(磁盘)装载到内存

    exec()对于每个程序段，先是调用uvmalloc()分配足够的物理帧，更新了用户页表。然后调用loadseg()加载程序段到这些物理帧(DRAM)中

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
// 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;
  uint64 sz1;
  // 再通过uvmalloc为每个ELF段分配内存
  if((sz1 = uvmalloc(pagetable, sz, ph.vaddr + ph.memsz)) == 0)
    goto bad;
  sz = sz1;
  if(ph.vaddr % PGSIZE != 0)
    goto bad;
  // 然后通过loadseg把段的内容载入物理内存中
  // loadseg通过walkaddr找到写入ELF段的内存的物理地址；通过readi来将段的内容从文件中读出
  if(loadseg(pagetable, ph.vaddr, ip, ph.off, ph.filesz) < 0)
    goto bad;
}


// Load a program segment into pagetable at virtual address va.
// va must be page-aligned
// and the pages from va to va+sz must already be mapped.
// Returns 0 on success, -1 on failure.
static int
loadseg(pagetable_t pagetable, uint64 va, struct inode *ip, uint offset, uint sz)
{
  uint i, n;
  uint64 pa;

  if((va % PGSIZE) != 0)
    panic("loadseg: va must be page aligned");

  for(i = 0; i < sz; i += PGSIZE){
    pa = walkaddr(pagetable, va + i);
    if(pa == 0)
      panic("loadseg: address should exist");
    if(sz - i < PGSIZE)
      n = sz - i;
    else
      n = PGSIZE;
    // 将文件内容写入物理内存DRAM中
    if(readi(ip, 0, (uint64)pa, offset+i, n) != n)
      return -1;
  }
  
  return 0;
}


// Look up a virtual address, return the physical address,
// or 0 if not mapped.
// Can only be used to look up user pages.
uint64
walkaddr(pagetable_t pagetable, uint64 va)
{
  pte_t *pte;
  uint64 pa;

  if(va >= MAXVA)
    return 0;

  pte = walk(pagetable, va, 0);
  if(pte == 0)
    return 0;
  if((*pte & PTE_V) == 0)
    return 0;
  if((*pte & PTE_U) == 0)
    return 0;
  pa = PTE2PA(*pte);
  return pa;
}

  • 初始化用户栈

    exec()首先分配两页物理帧:

    • 第一页用作保护页，通过调用uvmclear()将PTE_U设为无效，这样在用户空间下不能访问它

    • 第二页留给用户栈，argc, argv 已经其他需要的寄存器推入用户栈内

    最后，exec()就清除进程的旧内存映像，即释放旧页表所占用的物理内存，并使用新的页表, 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
// 到这里，用户空间的text和data都已经加载完毕了
// Allocate two pages at the next page boundary.
// 紧接着data的位置向上继续分配两个页，第一页用作guard page，第二页用作user stack
// ustack中的前三项就是伪造的返回PC值，argc和argv指针
sz = PGROUNDUP(sz);
uint64 sz1;
if((sz1 = uvmalloc(pagetable, sz, sz + 2*PGSIZE)) == 0)
  goto bad;
sz = sz1;
// uvmclear将PTE_U设为无效，因此这一页用作保护页
uvmclear(pagetable, sz-2*PGSIZE); 
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;
  if(copyout(pagetable, sp, argv[argc], strlen(argv[argc]) + 1) < 0)
    // 保护页还让exec能够处理那些过于庞大的参数；当参数过于庞大时，
    // exec 用于将参数拷贝到栈上的函数copyout会发现目标页无法访问，并且返回-1
    goto bad;
  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.
// 现在的sp指向argv[]数组，argc通过a0寄存器i 返回
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;
// 注意，在用户进程被创建的时候，这里就将返回到main的pc值放到寄存器epc里面
p->trapframe->epc = elf.entry;  // initial program counter = main
p->trapframe->sp = sp; // initial stack pointer
proc_freepagetable(oldpagetable, oldsz);

// the C calling convention on RISC-V places return values in a0
return argc; // this ends up in a0, the first argument to main(argc, argv)
xv6

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！