操作系统MIT6.S081：Lab5-＞Lazy allocation

操作系统MIT6.S081：Lab5-＞Lazy allocation
本系列文章为MIT6.S081的学习笔记，包含了参考手册、课程、实验三部分的内容，前面的系列文章链接如下
操作系统MIT6.S081：[xv6参考手册第1章]-＞操作系统接口
 操作系统MIT6.S081：[xv6参考手册第2章]-＞操作系统组织结构
 操作系统MIT6.S081：[xv6参考手册第3章]-＞页表
 操作系统MIT6.S081：[xv6参考手册第4章]-＞Trap与系统调用
 操作系统MIT6.S081：P1-＞Introduction and examples
操作系统MIT6.S081：P2-＞OS organization and system calls
操作系统MIT6.S081：P3-＞Page tables
操作系统MIT6.S081：P4-＞RISC-V calling conventions and stack frames
操作系统MIT6.S081：P5-＞Isolation & system call entry/exit
操作系统MIT6.S081：P6-＞Page faults
操作系统MIT6.S081：Lab1-＞Unix utilities
操作系统MIT6.S081：Lab2-＞System calls
操作系统MIT6.S081：Lab3-＞Page tables
操作系统MIT6.S081：Lab4-＞Trap
文章目录
前言
- 利用用户空间堆内存的lazy allocation，O/S可以与页表硬件一起实现许多巧妙的技巧。
- xv6应用程序使用sbrk()系统调用向内核请求堆内存。在我们为你提供的内核中，sbrk()分配物理内存并将其映射到进程的虚拟地址空间。
- 内核分配和映射大块内存可能需要很长时间。例如，1GB由262144个4096Bytes的页面组成。即使每个page的消耗不大，但是如此大量的page会占用极大的资源。
- 此外，一些程序分配的内存比实际使用的多(例如为了实现稀疏数组)，或者在使用之前就分配内存。
- 为了让sbrk()在这些情况下更快地执行，功能复杂的内核会延迟分配用户内存。也就是说，sbrk()不立即分配物理内存，而只是记住分配了哪些用户地址，并在用户页表中将这些地址标记为无效。
- 当进程第一次尝试使用任何给定的延迟分配内存页面时，CPU会产生一个page fault，内核通过分配物理内存、置零、映射它来处理该page fault。
- 你将在本实验中将此lazy acclocation功能添加到xv6。
在开始实验之前，请阅读xv6参考手册的第4章(特别是4.6节)以及你可能修改的相关源文件：
kernel/trap.c
kernel/vm.c
kernel/sysproc.c
开始实验之前，切换至lazy分支：

一、Eliminate allocation from sbrk()

1.1 实验描述

实验目的

你的第一个任务是将sbrk(n)系统调用的页面分配功能删除，sysproc.c中的sys_sbrk()函数就是该系统调用的具体实现。sbrk(n)将进程的内存大小增加n个字节，然后返回新分配区域的开始。你的新sbrk(n)应该只是将进程的大小(myproc()->sz)增加n并返回原来的size，它不应该分配内存，所以你应该删除对growproc()的调用(但你仍然需要增加进程的size)。

测试条件

----尝试猜测这种修改的结果是什么：会破坏什么？
----进行此修改，运行xv6，然后在shell中输入echo hi。你应该看到如下内容：

----usertrap(): ...代表消息来自trap.c中的用户trap处理程序，它捕获了一个它不知道如何处理的异常。我们需要知道为什么会发生此页面错误。
----stval=0x0..04008代表导致缺页的虚拟地址为0x4008。

1.2 实验思路

课程视频中已经演示过了，修改kernel/sysproc.c中的sys_sbrk()函数，将原本调用的growproc()函数注释掉，然后让myproc()->sz增加n。
```
uint64
sys_sbrk(void)
{
  int addr;
  int n;
  if(argint(0, &n) < 0)
    return -1;
  addr = myproc()->sz;
  /* 以前的，注释掉
  if(growproc(n) < 0)
    return -1;
  */
  //下面这行我们添加的
  myproc()->sz += n;
  
  return addr;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
```
1.3 实验结果

测试

运行xv6，执行echo hi，结果如下

 二、Lazy allocation

2.1 实验描述

实验目的

修改trap.c中的代码，通过将新分配的物理内存页映射到故障地址来响应用户空间的page fault，然后返回用户空间让进程继续执行。你应该在产生usertrap(): ...消息的printf调用之前添加代码，同时修改xv6相关内核代码以使echo hi工作。

实验提示

①你可以通过查看usertrap()中的r_scause()是13还是15来检查该错误是否是page fault。
②r_stval()返回RISC-V stval寄存器，其中包含导致page fault的虚拟地址。
③sbrk()会通过growproc()调用vm.c中的uvmalloc()。你可以参考uvmalloc()的代码，并需要调用kalloc()和mappages()。
④使用PGROUNDDOWN(va)将错误的虚拟地址向下舍入到页面边界。
⑤uvmunmap()会触发panic。如果某些页面未映射，请修改它以避免panic。
⑥如果内核崩溃，在kernel/kernel.asm中查找sepc。
⑦使用前面pgtbl实验的vmprint函数打印页表的内容。
⑧如果你看到错误incomplete type proc，请包含spinlock.h，然后包含proc.h。
注：如果一切顺利，你的lazy allocation代码应该会使得echo hi正常工作。你应该至少得到一个page fault，也许会有两个。

2.2 实验思路

参照实验提示的步骤一步一步来完成实验：

1、根据实验提示①，在kernel/trap.c中的usertrap()函数中添加对r_scause()为13或15情况的判断和处理。
```
if(r_scause() == 8){
  if(p->killed)
    exit(-1);
  p->trapframe->epc += 4;
  intr_on();
  syscall();
} 
//添加r_scause = 13和15的情况
else if(r_scause() == 13 || r_scause() == 15){
//结束添加
} else if((which_dev = devintr()) != 0){
} else {
  printf("usertrap(): unexpected scause %p pid=%d\n", r_scause(), p->pid);
  printf("            sepc=%p stval=%p\n", r_sepc(), r_stval());
  p->killed = 1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
```
2、根据实验提示②，通过r_stval()可以知道此处就是导致page fault的虚拟地址，我们要在这里分配物理内存并进行映射，于是我们先记录该地址。同时根据实验提示④，需要使用PGROUNDDOWN将错误的虚拟地址向下舍入到页面边界。
```
//......
else if(r_scause == 13 || r_scause == 15){
  uint64 va = r_stval();
  va = PGROUNDDOWN(va);
} 
//......
1
2
3
4
5
6
```
3、根据实验提示③，kernel/vm.c中的uvmalloc实现了内存分配与映射，具体代码如下所示。
```
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;
}
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
```
我们可以将这些代码复制到前面判断r_scause()为13或15那里，然后进行一些修改，我们这里只需要在指定位置分配1个page内存并完成映射即可。
```
//......

else if(r_scause == 13 || r_scause == 15){
    uint64 va = r_stval(); //引起pagefault的虚拟地址，需要分配物理内存并映射
    va = PGROUNDDOWN(va); //向下取整
    uint64 ka = (uint64)kalloc(); //分配内存
    if(pa == 0){  
      p->killed = 1; //分配物理内存失败，则杀死进程，且打印相关信息
      printf("usertrap(): kalloc() failed\n");
    }else{
      memset((void*)ka, 0, PGSIZE); //初始化置0
      if(mappages(p->pagetable, va, PGSIZE, ka, PTE_U | PTE_W| PTE_R) != 0)
      {
      //映射失败，则杀死进程，且打印相关信息
        kfree((void*)ka);
        printf("usertrap(): mappages() failed\n");
        p->killed = 1;
      }
    }
  } 
//......
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
```
4、根据实验提示⑤，kernel/vm.c中的uvmunmap()会触发panic，这是因为我们实现的是lazy allocation，这些页面还未映射，pet不存在。之后运行lazytests的时候还会产生uvmunmap: walk异常，也需要忽略。所以修改对应的两个函数，让它们在发现未映射的时候直接跳过就行了。
```
if((pte = walk(pagetable, a, 0)) == 0)
// panic("uvmunmap: walk"); 注释掉
  continue;
if((*pte & PTE_V) == 0)
//panic("uvmunmap: not mapped"); 注释掉
  continue;
1
2
3
4
5
6
```
2.3 实验结果

测试

打开xv6，执行echo hi，结果如下。

三、Lazytests and Usertests

3.1 实验描述

实验目的

我们为你提供了lazytests，这是一个xv6 用户程序，用于测试一些可能对你的lazy memory allocation造成压力的特定情况。修改你的内核代码，让所有的lazytests和usertests都通过。

实验提示

①处理sbrk()参数为负数的情况。
②如果一个进程在高于任何使用sbrk()分配的虚拟内存地址上发生页面错误，则终止该进程。
③正确处理fork()中的父子内存副本。
④处理进程将有效地址从sbrk()传递给系统调用(例如read或write)，但尚未分配该地址的内存的情况。
⑤正确处理内存不足：如果kalloc()在页面错误处理程序中失败，则终止当前进程。
⑥处理用户栈下方无效页面上的错误。

测试条件

如果你的内核通过了lazytests和usertests，则代表你的解决方案是正确的：

3.2 实验思路

参照实验提示的步骤一步一步来完成实验：

1、根据实验提示①，给sbrk添加处理参数为负数的情况。即dealloc相应的内存n，注意n不能大于p->sz。
```
uint64
sys_sbrk(void)
{
  int addr;
  int n;

  if(argint(0, &n) < 0)
    return -1;
  addr = myproc()->sz;
  if(n < 0)
  {
    if(addr + n < 0) return -1;
    else uvmdealloc(myproc()->pagetable, myproc()->sz, myproc()->sz+n);  
  }
  // if(growproc(n) < 0)
  //   return -1;
  myproc()->sz += n;
  return addr;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
```
2、根据实验提示②，如果读入的虚拟地址比p->sz大、读入的虚拟地址比进程的用户栈小、申请空间不够、映射失败的时候都需要终止进程。
```
else if(r_scause() == 13 || r_scause() == 15){
	uint64 va = r_stval();
    if (va < p->sz && va > PGROUNDDOWN(p->trapframe->sp)){
		uint64 ka = (uint64) kalloc();
        if (ka == 0) p->killed = -1; //分配内存失败
        else
        {
        	memset((void*)ka, 0, PGSIZE);
          	va = PGROUNDDOWN(va);
          	if (mappages(p->pagetable, va, PGSIZE, ka, PTE_U | PTE_W| PTE_R) != 0)
          	{
          		//映射失败
            	kfree((void*)ka);
            	p->killed = -1;
          	}
        }
    }
    else p->killed = -1; 	//读入的虚拟地址比p->sz大，比用户栈小
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
```
3、根据实验提示③，需要处理kernel/proc.c的fork()函数中父进程向子进程拷贝时的Lazy allocation 情况。

可以看到fork()是通过uvmcopy()将父进程页表向子进程拷贝的。对于uvmcopy()的处理和 uvmunmap()一致，只需要将PTE不存在和无效的两种情况由引发panic改为continue跳过即可。
```
//......

if((pte = walk(old, i, 0)) == 0)
  //panic("uvmcopy: pte should exist");  //注释掉原来这行
  continue; //添加
if((*pte & PTE_V) == 0)
  //panic("uvmcopy: page not present");  //注释掉原来这行
  continue; //添加

//......
1
2
3
4
5
6
7
8
9
10
```
4、根据实验提示④，当调用系统调用(如read、write)的时候，内核会访问未被分配的页表，此时不会进入usertrap，所以这时需要分配内存。我们查看sys_read和sys_write的调用顺序可以发现：sys_read()->fileread()->readi()->either_copyout()->copyout()->walkaddr()。我们看看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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
```
该函数实现的功能是：PTE无效、不存在、无PTE_U标志位时，都会返回0表示失败。现在我们需要添加Lazy allocation功能，所以PTE无效、不存在时需要分配、映射内存。将上面 (2、) 里面的代码部分重复处理一下即可。
```
uint64
walkaddr(pagetable_t pagetable, uint64 va)
{
  pte_t *pte;
  uint64 pa;
  struct proc *p=myproc();  // lab5-3

  if(va >= MAXVA)
    return 0;

  pte = walk(pagetable, va, 0);
  // lazy allocation - lab5-3
  if(pte == 0 || (*pte & PTE_V) == 0) {
    // va is on the user heap  
    if(va >= PGROUNDUP(p->trapframe->sp) && va < p->sz){
        char *pa;
        if ((pa = kalloc()) == 0) {
            return 0;
        }
        memset(pa, 0, PGSIZE);
        if (mappages(p->pagetable, PGROUNDDOWN(va), PGSIZE,
                     (uint64) pa, PTE_W | PTE_R | PTE_U) != 0) {
            kfree(pa);
            return 0;
        }
    } else {
        return 0;
    }
  }
  if((*pte & PTE_U) == 0)
    return 0;
  pa = PTE2PA(*pte);
  return pa;
}
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
```
5、实验提示⑤、⑥已经在前面实现了

6、如果直接make qemu会报错incomplete type proc。根据第二章的最后一个实验提示，需要在vm.c中先包含spinlock.h，然后包含proc.h。

3.3 实验结果

测试

运行xv6，执行lazytests，结果如下：

执行usertests，结果如下：

执行./grade-lab-lazy，结果如下。
相关阅读:
亚马逊云科技持续创新、领势而行，re:Invent颠覆想象
 FireMonkey 做界面的一个小技巧
 数据指标体系建设思考（一）
RK3568平台开发系列讲解（驱动篇）RK3568 PWM详解
 pc端微信不能发文件另存文件提示没有打开该文件的权限
 Java并发(二十)----synchronized原理进阶
 css中的单位
 智能门锁迈入“长尾”时代
 项目管理：团队执行力差，管理不善是根源
 机器学习之SGD, Batch, and Mini Batch的简单介绍
原文地址：https://blog.csdn.net/InnerPeaceHQ/article/details/126341711

文章目录

前言

一、Eliminate allocation from sbrk()

1.1 实验描述

1.2 实验思路

1.3 实验结果

二、Lazy allocation

2.1 实验描述

2.2 实验思路

2.3 实验结果

三、Lazytests and Usertests

3.1 实验描述

3.2 实验思路

3.3 实验结果