[PintOS - VM] Memory Management

Implement Supplemental Page Table

 

• 현재 Pintos 시스템은 메모리의 가상 주소와 물리 주소 매핑을 관리하는 페이지 테이블(pml4)을 가지고 있습니다.
• 앞 장의 논의처럼, Page Fault Handle 과  자원 관리를 위해 각 페이지에 대한 추가 정보를 저장하는 supplementary page table이  필요합니다.
• 따라서 프로젝트 3의 첫 번째 작업으로 supplementary page table의 기본 기능을 구현합시다!

1) SPT의 자료구조 선택 .

/* 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 hash_brown;
};

 

spt를 어떻게 구현할지는 우리에게 달렸다는 주석이 있다. 하지만 우리는 아래와 같은 이유로 Hash를 쓸 것이다!

1. PPT에서 SPT를 Hash 기준으로 아주 잘 설명하고 있음.
2. 지금껏 PintOS에서 Hash 자료구조를 사용한 적이 없음.

또한, 나는 해쉬브라운을 좋아하기에 hash 이름을 hash_brown으로 설정했다! 🥔

 

2) hash_init 및 매개변수 설정 .

void
supplemental_page_table_init (struct supplemental_page_table *spt UNUSED) {
//  hash_init(struct hash *, hash_hash_func *, hash_less_func *, void *aux)
	hash_init(&spt->hash_brown,vm_hash_func,vm_less_func,NULL);
}

 

 

여기서 hash_init은 hash_hash_func 와 hash_lees_func 매개변수를 요구하고 있다. 매개변수로 함수를 받는다니... 궁금하니 한 번 찾아보자!

 

/* Computes and returns the hash value for hash element E, given

* auxiliary data AUX. */

typedef uint64_t hash_hash_func (const struct hash_elem *e, void *aux);

/* Compares the value of two hash elements A and B, given

* auxiliary data AUX. Returns true if A is less than B, or

* false if A is greater than or equal to B. */

typedef bool hash_less_func (

         const struct hash_elem *a,

         const struct hash_elem *b,

         void *aux);

 

hash_hash_func 함수의 주석을 보면,주어진 hash_elem에 대해서, 보조 데이터인 aux를 활용하여 정숫값(uint64)인 hash_value를 반환한다고 되어있다.

 

gitbook에는 아래와 같이 가이드가 되어있다.

hash_hash_func와 hash_bytes 함수에 대한 가이드.

 

 

결과적으로, 아래와 같이 hash_elem을 이용하여 page를 구하고, 그 page의 va를 읽어서 hash_value 를 구해오면 됩니다!

/* 주어진 페이지 *p 에 대한 해시값을 리턴합니다. */
static
unsigned
vm_hash_func (const struct hash_elem *p_, void *aux UNUSED) {
	/* hash_entry()로 element에 대한 vm_entry 구조체 (ppt에서는 struct page를 vm_entry라고 부른다) */
	/* hash_bytes()를 이용해서 vm_entry의 멤버 vaddr에 대한 해시값을 구하고 반환 */
	const struct page *p = hash_entry(p_, struct page, hash_elem);
	return hash_bytes(&p->va, sizeof(p->va));
}

 

hash_less_func 함수의 주석을 보면, 이전 단원에서 처럼 두 값(a 와 b의 aux)을 비교하고, a가 b 보다 작으면 true를, 아니면 false를 반환하는 함수이다.

 

gitbook에는 아래와 같이 가이드가 되어있다.

 

PPT 설명에 따라서 va 값을 비교 후 리턴하였다.

static
unsigned vm_less_func (const struct hash_elem *a, const struct hash_elem *b, void *aux) {
	/* PPT 설명 주석*/
	/* hash_entry()로 각각의 element에 대한 vm_entry 구조체를 얻은
	후 vaddr 비교 (b가 크다면 true, a가 크다면 false */
	const struct page *p_a = hash_entry(a, struct page, hash_elem);
	const struct page *p_b = hash_entry(b, struct page, hash_elem);
	return p_a->va < p_b->va;
}

 

 

3) spt_find_page

struct page *spt_find_page (struct supplemental_page_table *spt, void *va);

 

우선, 위 함수의 매개변수와 리턴 타입을 살펴보자.

• 리턴타입 : struct page *
• 매개변수 : struct  supplemental_page_table *spt UNUSED, void *va UNUSED

이제 이것을 아래와 같이 요약해보자.

1. spt 테이블이서
2. va를 갖고
3. page를 리턴해라!

 

하지만 막상 구현하려고 하니 너무 막막하다..... 이럴 땐 hash.c 코드를 보며 적절한 built-in 함수가 있는지 찾아보자 ! ㄱㄱ 😼

 

 

hash_find

우선 hash_find 라는 녀석이 눈에 걸린다. find_elem 으로 한 번 더 들어가보자!

/* Finds and returns an element equal to E in hash table H, or a
   null pointer if no equal element exists in the table. */
struct hash_elem *
hash_find (struct hash *h, struct hash_elem *e) {
	return find_elem (h, find_bucket (h, e), e);
}

 

find_elem

/* Searches BUCKET in H for a hash element equal to E.  Returns
   it if found or a null pointer otherwise. */
static struct hash_elem *
find_elem (struct hash *h, struct list *bucket, struct hash_elem *e) {
	struct list_elem *i;

	for (i = list_begin (bucket); i != list_end (bucket); i = list_next (i)) {
		struct hash_elem *hi = list_elem_to_hash_elem (i);
		if (!h->less (hi, e, h->aux) && !h->less (e, hi, h->aux))
			return hi;
	}
	return NULL;
}

 

1. bucket 이라는 hash를 담은 list에서
2. less (이전에 작성한 비교함수)와 aux 값을 비교한 후
3. 동일한 aux 값을 발견하면, hash_elem을 리턴하고 있다.

그렇다면, spt_find_page 함수에서 매개변수로 받은 va를 활용하여 hash_elem을 구할 수 있고,

hash_entry() 매크로를 사용하여 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) {

	//  인자로 받은 vaddr에 해당하는 vm_entry를 검색 후 반환
	//  가상 메모리 주소에 해당하는 페이지 번호 추출 (pg_round_down())
	//  hash_find() 함수를 이용하여 vm_entry 검색 후 반환

	struct page *page = NULL;
    /* TODO: Fill this function. */
	page = (struct page *)malloc(sizeof(struct page));
    struct hash_elem *e;

    // va에 해당하는 hash_elem 찾기
    page->va = pg_round_down(va);
    e = hash_find(&spt->hash_brown, &page->hash_elem);
	// /* 우린 분명 page.va = va; 를 업데이트 하였다. 그런데 어떻게 해서 위의 hash_find 이 동작하는걸까? */
	// /* va를 건내주고, bucket 리스트에 있는 hash들을 순회하며 va가 같은 hash_elem을 가져온다. */
	// /* 사실 elem에 아무것도 설정되지 않아서 이상한 코드처럼 보이지만, 내부 find elem에서 va를 비교한 후 elem을 리턴한다.*/
	free(page);
    // 있으면 e에 해당하는 페이지 반환
    return e != NULL ? hash_entry(e, struct page, hash_elem) : NULL;
}

 

4) spt_insert_page()

bool spt_insert_page (struct supplemental_page_table *spt, struct page *page);

 

 

아래와 같이 단순히 hash_insert() 함수를 호출하였다.

/* Insert PAGE into spt with validation. */
bool
spt_insert_page (struct supplemental_page_table *spt UNUSED,
		struct page *page UNUSED) {
	int succ = false;
	// Insert struct page into the given supplemental page table. 
	// This function should checks that the virtual address does not exist in the given supplemental page table.
	// hash_insert -> 
	// succ = page_insert(&spt->hash_brown, page);
	// return succ;
	return hash_insert(&spt->hash_brown,&page->hash_elem) == NULL ? true : false;
}

 

return 값이 지저분해 보이는데, 그 이유는 hash_insert 함수의 주석을 보면 알 수 있다.

 

/* 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. */

 

주석을 보면 hash table에 새로운 요소를 집어넣되, "성공" 하면 true를, 그렇지 않으면 해당 주솟값을 리턴한다고 한다.

 

따라서 hash_insert가 성공적으로 요소를 집어넣어서 Null을 반환하면 true를, 그렇지 않으면 false를 리턴하였다.

 

 

Frame Management

/* The representation of "frame" */
struct frame {
	void *kva;
	struct page *page;  // 점유중인 페이지를 가르키는 포인터.
	struct list_elem frame_elem; // 추후, 추방정책을 위해 frame을 관리할 리스트.
};

 

5) vm_get_frame

static struct frame *vm_get_frame (void);

 

palloc_get_page(PALLOC_USER) 를 사용하여, frame을 생성 후 반환해야합니다.

1. 반드시! user pool을 사용하여 생성하고
2. 적절한 초기화를 진행하며 (frame->page = NULL)
3. 현 시점에서 추방 정책은 고려하지 않고 진행합니다.

static struct frame *
vm_get_frame (void) {
	struct frame *frame = (struct frame *)malloc(sizeof(struct frame));;
	/* TODO: Fill this function. */
	frame->kva = palloc_get_page(PAL_USER);

	if(frame->kva == NULL) {
		PANIC("todolater"); // 추방알고리즘 
	}
	/* 밑에 dealloc 함수가 있어서, free는 신경안써도 되는거같다. */
	frame->page = NULL; // ASSERT (frame->page == NULL); 가 있으므로, NULL로 초기화 해줍시다!
	list_push_back(&frame_list,&frame->frame_elem);
	ASSERT (frame != NULL);
	ASSERT (frame->page == NULL);
	return frame;
}

 

 

6) vm_do_claim_page

bool vm_do_claim_page (struct page *page);

 

Claims, meaning allocate a physical frame, a page. You first get a frame by calling vm_get_frame (which is already done for you in the template). Then, you need to set up the MMU. In other words, add the mapping from the virtual address to the physical address in the page table. The return value should indicate whether the operation was successful or not.

/* 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;
	page->frame = frame;
	
	/* TODO: Insert page table entry to map page's VA to frame's PA. */
	struct thread *t = thread_current();
	pml4_set_page (t->pml4, page->va, frame->kva, page->writable);

	return swap_in (page, frame->kva);
}

 

1. 앞서 구현한 vm_get_frame 을 활용하여 frame을 얻어온다.
2. va와 frame을 연결한다!
3. 성공 여부를 반환한다.

말로만 들으면 엄청 쉽다.. 그런데 va 와 frame을 어떻게 연결하지..?! 깃북 가이드에 MMU에 대한 언급이 있었으니, MMU.c를 훑어보자.

 

pml4_set_page -> pml4e_walk -> pdpe_walk -> pgdir_walk 순회

pml4_set_page는 va <-> frame을 연결해줍니다!

 

pml4_set_page를 호출하는 것 만으로도, 아래의 복잡한 과정이 한 번에 해결됩니다! 또한, 각 가상 주소의 Table이 존재하지 않으면 create 또한 자동으로 된답니다! 

 

 

7) vm_claim_page

bool vm_claim_page (void *va);

 

아래와 같이 va를 활용하여 page를 얻어오고, vm_do_claim_page를 호출만 해주면 된다!!

/* Claim the page that allocate on VA. */
bool
vm_claim_page (void *va UNUSED) {
	struct page *page = NULL;
	/* TODO: Fill this function */
	// printf("vm_claim_page 잘 오나요? \n");
	page = spt_find_page(&thread_current()->spt, va);
	if (page == NULL) {
		return false;
	}
	return vm_do_claim_page (page);
}