PintOS Project3 : Memory Management

https://oslab.kaist.ac.kr/pintosslides/

 

Implement Supplemental Page Table

 

가장 먼저 구현해야 할 것은 Supplemental Page Table이다.

 

기존에 핀토스에서는 pml4라는 페이지 테이블을 제공하고 있지만 가상 메모리를 구현하기에는 그 역할이 부족하다.

pml4의 경우 주어진 va에 대해 실제 kva(물리메모리)로의 단순한 변환만을 해주고 있다.

 

즉, 우리가 사용할 페이지라는 구조체의 정보에 대한 어떠한 정보도 가지고 있지 않다.

그래서 SPT는 각각의 페이지에 대한 정보를 추가적으로 보충해주는 역할을 수행한다.

 

SPT의 목적

1) 페이지 폴트가 발생했을 경우 해당 페이지 폴트가 발생한 페이지를 찾을 수 있고, 우리가 찾은 페이지가 가지고 있는 여러 가지 데이터들에 접근하기 위해서다.

2) 커널이 프로세스(쓰레드)를 종료시킬 때, 해당 SPT를 참고하여 어떠한 데이터들이 할당 해제되어야 할 지를 결정한다. 

 

👉🏻페이지 폴트가 일어난 가상 주소(va)를 포함하는 페이지 구조체가 있는데 이 구조체에 접근해 다양한 데이터들을 사용하기 위해 사용하는 것이다. (va를 이용해서 페이지를 찾고 할당할 수 있다.)

 

SPT를 구현하기 위해 어떤 자료 구조(배열, 리스트, 비트맵, 해시 테이블)로 구현할지를 정하라고 하는데 해시 테이블로 구현하였다. 

 

1) struct supplmental_page_table

 

supplemental_page_table에 hash 구조체를 추가한다.

/*vm.h*/

struct supplemental_page_table {
	struct hash hash_table;
};

 

page 구조체에 hash_elem을 추가한다.

/*vm.h*/

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 hash_elem;	/*Hash table element*/
 	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
	};
};

 

 

2) supplemental_page_table_init()

•  spt를 초기화해주는 역할을 수행한다.

 

•  hash table로 spt를 구현하였기 때문에 hash_init() 함수를 통해 초기화해준다.

•  이 함수는 새로운 프로세스가 시작될 때(userprog/process.c의 initd함수) 와 프로세스가 포크될 때 (procees.c의 __do_fork함수) 호출된다.

/*vm.c*/

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

 

2-1) page_hash, page_less

•  hash_init을 하기 위해선 page_hash , page_less 함수를 선언해야 한다.

 

•  page_hash() 

해시테이블에서는 특정 키를 해시값으로 변환하여 해당 해시값에 대응하는 버킷에 데이터를 저장하는데 이를 위해 키의 해시값을 계산하는 함수가 필요하다.

hash_byte 함수는 주어진 데이터에 대한 해시값을 계산하고 주소와 크기를 인자로 받아 페이지 주소를 해시값으로 변환한다. 

 

•   page_less()

비교 함수를 사용하여 해시테이블을 생성하면, 특정 가상 주소에 대한 페이지를 해시 테이블에 삽입하거나 검색할 때 페이지의 가상 주소를 기준으로 페이지를 정렬할 수 있다.

/*hash.c*/

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


bool page_less (const struct hash_elem *a, const struct hash_elem *b, void *aux)
{
	const struct page *pa = hash_entry(a, struct page, hash_elem);
	const struct page *pb = hash_entry(b, struct page, hash_elem);

	return pa->va < pb->va;
}

 

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

typedef bool hash_less_func (const struct hash_elem *a, const struct hash_elem *b, void *aux);

 

hash_hash_func 함수 포인터는 해시 테이블에서 요소를 해싱하는 데 사용될 함수를 가리키고,

hash_less_func 함수 포인터는 해시 테이블에서 요소를 비교하는 데 사용된다.

이러한 함수 포인터 타입을 정의함으로써, 자신만의 해시 함수와 비교 함수를 구현하여 해시 테이블에 사용할 수 있게 해야 한다.

 

이 부분에서 자신만의 해시 함수와 비교 함수를 만들지 않고 함수 포인터의 이름을 고대로 가져다 쓰는 바보같은 짓을 해서 애를 잠깐 먹었었따..

 

 

3) spt_find_page()

supplementary page table 로부터 가상주소(va)에 대응되는 페이지 구조체를 찾아서 반환한다.

supplementary page table의 value에는 페이지가 아닌 페이지 구조체의 멤버인 hash_elem이 들어간다.

그래서 우리는 간접적으로 페이지를 찾아올 수 있다. (hash_entry 사용)

 

하나의 더미 페이지를 할당(malloc) 시킨 후 , 해당 페이지의 va를 주어진 인자로 설정한 다음 더미 페이지의 hash_elem을 통해 우리가 찾으려는 페이지를 검색한다.

 

🤔더미 페이지를 할당하는 이유

메모리 주소 공간을 확보하고, 해당 페이지를 특정 데이터나 자료구조에 매핑하여 메모리 관리를 용이하게 함이다.

더미 페이지를 할당하고, 그 안에 데이터를 저장하고,이를 해시 테이블의 엔트리에 연결한다.

/*vm.c*/

/* Find VA from spt and return page. On error, return NULL. */
/* spt로부터 VA를 찾고 페이지를 반환합니다. 에러인 경우 NULL을 반환합니다. */
struct page *
spt_find_page(struct supplemental_page_table *spt UNUSED, void *va UNUSED)
{
	struct page *page = malloc(sizeof(struct page));
	struct hash_elem *e;
	if (page == NULL)
	{
		return NULL;
	}
	
   	 //va에 해당하는 hash_elem 찾기
	page->va = pg_round_down(va);
	e = hash_find(&spt->hash_table, &page->hash_elem);
	
   	 //있으면 e에 해당하는 페이지 반환
	if (e != NULL)
	{
		struct page *found_page = hash_entry(e, struct page, hash_elem);
		free(page);
		return found_page;
	}
	else
	{
		free(page);
		return NULL;
	}
}

 

 

4) spt_insert_page()

인자로 주어진 supplementary page table에 페이지 구조체를 삽입한다. 

이 함수에서 주어진 supplementary page table 에서 가상 주소가 존재하지 않는지 검사해야 한다.

 

만약 spt에 존재한다면 삽입하지 않고, 존재하지 않으면 삽입한다.

/*vm.c*/

/* Insert PAGE into spt with validation. */
/* 페이지를 유효성 검사를 거쳐 spt에 삽입합니다. */
bool spt_insert_page(struct supplemental_page_table *spt UNUSED, struct page *page UNUSED)
{
	int succ = false;

	if (is_user_vaddr(page->va))
	{
		if (spt_find_page(spt, page->va) == NULL)
		{
			hash_insert(&spt->hash_table, &page->hash_elem);
			succ = true;
		}
	}
	return succ;
}

 

 

Frame Management

물리 메모리를 관리하는 frame 을 구현해야 한다.

 

5) vm_get_frame()

palloc_get_page 함수를 호출하여 사용자 풀에서 새로운 물리 페이지(frame)를 가져온다.

👉🏻 palloc_get_page - 물리 페이지를 할당하고, 해당 페이지의 커널 가상 주소를 반환하는 함수

 

사용자 풀에서 페이지를 성공적으로 가져오면, 프레임을 할당하고 프레임 구조체의 멤버를 초기화한 후 해당 프레임에 반환한다.

 

페이지 할당이 실패했을 경우 지금은 PANIC("todo")로 표시한다. (swap out 구현 후 변경)

/*vm.c*/

static struct frame *
vm_get_frame(void)
{
	struct frame *frame = (struct frame*)malloc(sizeof(struct frame)); 
	/* TODO: Fill this function. */
   	// user_pool 에서 frame 가져오고, kva return해서 frame에 넣어준다.
	frame->kva = palloc_get_page(PAL_USER);
	
	if(frame->kva == NULL){ //frame에서 가용한 page가 없다면
		free(frame);
		PANIC("todo");
	}

	frame->page = NULL; //새 frame을 가져왔으니 page의 멤버를 초기화
	
	ASSERT (frame != NULL);
	ASSERT (frame->page == NULL);
	return frame;
}

 

 

6) vm_do_claim_page()

인자로 주어진 page에 물리 메모리 프레임을 할당한다.

먼저, vm_get_frame 함수를 호출함으로써 프레임 하나를 가져온다.

그런 다음 MMU를 설정한다.

  → 가상 주소와 물리 주소를 매핑한 정보를 페이지 테이블에 추가해야 한다는 것을 의미

/*vm.c*/

/* Claim the PAGE and set up the mmu. */
/* 페이지를 청구하고 mmu를 설정합니다.
   실질적으로 frame과 인자로 받은 page를 연결해주는 역할 수행.
   -> 해당 페이지가 이미 어떠한 물리 주소(kva)와 미리 연결이 되어 있는지 확인해야 한다.
   -> 이후 미리 연결된 kva가 없을 경우, 해당 va를 kva에 set해준다. */
static bool
vm_do_claim_page(struct page *page)
{
	struct frame *frame = vm_get_frame();
	if (frame == NULL)
	{
		return false;
	}

	/* Set links */
	frame->page = page;
	page->frame = frame;

	/* TODO: Insert page table entry to map page's VA to frame's PA. */
	/* 페이지 테이블 항목을 삽입하여 페이지의 VA를 프레임의 PA에 매핑합니다. */
	/* pml4_get_page는 가상주소를 넣어 해당 물리주소를 찾고 그에 해당하는
	커널 가상 주소를 반환한다.*/
	/* pml4_set_page는 사용자 가상 페이지 UPAGE에서 커널 가상 주소 KPAGE로 
	식별된 물리 프레임에 대한 페이지 맵 레벨 4 PML4에 매핑을 추가한다. */

	//가상 주소와 물리 주소 매핑
	if (pml4_get_page(thread_current()->pml4, page->va) == NULL)
	{
		if (!pml4_set_page(thread_current()->pml4, page->va, frame->kva, page->writable))
		{
			vm_dealloc_page(page);
			return false;
		}
	}
	/* 해당 페이지를 물리 메모리에 올려준다.*/
	return swap_in(page, frame->kva);
}

 

 

7) vm_claim_page()

인자로 주어진 va에 페이지를 할당하고, 해당 페이지에 프레임을 할당한다.

 

우선 한 페이지를 얻어야 하고 그 이후에 해당 페이지를 인자로 갖는 vm_do_claim_page 함수를 호출한다.

/*vm.c*/

/* Claim the page that allocate on VA. */
/* VA(페이지의 가상 메모리 주소)를 통해 페이지를 얻어온다. */
bool vm_claim_page(void *va UNUSED)
{
	struct page *page = NULL;

	/* 물리 프레임과 연결을 할 페이지를 SPT를 통해서 찾아준다.*/
	page = spt_find_page(&thread_current()->spt, va);

	if (page == NULL)
		return false;
	return vm_do_claim_page(page);
}