标签：uint64 va return pte 内存 lab5 缺页 S081 MIT

MIT 6.S081入门lab5 懒分配

一、参考资料阅读与总结

1.xv6 book书籍阅读（ Chapter 4 Section 4.6)

4.6 Page-fault Exceptions

xv6对异常情况的处理：用户空间终止进程；内核空间停止内核执行。
缺页错误常常被用于写时复制方法，例如COW-fork。
缺页错误的类型：
Load Page Faults： 无法转换的虚拟地址位于一条加载（读）指令中。Scause：13；
Store Page Faults： 无法转换的虚拟地址位于一条存储（写）指令中。Scause：15；
Instruction Page Faults： 无法转换的虚拟地址位于一条执行指令中。Scause：12；
缺页错误类型码：scause寄存器；虚拟地址：stval寄存器
由于fork在子进程关闭/exec 后，其整份的内存拷贝其其实是多余的，但是直接粗暴的共享内存回导致父子进程的相互干扰，这时我们就需要利用缺页错误来实现灵活的共享内存。
fork改进思想： 开始时父子进程共享内存页，但是为只读模式 -> 尝试写入，出现缺页错误 -> 内核复制该页并进行映射 ->开放读写权限并更新进程页表 ->恢复指令运行；
懒惰分配Lazy Allocation实现： 用户调用sbrk请求内存 -> sbrk标记进程大小增长（不分配）-> 缺页错误 -> 分配物理内存并更新页表。
按需调页Demand Paging： 需要装载页进入内存，但是内存不足时，内核逐出evict物理页到磁盘并标记无效 -> 其他进程读取该页时，触发缺页异常，产生缺页错误 -> RAM中找到空间，从磁盘读入, 改写PTE为有效后更新页表 -> 重新执行读写指令。
其他功能：自动增长栈和内存映射文件等。

4.7 Real World

现实很多操作系统将内核的映射也加入用户页表，通过PTE标志位实现隔离机制；
能够提升效率，但是内核代码会相当复杂。

二、涉及函数

本次实验原始代码基本是lab3和lab2的代码，这里就不输出相关函数了，核心是设计

三、课程视频观看笔记

目标：使用缺页错误实现虚拟内存分配
虚拟内存的优势：隔离；一定程度的间接性（trampoline和guard page）；
目前的映射是动态的，利用缺页错误，可以将这种映射动态化；
内核需要响应缺页错误所需要的数据：
错误的虚拟地址（pte） -> stval寄存器；
缺页地址错误的类型(R、W、X) - >scause；
引起错误地址的指令地址 -> sepc；
缺页地址在sbark()中的应用（增加）：由于应用很难预测程序的大小，因此申请的内存往往是超出的
懒分配的实现：增加p->sz -> 缺页错误： va < p->sz 分配页面，初始化，映射 -> 重执行；
由于是lazy分配，因此在uvmunmap时候会报未分配错误，但是由于是使用-分配机制，实际上其pte就是没有分配的，继续就可以了。本质是修改了设计，将之前的不变量变为了变量。
按需补0： 对于全局变量而言，由于是0，因此只需要在单一页物理地址补0（只读），并将所需要的BSS中全部映射到这一页。在调用这些全局变量时，利用缺页错误进行重新申请分配。其本质是推迟花费；
注：缺页错误比单纯保存到内存开销更大，由于其要进入内核；
COW-fork：只有在父/子进程对页进行修改（R）时候，才对相应的物理页进行复制，并重新映射（修改页表）；内核可以使用pte的RSW标记只读的错误触发来源（fork）
在释放的时候要注意，读取物理页面的ref，当ref为0的时候才进行释放
按需调页： exec中，在读取内存时，只完成虚拟地址的分配，只有在触发页面错误时，才进行物理内存的分配，加载并重新映射pte；在页面错误时，把页面从文件读取到内存中，重新映射并运行原始内存；本质是对于内存的节省
扩展： 如果内存耗尽，逐出页面到文件系统中，进行重新分配，重启指令；
驱逐页面的策略：LRU：最近最久使用；先驱逐非脏页（没有修改的页（只读））；时钟算法实现了每隔一段时间重置内存（最近使用的时间段）；
mmap内存映射文件： 使用内存读写文件，通常是是急读写，mmap将文件内容从硬盘读取入内存，ummap取消映射操作，之后操作系统将其内容从内存写回到硬盘；通常是是使用vma结构体实现对读取要求的存储，在触发缺页错误时候进行操作；在现代操作系统中，可以使用文件锁来保证对文件访问的单一性
总结： pagetable +traps == 虚拟内存

四、完成lab及其代码

Eliminate allocation from sbrk

kernel/sysproc.c

..
uint64
sys_sbrk(void)
{
  int addr;
  int n;
  struct proc *p = myproc();

  if(argint(0, &n) < 0)
	return -1;
  addr = p->sz;
  if (n < 0) { //缩小直接消除
	uvmdealloc(p->pagetable, p->sz, p->sz + n);
  }
  p->sz += n;
  // if(growproc(n) < 0)
  //   return -1;
  return addr; //注意这里返回的一定是原始addr 因为新的addr还没有分配，只是sz增加了
}

Lazy allocation

kerenl/trap.c

...
void
usertrap(void)
{
  if(r_scause() == 8){
  ...
	} else if((which_dev = devintr()) != 0){
	// ok
  } else if(r_scause() ==  13 || r_scause() == 15) {
	printf("usertrap(): page fault trap: signal() %d at address %p\n", r_scause(), r_stval());
	if (vmlazyalloc(p, r_stval()) != 0) { //直接写成函数，放入vm.c中，更规范化
	  p->killed = 1;
	}
  } else {
  ...
  }
  ...
  }

kernel/def.h

// vm.c
int             vmlazyalloc(struct proc *, uint64);

kernel/vm.c

// 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");
	  continue; // 由于为动态分配，因此无需panic为其产生panic。
	if((*pte & PTE_V) == 0)
	  // panic("uvmunmap: not mapped");
	  continue; // 由于为动态分配，因此无需panic为其产生panic。
	if(PTE_FLAGS(*pte) == PTE_V)
	  panic("uvmunmap: not a leaf");
	if(do_free){
	  uint64 pa = PTE2PA(*pte);
	  kfree((void*)pa);
	}
	*pte = 0;
  }
}

..

// validate and potentially allocate physical page
// for a process's virtual address
// return 0 on OK, -1 if any error
int vmlazyalloc(struct proc *p, uint64 va) {
  uint64 ka = (uint64)kalloc(); //分配相应内存
  if (ka == 0) {
	printf("usertrap(): kalloc() failed, out of memory.\n");
	return -1;
	} else {
	memset((void *) ka, 0, PGSIZE); //清空内存
	if (mappages(p->pagetable, PGROUNDDOWN(va), PGSIZE, ka, PTE_W|PTE_X|PTE_R|PTE_U) != 0) { //给予相应的映射（内存pte）
	  printf("usertrap(): map pages failed\n");
	  kfree((void *)ka);
	  return -1;
	}
  }
  return 0;
  }

Lazytests and Usertests 修改代码，根据hint, 增加判断，并修改原始代码由于固定内存映射而导致的报错

kernel/vm.c

...
// 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 || (*pte & PTE_V) == 0) { //在遇到虚拟未分配的地址时进行分配
	if (vmlazyalloc(myproc(), va) != 0)
	  return 0;
  }
  if((*pte & PTE_V) == 0)
	return 0;
  if((*pte & PTE_U) == 0)
	return 0;
  pa = PTE2PA(*pte);
  return pa;
}
...
// Given a parent process's page table, copy
// its memory into a child's page table.
// Copies both the page table and the
// physical memory.
// returns 0 on success, -1 on failure.
// frees any allocated pages on failure.
int
uvmcopy(pagetable_t old, pagetable_t new, uint64 sz)
{
  pte_t *pte;
  uint64 pa, i;
  uint flags;
  char *mem;

  for(i = 0; i < sz; i += PGSIZE){
	if((pte = walk(old, i, 0)) == 0)
	  // panic("uvmcopy: pte should exist");
	  continue; //跳过动态内存分配的区块
	if((*pte & PTE_V) == 0)
	  // panic("uvmcopy: page not present");
	  continue; //跳过动态内存分配的区块
	pa = PTE2PA(*pte);
	flags = PTE_FLAGS(*pte);
	if((mem = kalloc()) == 0)
	  goto err;
	memmove(mem, (char*)pa, PGSIZE);
	if(mappages(new, i, PGSIZE, (uint64)mem, flags) != 0){
	  kfree(mem);
	  goto err;
	}
  }
  return 0;

/ validate and potentially allocate physical page
// for a process's virtual address
// return 0 on OK, -1 if any error
int vmlazyalloc(struct proc *p, uint64 va) {
  pte_t pte;

  if (va >= p->sz || va < p->trapframe->sp) { //超出范围 ,这里注意一定要等于，不然会报错，等于是可以接受的
	return -1;
  }
  uint64 ka = (uint64)kalloc();
  if (ka == 0) {
	printf("usertrap(): kalloc() failed, out of memory.\n");
	return -1;
	} else {
	memset((void *) ka, 0, PGSIZE);
	// vmprint(p->pagetable);
	if (mappages(p->pagetable, PGROUNDDOWN(va), PGSIZE, ka, PTE_W|PTE_X|PTE_R|PTE_U) != 0) {
	  printf("usertrap(): map pages failed\n");
	  kfree((void *)ka);
	  return -1;
	}
	// vmprint(p->pagetable);
  }
  return 0;
  }

kernel/sysproc.c

uint64
sys_sbrk(void)
{
  int addr;
  int n;
  struct proc *p = myproc();

  if(argint(0, &n) < 0)
	return -1;
  addr = p->sz;
  if (n < 0) {
	uvmdealloc(p->pagetable, p->sz, p->sz + n); //减少内存的时候进行立即减少
  }
  p->sz += n;
  // if(growproc(n) < 0)
  //   return -1;
  return addr;
}

kernel/syscall.c

// Retrieve an argument as a pointer.
// Doesn't check for legality, since
// copyin/copyout will do that.
int
argaddr(int n, uint64 *ip)
{
  *ip = argraw(n);
  struct proc *p = myproc();
  uint64 va = *ip, pa = walkaddr(p->pagetable, va);
  if (pa == 0) { //存在未被分配的区域
	if (vmlazyalloc(p, va) != 0) { //进行分配
	  p->killed = 1;
	}
  }
  return 0;
}

参考文献

2020版xv6手册：https://pdos.csail.mit.edu/6.S081/2020/xv6/book-riscv-rev1.pdf
xv6手册与代码笔记：https://zhuanlan.zhihu.com/p/351939252
xv6阅读笔记：https://ghostasky.github.io/2022/07/12/XV6/
xv6手册中文版：http://xv6.dgs.zone/tranlate_books/book-riscv-rev1/c4/s6.html
28天速通MIT 6.S081操作系统公开课：https://zhuanlan.zhihu.com/p/627573247
MIT6.s081操作系统笔记：https://juejin.cn/post/7013843036996108325
MIT 6.S081 操作系统 LAB5:Lazy allocation:https://www.cnblogs.com/traver/p/15749324.html
xv6 lab5 lazy page allocation：https://www.cnblogs.com/mlmz/p/16092443.html

标签：uint64,va,return,pte,内存,lab5,缺页,S081,MIT
From： https://www.cnblogs.com/David-Dong/p/18047065

MIT 6.S081入门lab5 懒惰分配