作业地址

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

重新编译执行 echo hi 后出现下面的错误

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 <sbrk>
if(p == (char*)-1)
  1124:	83 c4 10             	add    $0x10,%esp
  1127:	83 f8 ff             	cmp    $0xffffffff,%eax
  112a:	74 1c                	je     1148 <malloc+0x88>
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 <free>

对应到源代码就是

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:
    // ...
  }
}