MIT 6.S081入门lab3 页表

一、参考资料阅读与总结

1.xv6 book书籍阅读（页表)

a. 总览

• 页表：操作系统为每一个进程提供私有空间和内存的机制，使每一个进程有着自己的虚拟地址空间。本质上是基于分页的内存空间管理方法。
• 页表存储：其实就是MMU，其存储了从虚拟地址VA到物理地址PA的映射。
• 页表作用：通过虚拟化，增强进程之间的隔离性，实现了物理内存的复用，内存在内核态的共享，保护页等

b.页式硬件

• 基址（重定位）-界限寄存器方式：本质使使用限制+偏移对内存进行虚拟化，但是其浪费了过多的物理内存，且不支持动态加载。
  

• 操作系统常用内存管理方法：

  • 分段： 将虚拟空间划分为不同的逻辑段（代码、堆、栈等），每个逻辑段维护一对基址—界限寄存器。
    问题：段大小不同，因此空间碎片化问题严重；对稀疏地址空间支持不好，其仍须完整加载。
    注：外部碎片：分配导致的非连续空闲空间的碎片；内部碎片：分配程序超出所需大小的碎片
  • 分页： 将虚拟内存切割为固定长度的分片——页（Page），同时将物理内存看作由与页大小相同的页帧（Page Frame）构成的阵列，通过MMU硬件完成对内存的映射（使用页表）
    问题：由于地址空间庞大，页表数量级大->使用分级页表降低开销；查找时间大幅增加->引入转换旁路缓冲存储器（TLB）进行缓存
    

• RISC-V硬件基础（简化）：

  • RISC-V指令是针对虚拟地址进行的操作，其可以处理64位虚拟地址，但物理地址为56位；
  • xv6运行在Sv39 RISC-V,即只有低39位addr被使用；
  • 使用页表条目（PTE）来保存虚拟地址到物理地址的 映射关系、其中虚拟地址低39位中的高27是用来对PTE进行索引的；
  • PTE由44bit的物理页帧号PPN和10bit的标志位组成，使用8B大小存储，即一个uint64；
  • 虚拟地址低39位中的低12位为页内偏移量Offset->4KB(4*2^10B)。
  • 转换过程： 有效低39位->其中的高27位取得PTE->44位PPN+10位权限检查->44位PPN+低12位Offset->56位物理地址

• RISC-V真实结构（三级页表）： 使用页目录PD+页目录项PDE，指出下一级页目录的物理帧的位置/是否存在有效页。
  

  • 页表大小的确定：8B(PTE)*512 = 4KB(一页物理帧[Offset])
  • 多级页表的核心：
    虚拟地址
    ->上级页表确定PPN(2^27 B)->
    下一级页表的起始位置(2^27 B)+虚拟地址中相应的索引给出这一级PTE的偏移(2^9 B)
    ->得到下一级的PTE(2^3B) ->......
    ->最后一级页表PPN(2^27 B)+Offset(2^12 B)
    ->物理地址
  • 缺页错误Page-Fault： 三次查找存在未命中，内核处理->调入页面、更新设置页表PTE、重启指令。
  • 为了节省时间开销，使用TLB进行缓存
    satp寄存器： 存放根页表在物理内存地址，每个CPU独有。
    标志为为权限信息，如V有效、R可读、W可写、X可执行、U用户访问等。

• 注意：指令只使用虚拟地址，通过MMU负责。虚拟内存（系统） = 由内核提供的，管理虚拟地址空间和物理内存的方法和机制。

c.内核地址空间

• 内核虚拟地址空间如何针对实际物理空间进行映射：
  
• xv6实际内存为从KERNBASE到PHYSTOP，KERNBASE以下为设备空间，PHYSTOP可以通过增加DRAM扩展
• 未启用页表时候，虚拟地址与实际物理地址相同；
• 启用页表后，虚拟地址空间存在着不止仅仅使用直接映射的部分：
  • 蹦床页面(trampoline page)，每个用户页表具有相同的映射；其一次映射到虚拟地址空间的顶端，一次是直接映射（trampoline页位于RAM中）
  • 内核栈：直接映射物理地址 + 虚拟地址高地址部分。目的：插入保护页（PTE没有设置），通过缺页异常防止内核栈溢出，同时节省物理内存。

d.代码：创建一个地址空间

• 核心代码：kernel/vm.c

  • 其中核心数据结构为pagetable_t，指向存放RISC-V根页表的那一页

    kernel/riscv.h:354

    typedef uint64 pte_t;
    typedef uint64 *pagetable_t; // 512 PTEs
    
    

  • 核心函数walk：给定虚拟地址找到相应的PTE -> 查找页表的软件形式。内核未初始化时，用来转换相关虚拟地址；

    kernel/vm.c:59 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_t *pte = &pagetable[PX(level, va)]; //获取页表地址
    	if(*pte & PTE_V) { 
    	  pagetable = (pagetable_t)PTE2PA(*pte); //检查有效性并跳转至下一层页表
    	} else {
    	//PTE不存在且需要分配
    	  if(!alloc || (pagetable = (pde_t*)kalloc()) == 0) //检查是否由空余
    		return 0;
    	  memset(pagetable, 0, PGSIZE); 
    	  *pte = PA2PTE(pagetable) | PTE_V; //分配新的页表界面并清0
    	}
      }
      return &pagetable[PX(0, va)]; //返回页表虚拟地址
    }
    

  • 核心函数mappages： 为给定输入的映射建立PTE并更新页表

    kernel/vm.c:144 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)
    {
      uint64 a, last;
      pte_t *pte;
    
      a = PGROUNDDOWN(va);
      last = PGROUNDDOWN(va + size - 1); //画出需要映射的页边界：上界和下界
      for(;;){
    	if((pte = walk(pagetable, a, 1)) == 0) //获取页表项PTE
    	  return -1;
    	if(*pte & PTE_V)
    	  panic("remap"); //判断是否被使用
    	*pte = PA2PTE(pa) | perm | PTE_V; //物理地址pa转换为页表项
    	if(a == last)
    	  break;//完成后跳出循环
    	a += PGSIZE;
    	pa += PGSIZE; 
      }
      return 0;
    }
    

  • 初始化函数kvminit： 被main调用，创建根页表，并使用kvmmap在内核页表上建立一系列映射，完成内核页表初始化

    kernel/vm.c:18 kvminit

    /*
     * create a direct-map page table for the kernel.
     */
    void
    kvminit()
    {
      kernel_pagetable = (pagetable_t) kalloc(); 
      memset(kernel_pagetable, 0, PGSIZE); //申请地址创建页表
    
      // 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);
    
      // map kernel text executable and read-only.
      kvmmap(KERNBASE, KERNBASE, (uint64)etext-KERNBASE, PTE_R | PTE_X);
    
      // map kernel data and the physical RAM we'll make use of. kernel data和free memory
      kvmmap((uint64)etext, (uint64)etext, PHYSTOP-(uint64)etext, PTE_R | PTE_W);
    
      // map the trampoline for trap entry/exit to
      // TRAMPOLINE = MAXVA - PGSIZE
      // the highest virtual address in the kernel.
      kvmmap(TRAMPOLINE, (uint64)trampoline, PGSIZE, PTE_R | PTE_X);
    }
    

    kernel/vm.c:114 kvmmap

    // 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) //调用mappages创建映射项
    	panic("kvmmap");
    }
    

• 内核页表装载：使用kvminithart函数将内核页表写入satp寄存器中

  kernel/vm.c:50 kvminithart

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

• 代码工作前提：未初始化页表时内核虚拟地址直接映射入物理内存，即kalloc()

• 进程与页表的交互： procinit 初始化进程并分配页表

  kernel/proc.c:26 procinit

  // 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)); //获取偏移量，并使用KSTACK获取虚拟地址（2*PGSIZE），一页隔离一页kstack
  	  kvmmap(va, (uint64)pa, PGSIZE, PTE_R | PTE_W);
  	  p->kstack = va;
    }
    kvminithart(); 更新satp
  }
  

• 刷新TLB： 使用sfence.vma()指令刷新TLB，同时其也再被trampoline.S使用，用于切换用户和内核态。

f.物理内存分配

xv6下的内存管理机制： 从kernel data到PHYSTOP作为free memory，用于运行内存分配；其以页为单位(4KB)，通过一个空闲物理帧链表free-list实现。

g.代码：物理内存分配

• 核心代码：内存分配器kernel/kalloc.c

  • 核心数据结构kmem，自旋锁+链表：

    kernel/kalloc.c:17 struct run 和 kmem

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

  • 核心函数kalloc：分配空闲物理帧，直接 取free-list第一页

    kernel/kalloc.c:65 struct kalloc

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

  • 核心函数kfree： 回收物理帧，将其内容置为1(垃圾数据)，同时转换指针类型，将空闲内存插入free-list中

    kernel/kalloc.c:47 kfree

    // 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); //输入垃圾数据
    
      r = (struct run*)pa; //转换指针类型
    
      acquire(&kmem.lock);
      r->next = kmem.freelist;
      kmem.freelist = r; //从头挂入free-list
      release(&kmem.lock);
    }
    

  • 核心函数freerange： 对其地址，同时通过调用free批量回收物理帧

    kernel/kalloc.c:33 freerange

    void
    freerange(void *pa_start, void *pa_end)
    {
      char *p;
      p = (char*)PGROUNDUP((uint64)pa_start);
      for(; p + PGSIZE <= (char*)pa_end; p += PGSIZE)
    	kfree(p);
    }
    
    

  • 初始化函数kinit： 启动自旋锁，并给出起始和终止地址，之后调用freerange

    kernel/kalloc.c:27 kinit

      ```
      extern char end[]; // first address after kernel.
      // defined by kernel.ld.
    
      void
      kinit()
      {
      initlock(&kmem.lock, "kmem");
      freerange(end, (void*)PHYSTOP);
      }
      ```
    

• 注意： 由于freerange按物理地址从小到大调用kfree，kfree又为头插法，因此分配时从大地址开始分配。

h.进程地址空间

• 用户空间理论大小： 0-MAXVA（2^38-1），256GB。
• 用户空间内存管理：向分配器发出请求，使用kalloc分配物理地址，并设置新的PTE。
• 页表的优点：
  • 隔离性： 用户进程有着自己的页表；
  • 连续性： 用户虚拟地址是连续的，物理帧可以不连续；
  • 用户内核态跳转： trampoline可以被映射到用户虚拟空间顶端。
• 具体细节：
  
• 用户栈包括了命令行参数字符串、命令行指针数组、从调用main的返回的其他参数
• 防止用户栈溢出，栈底存在保护页，触发缺页错误异常（现代操作系统会扩充栈）。和内核保护不同，其有实际物理帧对应

I.代码:sbrk

• sbrk系统调用:用户进程调用它以增加或减少自己拥有的物理内存

• 调用过程
  sys_sbrk -> growproc ->uvmalloc/uvmdealloc
  uvmalloc：kalloc分配内存、mappages添加入页表
  uvmdealloc：页面对齐，调用uvmunmap -> walk查找PTE、kfree释放内存

  kernel/sysproc.c:41 sys_sbrk

  uint64
  sys_sbrk(void)
  {
    int addr;
    int n;
  
    if(argint(0, &n) < 0)
  	return -1;
    addr = myproc()->sz;
    if(growproc(n) < 0) //调用growproc
  	return -1;
    return addr;
  }
  

  kernel/proc.c:239 growproc

  // 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;
    if(n > 0){ //增加内存占用，调用uvmalloc
  	if((sz = uvmalloc(p->pagetable, sz, sz + n)) == 0) {
  	  return -1;
  	}
    } else if(n < 0){ //减少内存占用，调用uvmdealloc
  	sz = uvmdealloc(p->pagetable, sz, sz + n);
    }
    p->sz = sz;
    return 0;
  }
  

  kernel/vm.c:229 uvmalloc

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

  kernel/vm.c:254 uvmdealloc

  // 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; //页表对齐
  	uvmunmap(pagetable, PGROUNDUP(newsz), npages, 1); //调用uvmunmap
    }
  
    return newsz;
  }
  

  kernel/vm.c:174 uvmunmap

  // 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) //寻找PTE
  	  panic("uvmunmap: walk");
  	if((*pte & PTE_V) == 0)
  	  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;
    }
  }
  

J.代码exec

• exec：将存储在文件系统上的，新的用户程序装载入内存并执行

• 代码调用路径：
  

  mermaid源代码

  graph TD
  	A[开始] --> B[读取文件 namei]
  	B -->|不存在| Z[返回-1]
  	B --> C[锁定inode ilock]
  	C --> D[检查ELF头是否有效 大小和ELF_MAGIC]
  	D -->|无效| Z
  	D --> E[创建空的用户页表 proc_pagetable]
  	E --> F[分配物理帧，更新页表 uvmalloc]
  	F --> G[加载程序段到内存 loadseg]
  	G --> H[解锁inode并结束文件操作、完成text和data的加载]
  	H --> I[准备用户栈:uvmalloc分配、uvmclear设置权限]
  	I --> J[推入参数和agrv指针]
  	J --> K[将程序参数入栈ustack（包括argc, argv等）]
  	K --> L[切换用户进程镜像（释放旧页表，替换为新页表）]
  	L --> M[返回参数个数（作为main的第一个参数）]
  	M --> N[结束]
  	K --> |无法切换|Z
  	I --> |用户栈申请失败|Z
  	E --> |创建页表失败|Z
  

• 注：ELF文件由4部分组成，分别是ELF头（ELF header）、程序头表（Program header table）、节（Section）和节头表（Section header table）。其定义在kernel/elf.h

• proc_pagetable： 使用uvmcreate创建空的用户页表，添加trampoline和trapframe映射；

• uvmcreate：使用kalloc()申请内存，并使用memset清理内存空间；

• loadseg： 检查页面大小是否完整，并调用walkaddr查找物理地址，使用readi加载程序进入物理地址；

• walkaddr： 使用walk查找PTE，将PTE转换为物理地址PE；

• uvmalloc： 见sbrk调用；

• **uvmclear：*找到相应pte并清除用户态可用表示。

  kernel/elf.h

  // Format of an ELF executable file
  
  #define ELF_MAGIC 0x464C457FU  // "\x7FELF" in little endian
  
  // 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;
  };
  
  // 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
  

  kernel/exec.c:12 exec

  int
  exec(char *path, char **argv)
  {
    char *s, *last;
    int i, off;
    uint64 argc, sz = 0, sp, ustack[MAXARG+1], stackbase;
    struct elfhdr elf;
    struct inode *ip;
    struct proghdr ph;
    pagetable_t pagetable = 0, oldpagetable;
    struct proc *p = myproc();
  
    begin_op();
  
    if((ip = namei(path)) == 0){ //使用namei打开二进制地址
  	end_op();
  	return -1;
    }
    ilock(ip); //锁定inode
  
    // Check ELF header
    if(readi(ip, 0, (uint64)&elf, 0, sizeof(elf)) != sizeof(elf)) //读取elf头
  	goto bad;
    if(elf.magic != ELF_MAGIC)
  	goto bad;
  
    if((pagetable = proc_pagetable(p)) == 0) //创建页表
  	goto bad;
  
    // 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;
  	if((sz1 = uvmalloc(pagetable, sz, ph.vaddr + ph.memsz)) == 0) //使用uvmalloc给每一个ELF分配内存
  	  goto bad;
  	sz = sz1;
  	if(ph.vaddr % PGSIZE != 0)
  	  goto bad;
  	if(loadseg(pagetable, ph.vaddr, ip, ph.off, ph.filesz) < 0) //使用loadseg载入物理内存
  	  goto bad;
    }
    iunlockput(ip);
    end_op();
    ip = 0;
  
    p = myproc();
    uint64 oldsz = p->sz; //获取当下程序的栈
  
    // Allocate two pages at the next page boundary.
    // Use the second as the user stack.
    sz = PGROUNDUP(sz);
    uint64 sz1;
    if((sz1 = uvmalloc(pagetable, sz, sz + 2*PGSIZE)) == 0) //uvmalloc申请栈空间
  	goto bad;
    sz = sz1;
    uvmclear(pagetable, sz-2*PGSIZE); //设置第一页为内核独享
    sp = sz;
      = 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) //将参数推入用户栈内
  	  goto bad;
  	ustack[argc] = sp; //设置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) //将argv[]指针推入用户栈内
  	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; //返回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 //初始化进程指针pc、sp等
    proc_freepagetable(oldpagetable, oldsz); //释放原始进程
  
    return argc; // this ends up in a0, the first argument to main(argc, argv) 返回a0 argc
  
   bad:
    if(pagetable)
  	proc_freepagetable(pagetable, sz);
    if(ip){
  	iunlockput(ip);
  	end_op();
    }
    return -1;
  }
  

  kernel/proc.c:155 proc_pagetable

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

  kernel/vm.c:197 uvmcreate

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

  kernel/exec.c:131 loadseg

  // 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) //loadseg
  {
    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;
  	if(readi(ip, 0, (uint64)pa, offset+i, n) != n)
  	  return -1;
    }
  
    return 0;
  }
  
  

  kernel/vm.c:91 walkaddr

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

  kernel/vm.c:338 uvmclear

  // mark a PTE invalid for user access.
  // used by exec for the user stack guard page.
  void
  uvmclear(pagetable_t pagetable, uint64 va)
  {
    pte_t *pte;
  
    pte = walk(pagetable, va, 0);
    if(pte == 0)
  	panic("uvmclear");
    *pte &= ~PTE_U;
  }
  

k.总结、xv6与真实操作系统的差异

• 内存分配核心： 有效使用有限的内存并为未知请求作好准备；
• 真实的内存映射： 利用页表将任意的硬件物理内存布局转换为可预测的内核虚拟地址布局；
• 真实的内存分配：对小对象提供内存分配，并提供不同的分页粒度；
• RISC-V特性：支持i物理地址级别保护，但是xv6未使用。

二、涉及文件

• kernel/memlayout.h： 定义RISC-V下物理内存布局

  kernel/memlayout.h

  // 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
  
  // local interrupt controller, which contains the timer.
  #define CLINT 0x2000000L
  #define CLINT_MTIMECMP(hartid) (CLINT + 0x4000 + 8*(hartid))
  #define CLINT_MTIME (CLINT + 0xBFF8) // cycles since boot.
  
  // qemu puts programmable interrupt controller here.
  #define PLIC 0x0c000000L
  #define PLIC_PRIORITY (PLIC + 0x0)
  #define PLIC_PENDING (PLIC + 0x1000)
  #define PLIC_MENABLE(hart) (PLIC + 0x2000 + (hart)*0x100)
  #define PLIC_SENABLE(hart) (PLIC + 0x2080 + (hart)*0x100)
  #define PLIC_MPRIORITY(hart) (PLIC + 0x200000 + (hart)*0x2000)
  #define PLIC_SPRIORITY(hart) (PLIC + 0x201000 + (hart)*0x2000)
  #define PLIC_MCLAIM(hart) (PLIC + 0x200004 + (hart)*0x2000)
  #define PLIC_SCLAIM(hart) (PLIC + 0x201004 + (hart)*0x2000)
  
  // 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) //内存大小
  
  // 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)
  
  // User memory layout.
  // Address zero first:
  //   text
  //   original data and bss
  //   fixed-size stack
  //   expandable heap
  //   ...
  //   TRAPFRAME (p->trapframe, used by the trampoline)
  //   TRAMPOLINE (the same page as in the kernel)
  #define TRAPFRAME (TRAMPOLINE - PGSIZE)
  
  

• kernel/vm.c： 虚拟化相关代码

  kernel/vm.c函数表

  函数名称	函数作用	参数和返回值
  kvminit	创建内核的直接映射页表	无参数; 无返回值
  kvminithart	切换到内核页表并启用分页	无参数; 无返回值
  walk	根据虚拟地址在页表中查找或创建页表项	pagetable_t pagetable, uint64 va, int alloc; 返回 pte_t*
  walkaddr	查找虚拟地址对应的物理地址	pagetable_t pagetable, uint64 va; 返回 uint64
  kvmmap	在内核页表中添加映射	uint64 va, uint64 pa, uint64 sz, int perm; 返回 void
  kvmpa	将内核虚拟地址转换为物理地址	uint64 va; 返回 uint64
  mappages	创建虚拟地址到物理地址的映射	pagetable_t pagetable, uint64 va, uint64 size, uint64 pa, int perm; 返回 int
  uvmunmap	移除一系列页表映射	pagetable_t pagetable, uint64 va, uint64 npages, int do_free; 返回 void
  uvmcreate	创建一个空的用户页表	无参数; 返回 pagetable_t
  uvminit	在用户页表中加载初始化代码	pagetable_t pagetable, uchar *src, uint sz; 返回 void
  uvmalloc	为进程分配内存	pagetable_t pagetable, uint64 oldsz, uint64 newsz; 返回 uint64
  uvmdealloc	释放进程的内存	pagetable_t pagetable, uint64 oldsz, uint64 newsz; 返回 uint64
  freewalk	递归地释放页表页面	pagetable_t pagetable; 返回 void
  uvmfree	释放用户内存页和页表	pagetable_t pagetable, uint64 sz; 返回 void
  uvmcopy	将一个进程的内存复制到另一个进程	pagetable_t old, pagetable_t new, uint64 sz; 返回 int
  uvmclear	清除用户访问的PTE标记	pagetable_t pagetable, uint64 va; 返回 void
  copyout	从内核复制数据到用户空间	pagetable_t pagetable, uint64 dstva, char *src, uint64 len; 返回 int
  copyin	从用户空间复制数据到内核	pagetable_t pagetable, char *dst, uint64 srcva, uint64 len; 返回 int
  copyinstr	从用户空间复制字符串到内核	pagetable_t pagetable, char *dst, uint64 srcva, uint64 max; 返回 int

• kernel/kalloc.c 内存划分的代码，上文已经分析完成

• kernel/riscv.h 使用内联汇编实现了相应的寄存器操作

  riscv.h的内联汇编函数作用表格

  函数名称	函数作用
  r_mhartid	返回当前 hart（核）的 ID
  r_mstatus	读取机器状态寄存器 (MSTATUS)
  w_mstatus	写入机器状态寄存器 (MSTATUS)
  w_mepc	设置机器异常程序计数器 (MEPC)
  r_sstatus	读取监督状态寄存器 (SSTATUS)
  w_sstatus	写入监督状态寄存器 (SSTATUS)
  r_sip	读取监督中断挂起寄存器 (SIP)
  w_sip	写入监督中断挂起寄存器 (SIP)
  r_sie	读取监督中断使能寄存器 (SIE)
  w_sie	写入监督中断使能寄存器 (SIE)
  r_mie	读取机器中断使能寄存器 (MIE)
  w_mie	写入机器中断使能寄存器 (MIE)
  w_sepc	设置监督异常程序计数器 (SEPC)
  r_sepc	读取监督异常程序计数器 (SEPC)
  r_medeleg	读取机器异常委托寄存器 (MEDELEG)
  w_medeleg	写入机器异常委托寄存器 (MEDELEG)
  r_mideleg	读取机器中断委托寄存器 (MIDELEG)
  w_mideleg	写入机器中断委托寄存器 (MIDELEG)
  w_stvec	设置监督陷阱向量基地址寄存器 (STVEC)
  r_stvec	读取监督陷阱向量基地址寄存器 (STVEC)
  w_mtvec	设置机器模式陷阱向量基地址寄存器 (MTVEC)
  w_satp	设置监督地址转换和保护寄存器 (SATP)
  r_satp	读取监督地址转换和保护寄存器 (SATP)
  w_sscratch	设置监督暂存寄存器 (SSCRATCH)
  w_mscratch	设置机器暂存寄存器 (MSCRATCH)
  r_scause	读取监督陷阱原因寄存器 (SCAUSE)
  r_stval	读取监督陷阱值寄存器 (STVAL)
  w_mcounteren	设置机器计数器使能寄存器 (MCOUNTEREN)
  r_mcounteren	读取机器计数器使能寄存器 (MCOUNTEREN)
  r_time	读取机器模式周期计数器
  intr_on	开启设备中断
  intr_off	关闭设备中断
  intr_get	获取设备中断的状态
  r_sp	读取堆栈指针寄存器 (SP)
  r_tp	读取线程指针寄存器 (TP)
  w_tp	写入线程指针寄存器 (TP)
  r_ra	读取返回地址寄存器 (RA)
  sfence_vma	清除 TLB 缓存

• kernel/exec.c 上文针对exec已经分析了

三、课程视频观看笔记

• 地址空间：
  • 地址空间的目标：内存隔离，即每个进程运行在属于自己的、独立的地址空间。->复用硬件地址空间
• 页式硬件（RISC-V）
  • 页表是硬件支持的：cpu 传递虚拟地址(va)给mmu，mmu将va转化为物理地址(pa)送入内存；
  • mmu只做转换，其页表存在内存中；
  • satp寄存器指向映射页表的指针，内核更新satp。注意 satp为物理地址；
  • index为页面地址、Offset为页内偏移；
  • 如果使用单级页表，如果虚拟内存小于物理内存，会出现虚拟内存占满而物理内存没有的情况；
  • 多级数的核心是实现页表的稀疏存储；
  • 为了降低三级页表锁带来的多次访问，使用TLB进行缓存。每次切换页表时需要刷新TLB；
  • CPU缓存中，地址为虚拟地址的在mmu之前，为物理地址的在mmu之后；
  • 页表提供了一种间接性，由于操作系统能够控制页表转换，其能处理页表错误等一系列问题。
• VMcode + layout
  • 物理空间分为两部分，DRAM和其他IO接口（包括网卡、UART、ROM等）
  • xv6使用的是恒等映射，同时由于映射是由操作系统控制的，其映射可以实现对物理地址的一对一、多对一、一对零等任意映射。
  • 权限是通过页表的权限进行管理的
  • 在xv6中每个进程都存在独立的内核页表
  • 由于是恒等映射，因此从虚拟地址到物理地址的启用会更加方便；同时，如果页表出现问题，会出现内核错误。

四、完成lab及其代码

• Print a page table
  声明及其调用：

  defs.h

  // vm.c
  ...
  void             vmprint(pagetable_t pagetable);
  ...
  

  exec.h

  // vm.c
  ...
    proc_freepagetable(oldpagetable, oldsz);
  vmprint(p->pagetable); //加入打印
  return argc; // this ends up in a0, the first argument to main(argc, argv)
  ...
  

  主函数打印实现，参考freewalk实现
  vm.c

  //Utility func to print the vaild
  //PTEs within a apage table recursively
  void
  pgtblprint(pagetable_t pagetable, int depth)
  {
    static char *indent[] = {
  	  "..",
  	  ".. ..",
  	  ".. .. .."
    };
  
    // 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){ // if table is effective
  	  printf("%s%d: pte %p pa %p\n", indent[depth], i, pte, PTE2PA(pte));
  	  if((pte & (PTE_R|PTE_W|PTE_X)) == 0){
  	  // this PTE points to a lower-level page table.
  	  uint64 child = PTE2PA(pte);
  	  pgtblprint((pagetable_t)child, depth + 1);
  	  } 
  	}
    }
  }
  
  
  void             
  vmprint(pagetable_t pagetable)
  {
    printf("page table %p\n", pagetable);
    pgtblprint(pagetable, 0);
  }
  

• A kernel page table per process
  调了半天没有调试出来，后面再跳把 sbark测试半天通不过

参考文献

2020版xv6手册：https://pdos.csail.mit.edu/6.S081/2020/xv6/book-riscv-rev1.pdf
xv6手册与代码笔记：https://zhuanlan.zhihu.com/p/351646541
xv6阅读笔记：https://ghostasky.github.io/2022/07/12/XV6/
xv6手册中文版：http://xv6.dgs.zone/tranlate_books/book-riscv-rev1/c1/s3.html
28天速通MIT 6.S081操作系统公开课：https://zhuanlan.zhihu.com/p/625962093
MIT6.s081操作系统笔记：https://juejin.cn/post/7008487319976017928