一、什么是惰性分配（lazy page allocation）？

1.eager allocation

sbrk是xv6提供的系统调用，使得用户应用程序能扩大自己的heap。当一个应用程序启动的时候，PAGESIZE为heap的最底端，同时也是stack的最顶端。这个位置通过代表进程的数据结构中的sz字段表示，这里以*p->sz表示*。

当调用sbrk时，它的参数是整数，代表了你想要申请的字节数.

这意味着，当sbrk实际发生或者被调用的时候，内核会分配一些物理内存，并将这些内存映射到用户应用程序的地址空间，然后将内存内容初始化为0，再返回sbrk系统调用。这样，应用程序可以通过多次sbrk系统调用来增加它所需要的内存。类似的，应用程序还可以通过给sbrk传入负数作为参数，来减少或者压缩它的地址空间。

在XV6中，**sbrk的实现默认是eager allocation。这表示了，一旦调用了sbrk，内核会立即分配**应用程序所需要的物理内存。但是实际上，对于应用程序来说很难预测自己需要多少内存，所以通常来说，应用程序倾向于申请多于自己所需要的内存。这意味着，进程的内存消耗会增加许多，但是有部分内存永远也不会被应用程序所使用到。

2.lazy allocation的核心思想

lazy allocation核心思想非常简单，sbrk系统调基本上不做任何事情，唯一需要做的事情就是提升p->sz，将p->sz增加n，其中n是需要新分配的字节数。但是内核在这个时间点并不会分配任何物理内存。之后在某个时间点，应用程序使用到了新申请的那部分内存，这时会触发page fault，因为我们还没有将新的内存映射到page table。所以，如果我们解析一个大于旧的p->sz，但是又小于新的p->sz（注，也就是旧的p->sz + n）的虚拟地址，我们希望内核能够分配一个内存page，并且重新执行指令。

所以，当我们看到了一个page fault，相应的虚拟地址小于当前p->sz，同时大于stack，那么我们就知道这是一个来自于heap的地址，但是内核还没有分配任何物理内存。所以对于这个page fault的响应也理所当然的直接明了：在page fault handler中，通过kalloc函数分配一个内存page；初始化这个page内容为0；将这个内存page映射到user page table中；最后重新执行指令。比方说，如果是load指令，或者store指令要访问属于当前进程但是还未被分配的内存，在我们映射完新申请的物理内存page之后，重新执行指令应该就能通过了。

二、如何实现lazy allocation?

lazy allocation的核心思想简单易懂，我们根据思想对sbrk函数进行修改即可.注意：sbrk函数不仅用于增加物理内存，也用于减少物理内存

1.先分析sbrk函数原本的功能，再做修改

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
uint64
sys_sbrk(void)
{
  int addr;
  int n;
  //n为想要增加或减少的字节数
  //addr为p->sz 所指的地址
  if(argint(0, &n) < 0)
    return -1;
  addr = myproc()->sz;
  if(growproc(n) < 0)
    return -1;
  return addr;
}

// 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){
    //立马分配n个字节给进程(eager allocation)
    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;
}

可以看出来sbrk函数原本根据n的正负值来立刻分配或立刻减少n个字节给进程

根据lazy allcation的思想，我们在进程要求新增物理内存大小的时候只增加p->sz的值，如何操作看下一节，我们还需要思考，**lazy allocation的思想是否可以用于减少物理内存的大小？**

答案是不可以：因为我们是通过page fault会进入usertrap函数这一机制，在进程实际需要使用到内存的时候为其分配物理内存。

倘若n值为复数，我们仅仅将p-sz的值减少而不去释放物理内存，那么当进程访问本不应该存在的物理地址时，不会发生page fault，

进而程序使用了本不应该使用的物理内存，而操作系统却没有报错。所以我们对n值为负数时，立刻释放物理内存的操作不做修改。

修改后的sbrk函数如下(为了避免对growproc函数的修改，将n值正负如何进行处理的代码选择放在了sbrk函数中)：

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
uint64
sys_sbrk(void)
{
  int addr;
  int n;

  if(argint(0, &n) < 0)
    return -1;

  struct proc* p = myproc();
  addr = p->sz;
  uint64 sz = p->sz;

  if(n > 0) {
    // lazy allocation 仅增加p->sz的大小，并不实际分配物理内存
    p->sz += n;
  } else if(sz + n > 0) {
  	// 减少n字节
    sz = uvmdealloc(p->pagetable, sz, sz + n);
    p->sz = sz;
  } else {
  	// 减少n字节，p-sz 大小小于0，说明减少的字节太多，发生错误。
    return -1;
  }
  return addr;

}

2.在usertrap中增加对page fault的处理

2.1 trap流程与systemcall调用流程的区别

这里的 trap流程与systemcall类似，不同于systemcall的是，在进入内核态后，r_scause()值不同，原本的

xv6系统，虽然scause会根据不同的trap赋予不同的值，但实际上的usertrap函数中只有处理scause值为8（系统调用）的代码，我们需要在usertrap函数中自行添加对page fault的处理。

我们可以根据图片看出来xv6系统会根据不同的page fault生成三种不同的数值：12(因为指令执行引起的page fault)、13(因为load–读操作引起的page fault)、15(是因为store–写操作引起的page fault)

由于本身的xv6系统不存在实际上的scause为其他值的情况，我们可以认为所有scause值为其他值的情况都是由于我们的修改引起的。我们可以用print函数将scause值打印出来调试错误，实际上后续的实验过程中，由于lazy allocation引起的scause只有13或15两种值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//
// handle an interrupt, exception, or system call from user space.
// called from trampoline.S
//
void
usertrap(void)
{
  ....
  ....
  // system call    
  if(r_scause() == 8){
    
    ...  
      
  } //page fault
    else if(r_scause() == 15||r_scause() == 13){
    ...
    ...
  } 
    ...
    ...
  usertrapret();
}

2.2 发生page fault的虚拟地址范围

这样我们在usertrap函数中可以通过r_stval得知发生page fault的虚拟地址

xv6中虚拟地址的范围在0-MAXVA之间，所以超出这个范围的sepc值属于严重的错误，我们应该将进程杀死，而不是对待page fault的方式对其进行处理。lazy allocation政策下发生page fault的情况是错以为有内存的情况下进行读写操作，所以发生page fault的虚拟地址应该小于进程认为自己拥有的字节大小（p->sz）

其次，目前的lazy allocation仅在需要增加字节的时候使用，所以发生page fault的虚拟地址应该大于栈指针（p->trapframe->sp）（xv6最初的进程为栈分配了PGSIZE的值，后续的进程都是初始进程fork出来的，意味着所有进程都具有PGSIZE大小的栈，那么我们lazy allocation的地址一定是大于栈指针的）。

所以，综合考虑下我们检测发生page fault的范围应该是p->trapframe->sp - p->sz

2.3 分配物理内存并进行映射

在判断发生虚拟地址的正确性后，我们需要做的就是为其分配物理地址并映射，应该注意的是当物理内存不足后，我们直接杀死了进程。其余更高级的系统会采用更加灵活的方式：

最终的代码应该是

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
//kernel/trap.c/usertrap函数中

else if(r_scause() == 15||r_scause() == 13){//page fault
    // printf("it is page fault\n");
    // printf("usertrap(): unexpected scause %p pid=%d\n", r_scause(), p->pid);
    // printf("            sepc=%p stval=%p\n", r_sepc(), r_stval());
    //stval寄存器中保存了造成页面错误的虚拟地址
    uint64 va=r_stval();
    //如果某个进程在高于sbrk()分配的任何虚拟内存地址上出现页错误，则终止该进程。
    //page guard
    if(PGROUNDUP(p->trapframe->sp) - 1 >= va ){
        p->killed=1;
    }else if(va>p->sz){
      p->killed=1;
    }else{
      uint64* ka=kalloc();
      if(ka==0){
        //printf("out of memory\n");
        p->killed=1;
      }else{
          //填空垃圾数据
          memset((void *)ka, 0, PGSIZE);
          if(mappages(p->pagetable, PGROUNDDOWN(va), PGSIZE, (uint64)ka, PTE_W|PTE_X|PTE_R|PTE_U) != 0){
            kfree((void *)ka);
            p->killed=1;
          }
        }
      }  
  }

三、惰性分配一定优于积极分配(eager allocation)吗？

​ 惰性分配策略并不一定优于积极分配策略。两种策略各有优缺点，适用于不同的场景和需求。积极分配策略直接为进程分配内存，简单直接，适合对内存需求较为明确的情况，可以提高系统的响应速度。而惰性分配策略则可以节省内存资源，只在实际需要时进行分配，适用于内存需求不确定或者资源有限的情况下，可以降低内存的浪费。因此，选择哪种分配策略取决于具体的应用场景和需求，没有一种策略绝对优于另一种策略。