[pintos] Week4~5: Virtual Memory - Part.2 Memory Management

Memory Management

가상 메모리 시스템이 제대로 돌아가기 위해서는 가상메모리 페이지(virtual pages)와 물리메모리 페이지 프레임(physical frames)을 효과적으로 관리해야 한다. 즉, 임의의 가상 혹은 물리 메모리 영역을 누가 사용했고, 어떤 목적으로 사용했는지 등을 기억하고 있어야 한다. 당신은 먼저 supplemental page table을 다루고, 그 이후에 물리메모리 페이지 프레임을 다뤄야 한다.

• include/vm/vm.h

struct page {
  const struct page_operations *operations;
  void *va;              /* Address in terms of user space */
  struct frame *frame;   /* Back reference for frame */
  struct hash_elem hash_elem;			// 해시 저장용 elem
    
  union {
    struct uninit_page uninit;
    struct anon_page anon;
    struct file_page file;
#ifdef EFILESYS
    struct page_cache page_cache;
#endif
  };
};

우리는 SPT를 구현해야 한다. SPT를 이루는 자료구조는 해시 테이블을 사용할 예정이다. 그렇기 때문에 해시테이블에 저장하고 순회를 하기 위해 hash_elem을 추가한다.

---

supplemental_page_table_init 구현

/* 프로세스가 시작될 때(initd) or 포크될 때(__do_fork) 호출되는 함수 */
void
supplemental_page_table_init (struct supplemental_page_table *spt UNUSED) 
{
	/* SPT 초기화시 hash_init에 아래 작성한 page_hash, page_less를 포함한다. */
	hash_init(&spt->pages, page_hash, page_less, NULL);
}

supplemental_page_table_init은 보조 페이지 테이블을 초기화 한다. 보조 페이지 테이블을 해시 테이블로 구현할 것이다. 

/* Hash table. */
struct hash {
	size_t elem_cnt;            /* Number of elements in table. */
	size_t bucket_cnt;          /* Number of buckets, a power of 2. */
	struct list *buckets;       /* Array of `bucket_cnt' lists. */
	hash_hash_func *hash;       /* Hash function. */
	hash_less_func *less;       /* Comparison function. */
	void *aux;                  /* Auxiliary data for `hash' and `less'. */
};

해시 자료구조를 보면  hash_hash_func 와 hash_less_func라는 필드가 보인다. 이 필드가 무엇인지 확인해 보면 

/* 보조 데이터 AUX가 주어졌을 때, 해시 요소 E의 해시 값을 계산하여 반환합니다. */
typedef uint64_t hash_hash_func (const struct hash_elem *e, void *aux);

/* 보조 데이터 AUX가 주어지면 두 해시 요소 A와 B의 값을 비교합니다.
 * A가 B보다 작으면 true를 반환하고,
 * A가 B보다 크거나 같으면 false를 반환합니다. */
typedef bool hash_less_func (const struct hash_elem *a,
		const struct hash_elem *b,
		void *aux);

위 코드들은 해시 테이블 구현에 사용되는 함수 포인터 타입을 정의한 것이다. 즉 우리는 위에 정의된 타입과 인자를 이용해 구현한 코드를 해시 테이블 초기화 시에 같이 사용해야 한다는 것이다. 자세한 내용은 pintos gitbook - APPENDIX - Hash Table 을 확인하라

• include/vm/vm.h

.
.
.
/* SPT 해시 테이블에 넣기 위한 hash_func & less_func 함수 선언 */
uint64_t page_hash(const struct hash_elem *e, void *aux);
bool page_less(const struct hash_elem *a, const struct hash_elem *b, void *aux);

#endif  /* VM_VM_H */

먼저 해시 함수를 정의했다. 이후 실제 vm.c 에서 구현을 진행하겠다.

• vm/vm.c

/* SPT 해시 테이블에 넣기 위한 hash_func & less_func 함수 구현 */

/* page_hash 가상 주소를 바탕으로 해시값을 계산한다. */
uint64_t page_hash(const struct hash_elem *e, void *aux){
	const struct page *p = hash_entry(e, struct page, hash_elem);
	return hash_bytes(&p->va, sizeof(p->va));
}

/* 두 page의 va를 기준으로 정렬을 비교한다. */
bool page_less(const struct hash_elem *a, const struct hash_elem *b, void *aux){
	/* 이 함수는 해시 테이블 충돌 시 내부 정렬에 사용된다고 한다. */
	struct page *pa = hash_entry(a, struct page, hash_elem);
	struct page *pb = hash_entry(b, struct page, hash_elem);
	return pa->va < pb->va;
}

page_hash()

• 해시 테이블의 각 요소 e에 대해 해시 값을 계산한다.
• aux는 보조 데이터로, 필요시 추가 정보를 넘겨줄 수 있다.
• 해시 테이블은 이 값을 기반으로 내부의 버킷(bucket)에 데이터를 배치한다.

page_less()

• 두 해시 요소 a, b 를 비교하여 정렬 기준을 제공한다.
• a 가 b 보다 작으면 true, 그렇지 않으면 false를 반환한다.
• 이는 충돌 해결 및 검색 최적화를 위해 해시 테이블 내부적으로 정렬 또는 비교할 때 사용한다.

---

spt_find_page 구현

• vm/vm.c

* 가상 주소를 통해 SPT에서 페이지를 찾아 리턴한다.
* 에러가 발생하면 NULL을 리턴 */
struct page *
spt_find_page (struct supplemental_page_table *spt UNUSED, void *va UNUSED) {

	/* TODO: Fill this function. */
	struct page key;
	key.va = pg_round_down(va);

	struct hash_elem *e = hash_find(&spt->pages, &key.hash_elem);
	return e != NULL ? hash_entry(e, struct page, hash_elem) : NULL;
}

spt_find_page는 주어진 가상 주소 va에 대응하는  page를 SPT에서 찾아서 반환하는 함수이다.

• pg_round_down(va) : 주소 va는 어떤 위치든 들어올 수 있지만, 페이지 단위로 관리하기 때문에 페이지의 시작 주소로 내림을 한다. 예를 들어 va = 0x8048123 이면 pg_round_down(va) = 0x8048000이 된다.

/* Round down to nearest page boundary. */
#define pg_round_down(va) (void *) ((uint64_t) (va) & ~PGMASK)

---

spt_insert_page 구현

• va/vm.c

 * PAGE를 spt에 삽입하며 검증을 수행한다. 
 * 가상 주소가 이미 존재하면 삽입하지 않는다. */
bool
spt_insert_page (struct supplemental_page_table *spt UNUSED, struct page *page UNUSED) 
{
	/* TODO: Fill this function. */
	return hash_insert(&spt->pages, &page->hash_elem) == NULL ? true : false;
}

spt_insert_page는 SPT에 새로운 page를 삽입하는 함수이다. 

/* Inserts NEW into hash table H and returns a null pointer, if
   no equal element is already in the table.
   If an equal element is already in the table, returns it
   without inserting NEW. */
struct hash_elem *
hash_insert (struct hash *h, struct hash_elem *new) {
	struct list *bucket = find_bucket (h, new);
	struct hash_elem *old = find_elem (h, bucket, new);

	if (old == NULL)
		insert_elem (h, bucket, new);

	rehash (h);

	return old;
}

• h에 new를 삽입하려고 시도한다.
• 이미 동일한 요소(키)가 존재하면, 삽입하지 않고 기존 요소의 포인터를 반환한다.
• 중복이 없으면 삽입하고 NULL을 반환한다. 즉 반환값이 NULL 이면 성공적으로 삽입되었다는 뜻이다.

return hash_insert(&spt->pages, &page->hash_elem) == NULL ? true : false;

결과적으로 해시 테이블에 요소를 삽입하려 했을 대 NULL이 반환되면 삽입에 성공했으니 ture를 값이 있다면 중복이니 false를 반환한다.

---

vm_get_frame 구현

• vm/vm.c

 * palloc()을 사용하여 프레임을 할당합니다.
 * 사용 가능한 페이지가 없으면 페이지를 교체(evict)하여 반환합니다.
 * 이 함수는 항상 유효한 주소를 반환합니다. 즉, 사용자 풀 메모리가 가득 차면,
 * 이 함수는 프레임을 교체하여 사용 가능한 메모리 공간을 확보합니다.*/
static struct frame *
vm_get_frame(void)
{
	/* TODO: Fill this function. */
	struct frame *frame = NULL;

	// 1. 유저 풀에서 새로운 페이지 할당
	void *kva = palloc_get_page(PAL_USER);

	// 2. 할당 실패 시 PANIC
	if (kva == NULL) {
		// 추후 페이지 교체를 추가해야 한다.
		PANIC("todo: implement eviction here");
	}

	// 3. 프레임 구조체 할당 및 초기화
	frame = (struct frame *)malloc(sizeof(struct frame)); 
	frame->kva = kva; // 프레임의 물리 주소 (kva는 물리 주소를 커널의 가상 주소로 1대 1로 매핑해 놓았다.)
	frame->page = NULL;

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

vm_get_frame() 은 물리 프레임을 할당하는 함수이다. 페이지를 메모리에 매핑하기 전에 사용할 물리 메모리 공간을 확보하는 역할이다.

struct frame {
    void *kva;           // 커널 가상 주소 (실제 물리 프레임 주소)
    struct page *page;   // 이 프레임을 사용하는 가상 페이지
};

• PAL_USER 플래그를 통해 사용자 영역 메모리 풀에서 1페이지(4KB)를 할당받는다. kva는 물리주소와 1대 1 매핑된 커널 가상 주소다.
• 현재는 kva가 없을 경우 커널 패닉을 발생 시킨 다 추후 Swap in/out 구현 시 eviction(페이지 교체)를 구현해서 대체할 예정이다.
• 새로운 frame 구조체를 malloc으로 생성한다. kva는 물리 프레임 주소이고 page는 아직 이 프레임을 사용하는 가상 페이지가 없으므로 NULL로 설정한다.

---

vm_do_claim_page 구현

• vm/vm.c

 * 인자로 주어진 page에 frame을 할당 한다. --> vm_get_frame()
 * mmu를 설정한다.(pml4) */
static bool
vm_do_claim_page (struct page *page) 
{
	void *temp = page->operations->swap_in;
 	struct frame *frame = vm_get_frame();

	/* TODO: vm_get_frame이 실패하면 swap_out */
	
	/* Set links */
	frame->page = page;
	page->frame = frame;

	if (!swap_in(page, frame->kva))
        return false;

	/* TODO: Insert page table entry to map page's VA to frame's PA. */
	/* 페이지의 VA와 프레임의 KVA를 페이지 테이블에 매핑 */
    if (!pml4_set_page(thread_current()->pml4, page->va, frame->kva, page->writable))
      return false;

    return true;
}

vm_do_claim_page 는 가상 페이지를 실제 메모리에 물리적으로 연결(매핑) 하는 과정을 수행한다.

즉, 가상 주소 공간에서 페이지 폴트가 발생했을 때:

• 실제로 사용할 물리 프레임을 할당하고
• 그 페이지의 내용을 메모리에 로드하며 (필요하면 swap-in)
• 가상 주소를 물리 주소에 매핑(MMU 설정)하는 함수다.

frame->page = page;
page->frame = frame;

• 가상 페이지와 물리 프레임이 서로를 참조하도록 설정
• 이는 추후 프레임 교체(eviction) 시에도 중요한 연결 정보

if (!swap_in(page, frame->kva))
    return false;

• 페이지가 디스크(swap 영역 또는 파일 시스템 등)에 존재하는 경우, 데이터를 프레임에 로드
• 실패 시 false 반환 → 메모리에 데이터를 올리는 데 실패

if (!pml4_set_page(thread_current()->pml4, page->va, frame->kva, page->writable))
    return false;

• 현재 스레드의 4단계 페이지 테이블(pml4)에 가상 주소 va를 물리 주소 kva에 매핑
• page->writable에 따라 읽기 전용 또는 읽기/쓰기 권한 설정

---

vm_claim_page 구현

• vm/vm.c

 * VA에 해당하는 페이지를 가져온다. 
 * 해당 페이지로 vm_do_claim_page를 호출한다. */
bool
vm_claim_page (void *va UNUSED) 
{
	/* TODO: Fill this function */
	struct page *page = NULL;
	page = spt_find_page(&thread_current()->spt, va);
	if (page == NULL){
		return false;
	}
	return vm_do_claim_page (page);
}

 

vm_claim_page는 가상 주소 va에 해당하는 페이지를 메모리에 올리는(할당하고 매핑하는) 역할을 한다.

• 페이지 폴트가 발생했을 때 이 함수가 va에 해당하는 페이지 정보를 SPT에서 찾는다.
• 해당 페이지를 물리 메모리에 할당 및 매핑한다.

---

여기 까지가 Memory Management의 구현 내용이다. 다음 포스팅에서는 Anonymous Page 부분을 구현할 것이다. 다음 포스팅까지 구현을 진행하면 테스트가 돌아가기 시작할 것이다.