09_pintos_VM_memory_management

우리는 가상메모리 혹은 물리메모리를 누가 사용했고 무슨 목적으로 사용했는지를 기억하고 있어야함
이를 위해서 우리는 supplemental page table을 사용할 것이고 이후에 물리 메모리를 다룰 예정이다.

1. supplemental_page_table_init
   우리는 hash table을 사용할 것이기 때문에 hash init을 여기서 해준다.
   사용 전에 struct page에 hash_elem 또한 추가해준다.
   init 함수는 __do_fork 에서 호출이된다. (spt 함수들이 어디서 호출되는지도 알아두자)

/* Initialize new supplemental page table */
void
supplemental_page_table_init (struct supplemental_page_table *spt UNUSED) {
  hash_init (&spt->pages, page_hash, page_cmp_less, NULL);
}

struct page {
	const struct page_operations *operations;
	void *va;              /* Address in terms of user space */
	struct frame *frame;   /* Back reference for frame */

	/* Your implementation */
	struct hash_elem elem_hash;
	bool writable;
	/* Per-type data are binded into the union.
	 * Each function automatically detects the current union */
	union {
		struct uninit_page uninit;
		struct anon_page anon;
		struct file_page file;
#ifdef EFILESYS
		struct page_cache page_cache;
#endif
	};
};

해시를 사용하기 위해서 spt에 hash struct 를 추가해줌

/* Representation of current process's memory space.
 * We don't want to force you to obey any specific design for this struct.
 * All designs up to you for this. */
struct supplemental_page_table {
	struct hash pages;
};

2. spt_find_page 함수 (spt table에서 input된 va와 동일한 page를 찾는다)

/* Find VA from spt and return page. On error, return NULL. */
struct page *
spt_find_page (struct supplemental_page_table *spt UNUSED, void *va UNUSED) {
  // struct page *page = NULL;
  /* TODO: Fill this function. */

  struct page *page = (struct page *) malloc (sizeof (struct page)); // va 와 일치하는 page 정보를 찾기 위해서 임시적인 공간을 만들어줌
  struct hash_elem *e; // hash_find를 통해서 찾은 hash_elem을 저장하기 위한 공간

  page->va = pg_round_down (va); // pg_round_down() 함수를 통해서 page의 시작주소로 변경을 해준 후 위에서 만든 임시공간의 va와 연결시켜줌
  e = hash_find (&spt->pages, &page->elem_hash); // 입력받은 spt hash에서 일치하는 page를 찾고 --> 해당 page의 hash_elem을 e로 return 한다
  free (page); // page의 역할을 다 끝났으니 free 해주고

  return e != NULL ? hash_entry (e, struct page, elem_hash) : NULL; // e가 NULL이 아니면 e를 page로 확장해서 page를 return하고 NULL이면 NULL 을 return 함
}

3. spt_insert_page
   hash에 page를 insert 함.
   insert에 성공하면 return true 실패하면 return false.

/* Insert PAGE into spt with validation. */
bool
spt_insert_page (struct supplemental_page_table *spt UNUSED,
                 struct page *page UNUSED) {
  // int succ = false;
  /* TODO: Fill this function. */

  return insert_page (&spt->pages, page); // hash와 page를 이용해서 hash에 page를 insert 한다.
}

bool
insert_page (struct hash *pages, struct page *p) {
  if (hash_insert (pages, &p->elem_hash) == NULL) { // pages(hash)에 page의 hash_elem을 넣어서 연결해줌 연결에 성공하면 NULL이 return 됨
    return true; // 연결에 성공했으면 true를 return 하고
  } else {
    return false; // 실패하면 false를 return 함
  }
}

4. Frame management
   frame은 list로 관리할 것이기 때문에 frame struct에 list_elem을 추가함
   frame은 물리메모리 상의 block이니깐 kva라고 명명되어 있음

/* The representation of "frame" */
struct frame {
	void *kva;
	struct page *page;
	struct list_elem elem_fr;
};

5. vm_get_frame
   frame을 얻기 위한 함수 - 얻는데 성공한다면 frame_table에 넣어서 관리함
   전역변수로 frame_table을 선언해줌

모든 유저 공간 페이지들은 이 함수를 통해서 할당될 것

struct list frame_table;

/* palloc() and get frame. If there is no available page, evict the page
 * and return it. This always return valid address. That is, if the user pool
 * memory is full, this function evicts the frame to get the available memory
 * space.*/
 //모든 유저 공간 페이지들은 이 함수를 통해서 할당될 것임
static struct frame *
vm_get_frame (void) { // palloc으로 page를 얻고 frame을 가져옴
  struct frame *frame = (struct frame *) malloc (sizeof (struct frame)); // frame 공간을 할당 받고
  /* TODO: Fill this function. */

  frame->kva = palloc_get_page (PAL_USER); // frame의 물리메모리 주소에 PAL_USER로 page를 할당 받아서 넣는다 -- Gitbook 에 PAL_USER로 할당 받아야한다는게 있음
  if (frame->kva == NULL) { // 만약 할당에 실패했다면
    frame = vm_evict_frame (); // 해당 frame을 지움
    frame->page = NULL; // page는 NULL로 하고
    return frame; // 그 frame을 반환함
  }
  list_push_back (&frame_table, &frame->elem_fr); // 위 if문에 걸리지 않았다면 frame table에 현재 frame을 넣어주고
  frame->page = NULL; // page는 NULL로 함 -- frame 내의 page에는 아직 할당된게 없으니깐

  ASSERT (frame != NULL);
  ASSERT (frame->page == NULL);

  return frame; // 해당 frame을 return 함
}

vm_evict_frame

/* Evict one page and return the corresponding frame.
 * Return NULL on error.*/
static struct frame *
vm_evict_frame (void) {
  struct frame *victim = vm_get_victim (); // vm_get_victim() --> 제거될 frame을 가져옴
  /* TODO: swap out the victim and return the evicted frame. */
  swap_out (victim->page); // 제거될 frame을 disk에 복사함

  return victim; // 제거될 frame을 return 함
}

vm_get_victim

/* Get the struct frame, that will be evicted. */
static struct frame *
vm_get_victim (void) {
  struct frame *victim = NULL;
  /* TODO: The policy for eviction is up to you. */

  struct thread *cur = thread_current (); // 현재 thread를 불러오고
  struct list_elem *s; // list 순회를 위해서 필요한 list_elem 선언

  for (s = list_begin (&frame_table); s != list_end (&frame_table); s = list_next (s)) { // frame은 전역변수로 선언이 되어있음
    victim = list_entry (s, struct frame, elem_fr); // frame으로 확장
    if (pml4_is_accessed (cur->pml4, victim->page->va)) // PML4에 VPAGE용 PTE가 있는지 없는지 확인함 -> 즉 pml4에 해당 page가 있는지 없는지 찾는 부분 --> 있으면 true, 없으면 false
      pml4_set_accessed (cur->pml4, victim->page->va, 0); // 만일 있었다면 해당 access를 0으로 바꿔줌
    else
      return victim; 
  }

  return victim;
}

6. vm_do_claim_page
   page에 물리메모리 frame을 할당함

/* Claim the PAGE and set up the mmu. */
static bool
vm_do_claim_page (struct page *page) {
  struct frame *frame = vm_get_frame ();

  /* Set links */
  frame->page = page; // frame과 page를 이어줌
  page->frame = frame;

  /* TODO: Insert page table entry to map page's VA to frame's PA. */

  if (install_page (page->va, frame->kva, page->writable)) // page의 가상메모리와 frame의 물리메모리를 매핑해주고 page의 writable 정보도 같이 써줌
    return swap_in (page, frame->kva); // 해당 매핑이 성공한다면 해당 페이지를 물리메모리로 swap in 해줌

  return false; // 실패했다면 false를 return 함
}

7. vm_claim_page
   input된 va와 일치하는 page를 찾고 찾았다면 frame도 할당해줌

/* Claim the page that allocate on VA. */
// 주어진 va에 page를 할당함
bool
vm_claim_page (void *va UNUSED) {
  struct page *page = NULL;
  /* TODO: Fill this function */
  page = spt_find_page (&thread_current ()->spt, va); // spt에 va와 일치하는 page를 찾아옴

  if (page == NULL) { // page가 NULL이면 va와 일치하는 page가 없기 때문에
    return false; // false를 return 하고
  }

  return vm_do_claim_page (page); // 일치하는 page를 찾았다면 frame 도 할당함
}