## Part One: Eliminate allocation from sbrk()

  1 2 3 4 5 6 7 8 9 10 11 12 13 14  int sys_sbrk(void) { int addr; int n; if(argint(0, &n) < 0) return -1; myproc()->sz += n; addr = myproc()->sz; /* if(growproc(n) < 0) */ /* return -1; */ return addr; }

 1 2  $echo hi pid 3 sh: trap 14 err 6 on cpu 0 eip 0x112c addr 0x4004--kill proc sh.c:exec() 中看到在执行 shell 命令时通过 malloc() 动态申请内存   1 2 3 4 5 6 7 8 9 10  struct cmd* execcmd(void) { struct execcmd *cmd; cmd = malloc(sizeof(*cmd)); memset(cmd, 0, sizeof(*cmd)); cmd->type = EXEC; return (struct cmd*)cmd; } 跳转到 malloc() 内， umalloc.c:malloc() 是基于 K&R The C Programming Language 8.7 节实现：通过链表来管理动态分配内存。   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  // static Header *freep = NULL; // start of free list void* malloc(uint nbytes) { Header *p, *prevp; uint nunits; nunits = (nbytes + sizeof(Header) - 1)/sizeof(Header) + 1; if((prevp = freep) == 0){ // no free list yet base.s.ptr = freep = prevp = &base; base.s.size = 0; } for(p = prevp->s.ptr; ; prevp = p, p = p->s.ptr){ if(p->s.size >= nunits){ // big enough if(p->s.size == nunits) // exactly prevp->s.ptr = p->s.ptr; else { // allocate tail end p->s.size -= nunits; p += p->s.size; p->s.size = nunits; } freep = prevp; return (void*)(p + 1); } if(p == freep) // wrapped around free list if((p = morecore(nunits)) == 0) return 0; // none left } } 当遍历整个链表都没有剩余空间时 malloc() 会调用 morecore() 向系统申请更多的内存空间 umalloc.c:morecore() 会根据所需空间大小调用 sbrk() 这个 system call 申请内存   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16  static Header* morecore(uint nu) { char *p; Header *hp; if(nu < 4096) nu = 4096; p = sbrk(nu * sizeof(Header)); if(p == (char*)-1) return 0; hp = (Header*)p; hp->s.size = nu; free((void*)(hp + 1)); return freep; } 由于在 sysproc.c:sys_sys_sbrk() 中已经把 growproc() 注释掉，进程实际的内存空间没有被分配出来，即使 malloc() 已经返回了首地址也不能正常访问，从而导致 Page fault。 从错误信息中得知导致异常的代码地址是 0x112c ，从 sh.asm 找到   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16  p = sbrk(nu * sizeof(Header)); 111b: 83 ec 0c sub$0xc,%esp 111e: 56 push %esi 111f: e8 76 fc ff ff call d9a if(p == (char*)-1) 1124: 83 c4 10 add $0x10,%esp 1127: 83 f8 ff cmp$0xffffffff,%eax 112a: 74 1c je 1148 hp->s.size = nu; ;; 抛出异常的代码 112c: 89 58 04 mov %ebx,0x4(%eax) free((void*)(hp + 1)); 112f: 83 ec 0c sub $0xc,%esp 1132: 83 c0 08 add$0x8,%eax 1135: 50 push %eax 1136: e8 f5 fe ff ff call 1030 

 1  hp->s.size = nu;

0x112c 对应的代码可以看到 mov %ebx, 0x4(%eax) 访问了 malloc() 返回地址 + 4 的内容，由于这个地址对应的物理页是不存在的，所以会抛出异常。

## Part Two: Lazy allocation

• look at the cprintf arguments to see how to find the virtual address that caused the page fault.

• steal code from allocuvm() in vm.c, which is what sbrk() calls (via growproc()).

• use PGROUNDDOWN(va) to round the faulting virtual address down to a page boundary.

• break or return in order to avoid the cprintf and the myproc()->killed = 1.

• you’ll need to call mappages(). In order to do this you’ll need to delete the static in the declaration of mappages() in vm.c, and you’ll need to declare mappages() in trap.c. Add this declaration to trap.c before any call to mappages():

int mappages(pde_t *pgdir, void *va, uint size, uint pa, int perm);

• you can check whether a fault is a page fault by checking if tf->trapno is equal to T_PGFLT in trap().

  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  void trap(struct trapframe *tf) { uint a; char *mem; // ... switch(tf->trapno){ // ... case T_PGFLT: a = PGROUNDDOWN(rcr2()); if (!(mem = kalloc())) { cprintf("allocuvm out of memory.\n"); goto ALLOC_FAILED; } memset(mem, 0, PGSIZE); if (mappages(myproc()->pgdir, (char *)a, PGSIZE, V2P(mem), PTE_W|PTE_U) < 0) { cprintf("allocuvm out of memory.\n"); kfree(mem); goto ALLOC_FAILED; } break; ALLOC_FAILED: //PAGEBREAK: 13 default: // ... } }