106 OS homework 2-2 成果報告書

組長：B10415011、賴君庭
組員：B10415024、廖珮均
github: https://github.com/Nina9721/xv6-public/

🙂 使用情境說明(包含流程圖)

系統流程圖

user使用流程(test1)

例外狀況：
address是virtual address的illege range(意即他無法process的page table)，印出錯誤訊息，且刪掉這個讓page fault產生的process

😇 成功畫面

test1(cow vs fork)

test2

test3

🏃 實作過程(修改哪些檔案[含圖片])

有做更改的檔案

defs.h

char*           kalloc(void);
void            kfree(char*);
void            kinit1(void*, void*);
void            kinit2(void*, void*);
uint		 getNumFreePages(void);//B10415011
uint		 getRefcount(uint pa);//B10415011
void	  	 decrementRefcount(uint pa);//B10415011
void	    	 incrementRefcount(uint pa);//B10415011

// vm.c
void            seginit(void);
void            kvmalloc(void);
pde_t*          setupkvm(void);
char*           uva2ka(pde_t*, char*);
int             allocuvm(pde_t*, uint, uint);
int             deallocuvm(pde_t*, uint, uint);
void            freevm(pde_t*);
void            inituvm(pde_t*, char*, uint);
int             loaduvm(pde_t*, char*, struct inode*, uint, uint);
pde_t*          copyuvm(pde_t*, uint);
void            switchuvm(struct proc*);
void            switchkvm(void);
int             copyout(pde_t*, uint, void*, uint);
void            clearpteu(pde_t *pgdir, char *uva);
void		 pagefault(uint err_code);//B10415011

usys.S

SYSCALL(getNumFreePages)//B10415011

Makefile

//B10415011
	_testcow\

syscall.c

extern int sys_getNumFreePages(void);//B10415011

[SYS_getNumFreePages]   sys_getNumFreePages,//B10415011

syscall.h

#define SYS_getNumFreePages  22//B10415011

sysproc.c

//B10415011
int 
sys_getNumFreePages(void)
{
  return getNumFreePages();
}

user.h

int getNumFreePages(void);//B10415011

vm.c

pde_t*
copyuvm(pde_t *pgdir, uint sz)
{
  pde_t *d;
  pte_t *pte;
  uint pa, i, flags;
  
  //char *mem;

  if((d = setupkvm()) == 0)
    return 0;
  for(i = 0; i < sz; i += PGSIZE){
    if((pte = walkpgdir(pgdir, (void *) i, 0)) == 0)
      panic("copyuvm: pte should exist");
    if(!(*pte & PTE_P))
      panic("copyuvm: page not present");
      
    // B10415011
    // Read only
    *pte &= ~PTE_W;
    
    pa = PTE_ADDR(*pte);
    flags = PTE_FLAGS(*pte);
    
    //if((mem = kalloc()) == 0)
    //  goto bad;
    //memmove(mem, (char*)P2V(pa), PGSIZE);
    //if(mappages(d, (void*)i, PGSIZE, V2P(mem), flags) < 0)
    
    if(mappages(d, (void*)i, PGSIZE, pa, flags) < 0)
      goto bad;
      
    incrementRefcount(pa);
  }
  
  // Flush TLB for original process
  lcr3(V2P(pgdir));
  return d;

bad:
  freevm(d); 
  // Flush TLB
  // Some entries in the original process page table have been changed
  lcr3(V2P(pgdir));
  return 0;
}


//B10415024
void
pagefault(uint err_code)
{
  //cprintf("Page fault occured.\n");

  
  //struct proc *curproc = myproc();
  //struct cpu *curcpu = mycpu();//cpu->apicid
  
  // Get the fault virtual address from the CR2 register
  uint va = rcr2();
  pte_t *pte;

  // Error handling code
  if(myproc() == 0)
  {
    cprintf("Page fault with no user process from cpu %d, cr2=0x%x\n", cpuid(), va);
    panic("pagefault");
  }

  if(va >= KERNBASE || (pte = walkpgdir(myproc()->pgdir, (void*)va, 0)) == 0 || !(*pte & PTE_P) || !(*pte & PTE_U))
  {
    cprintf("Illegal virtual address on cpu %d address 0x%x, kill proc %s with pid %d\n", cpuid(), va, myproc()->name, myproc()->pid);

    // Mark the process as killed
    myproc()->killed = 1;
    return ;
  }
  
  // Current page has write permissions enabled
  if(*pte & PTE_W)
  {
    cprintf("Error code: %x, address 0x%x\n", err_code, va);
    panic("Page fault already writeable");
  }

  // Get the physical address from the given page table entry
  uint pa = PTE_ADDR(*pte);
  // Get the refcount of the current page
  uint refcount = getRefcount(pa);
  char *mem;

  // Current process is the first one that tries to write to this page
  if(refcount > 1)
  {
    // Allocate a new memory page for the process
    if((mem = kalloc()) == 0)
    {
      cprintf("Page fault out of memory, kill proc %s with pid %d\n", myproc()->name, myproc()->pid);
      myproc()->killed = 1;
      return;
    }
    
    // Copy the contents from the original memory page pointed the virtual address
    memmove(mem, (char*)P2V(pa), PGSIZE);
    // Point the given page table entry to the new page
    *pte = V2P(mem) | PTE_P | PTE_U | PTE_W;
    // Since the current process now doesn't point to original page
    decrementRefcount(pa);
  }
  // Current process is the last one that tries to write to this page
  else if(refcount == 1)
  {
     // Remove the read only restriction on the trapping page
     *pte |= PTE_W;
  }
  else 
  {
     panic("pagefault reference count wrong\n");
  }

  // Flush TLB for process 
  lcr3(V2P(myproc()->pgdir));
}

kalloc.c

struct {
  struct spinlock lock;
  int use_lock;
  struct run *freelist;
  
  uint numFreePages;//B10415024// store the numFreePages
  uint pg_refcount[PHYSTOP >> PGSHIFT];//B10415024
} kmem;

void
kinit1(void *vstart, void *vend)
{
  initlock(&kmem.lock, "kmem");
  kmem.use_lock = 0;
  //B10415024
  // Initialize the numFreePages
  kmem.numFreePages = 0;
  freerange(vstart, vend);
}

void
freerange(void *vstart, void *vend)
{
  char *p;
  p = (char*)PGROUNDUP((uint)vstart);
  for(; p + PGSIZE <= (char*)vend; p += PGSIZE)
  {
    //B10415024
    // Initialize the refcount
    kmem.pg_refcount[V2P(p) >> PGSHIFT] = 0;
    kfree(p);
  }
}

void
kfree(char *v)
{
  struct run *r;

  if((uint)v % PGSIZE || v < end || V2P(v) >= PHYSTOP)
    panic("kfree");


  if(kmem.use_lock)
    acquire(&kmem.lock);
  r = (struct run*)v;

  //B10415024
  // Someone free it
  if(kmem.pg_refcount[V2P(v) >> PGSHIFT] > 0)
    --kmem.pg_refcount[V2P(v) >> PGSHIFT];
 
  // No reference to the page -> free the page
  if(kmem.pg_refcount[V2P(v) >> PGSHIFT] == 0)
  { 
    // Fill with junk to catch dangling refs.
    memset(v, 1, PGSIZE);
    // When a page is freed
    kmem.numFreePages++;
    r->next = kmem.freelist;
    kmem.freelist = r;
  }
  
  if(kmem.use_lock)
    release(&kmem.lock);
}

char*
kalloc(void)
{
  struct run *r;

  if(kmem.use_lock)
    acquire(&kmem.lock);
  r = kmem.freelist;
  if(r)
  {
    kmem.freelist = r->next;
    //B10415024
    // On a page allocation
    kmem.numFreePages--;
    // When allocate
    kmem.pg_refcount[V2P((char*)r) >> PGSHIFT] = 1;
  }
  if(kmem.use_lock)
    release(&kmem.lock);
  return (char*)r;
}

//B10415011
uint 
getNumFreePages(void)
{
  acquire(&kmem.lock);
  uint numFreePages = kmem.numFreePages;
  release(&kmem.lock);
  return numFreePages;
}

//B10415011
uint 
getRefcount(uint pa)
{
  if(pa < (uint)V2P(end) || pa >= PHYSTOP)
    panic("getRefcount");
  
  acquire(&kmem.lock);
  uint count = kmem.pg_refcount[pa >> PGSHIFT];
  release(&kmem.lock);
  return count;
}

//B10415011
void
decrementRefcount(uint pa)
{
  if(pa < (uint)V2P(end) || pa >= PHYSTOP)
    panic("decrementRefcount");
  
  acquire(&kmem.lock);
  --kmem.pg_refcount[pa >> PGSHIFT];
  release(&kmem.lock);
}

//B10415011
void
incrementRefcount(uint pa)
{
  if(pa < (uint)V2P(end) || pa >= PHYSTOP)
    panic("incrementRefcount");
  
  acquire(&kmem.lock);
  ++kmem.pg_refcount[pa >> PGSHIFT];
  release(&kmem.lock);
}

trap.c

void
trap(struct trapframe *tf)
{
  ...

  switch(tf->trapno){
  //B10415024
  case T_PGFLT:
    pagefault(tf->err);
    break;
  ...
  }

  ...
}

testcow.c

//B10415024

#include "types.h"
#include "stat.h"
#include "user.h"

int a = 1;

void
test1()
{
//1
  printf(1, "Number of free pages : %d\n", getNumFreePages());
  printf(1, "-Fork-\n");
  int pid = fork();
//1
  if(pid == 0)//code exec by child
  {
//3
    printf(1, "Child:  'a' = %d\n", a);
    printf(1, "Number of free pages : %d\n", getNumFreePages());
    printf(1, "-Change-\n");
    a = 2;
    printf(1, "Child:  'a' = %d\n", a);
    printf(1, "Number of free pages : %d\n", getNumFreePages());
    exit();
//3
  }
//2
  printf(1, "Parent: 'a' = %d\n", a);
  wait();
//2
//4
  printf(1, "-Reaping child-\n");
  printf(1, "Patent: 'a' = %d\n", a);
  printf(1, "Number of free pages : %d\n", getNumFreePages());
  return;
//4
}

void
test2()
{
//1
  printf(1, "Number of free pages : %d\n", getNumFreePages());
  printf(1, "-First time Fork-\n");
  int pid = fork();
//1
  if(pid == 0)
//2.5
    exit();
//2.5
  else
  { 
//2
    printf(1, "Number of free pages : %d\n", getNumFreePages());
    printf(1, "-Second time Fork-\n");
    pid = fork();
//2
    if(pid == 0)
    {
//5
      printf(1, "Child:  'a' = %d\n", a);
      printf(1, "Number of free pages : %d\n", getNumFreePages());
      printf(1, "-Change-\n");
      a = 5;
      printf(1, "Child:  'a' = %d\n", a);
      printf(1, "Number of free pages : %d\n", getNumFreePages());
      exit();
//5
    }
//3
    printf(1, "Number of free pages : %d\n", getNumFreePages());
    wait();
//
    printf(1, "-Reaping child-\n");
//3
  }
//4
  printf(1, "Number of free pages : %d\n", getNumFreePages());
  wait();
//4
//6
  printf(1, "-Reaping child-\n");
  printf(1, "Number of free pages : %d\n", getNumFreePages());
//6
  return;
}

void
test3()
{
//1
  a = 3;
  printf(1, "Number of free pages : %d\n", getNumFreePages());
  printf(1, "-First time Fork-\n");
  int pid = fork();
//1

  if(pid == 0)
  { 
//3
    printf(1, "Child 1 : 'a' = %d\n", a);
    printf(1, "Number of free pages : %d\n", getNumFreePages());
    printf(1, "-Change-\n");
    a = 4;
    printf(1, "Child 1 : 'a' = %d\n", a);
    printf(1, "Number of free pages : %d\n", getNumFreePages());
//3
  }
  else 
  {
//2
    printf(1, "Number of free pages : %d\n", getNumFreePages());
    wait();
//2
//4
    printf(1, "-Reaping child-\n");
    printf(1, "Number of free pages : %d\n", getNumFreePages());
    printf(1, "-Second time Fork-\n");
    pid = fork();
//4
    if(pid == 0)
    { 
//6
      printf(1, "Child 2 : 'a' = %d\n", a);
      printf(1, "Number of free pages : %d\n", getNumFreePages());
      printf(1, "-Change-\n");
      a = 4;
      printf(1, "Child 2 : 'a' = %d\n", a);
      printf(1, "Number of free pages : %d\n", getNumFreePages());
//6
    }
    else 
    {
//5
       printf(1, "Number of free pages : %d\n", getNumFreePages());
       wait();
//5
//7
       printf(1, "-Reaping child-\n");
       printf(1, "Number of free pages : %d\n", getNumFreePages());
//7
    }
  }
  return;
}
int
main(void)
{
  printf(1, "Parent and Child share the global variable 'a'\n");
  printf(1,"---run test1---\n");
  test1();
  printf(1,"---------------\n");
  printf(1,"---run test2---\n");
  test2();  
  printf(1,"---------------\n");
  printf(1,"---run test3---\n");
  test3();  
  printf(1,"---------------\n");
  exit();
}

😎 結論

copy on write是對fork這個system call修改，主要是為了減少記憶體的用量。本來的fork是創一個child process，這個child process直接從parent的記憶體複製過來，花費相對較多的時間跟記憶體用量；而copy on write解決了這個問題，它是在child需要做更動時，才把記憶體內容複製過來，在未更動以前，child只從parent複製一部分的記憶體內容，另外沒有複製的部分是屬於與parent的共用區段。

📅 組員分工

君庭 B10415011：新增system call、處理page table、測試、Debug
珮均 B10415024：追蹤count、意外處理、測試、Debug