(2022.02.22) Memory Mgmt 가이드라인 (1/2)

아마 해당 주제의 포스팅이 개강 전 마지막 포스팅이 될 것 같다. 실제 코딩은 대전 내려가서 해야할 듯.... 좀 길어질 것 같아 2개로 포스팅을 나누려고 한다.

 

우선 포스팅을 작성하다보니 struct page 구조체와 실제로 메모리상에서 4kB의 공간을 차지하고 있는 page 용어가 헛갈릴 수 있겠다는 생각이 들어 struct page는 "페이지_정보_구조체"로, page는 "페이지"로 표기하기로 한다. 

 

모든 페이지의 수월한 관리를 위해서 pintos는 해당 페이지의 종류, 연결된 프레임 등의 정보를 저장하고 있어야 한다. 이를 위해 pintos에서는 struct page(후술 페이지_정보_구조체)라는, 다음과 같은 구조체를 각 페이지마다 생성해서 관리한다. 해당 구조체에 미리 들어가 있는 것들은 수정이 불가하다.

/* The representation of "page".
 * This is kind of "parent class", which has four "child class"es, which are
 * uninit_page, file_page, anon_page, and page cache (project4).
 * DO NOT REMOVE/MODIFY PREDEFINED MEMBER OF THIS STRUCTURE. */
struct page {
	const struct page_operations *operations;
	void *va;              /* Address in terms of user space */
	struct frame *frame;   /* Back reference for frame */

	/* Your implementation */

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

각 페이지_정보_구조체는 프로젝트 3까지 이전 포스팅에서 잠깐 언급했다시피 VM_UNINIT, VM_ANON, VM_FILE의 3가지 종류로 구분할 수 있다. 해당 분류는 연동된 페이지가 어디서부터 기원했고, 어떤 용도로 사용되는지를 구분할 때 사용되며, 그 종류에 따라 페이지_정보_구조체의 생성 및 파괴 루틴이 달라져야 하기에 해당 정보를 토대로 구분한다.

 

구체적으로 각 종류별로 어떻게 다른 것인지를 알아보자. 먼저 vm_type에 서술된 주석은 다음과 같고,

enum vm_type {
	/* page not initialized */
	VM_UNINIT = 0,
	/* page not related to the file, aka anonymous page */
	VM_ANON = 1,
	/* page that realated to the file */
	VM_FILE = 2,
	...
}

각 vm_type과 관련된 함수들이 정의된 uninit.c, anon.c, file.c를 살펴보면 아래의 주석을 확인할 수 있다.

/* uninit.c: Implementation of uninitialized page.
 *
 * All of the pages are born as uninit page. When the first page fault occurs,
 * the handler chain calls uninit_initialize (page->operations.swap_in).
 * The uninit_initialize function transmutes the page into the specific page
 * object (anon, file, page_cache), by initializing the page object,and calls
 * initialization callback that passed from vm_alloc_page_with_initializer
 * function.
 * */

/* anon.c: Implementation of page for non-disk image (a.k.a. anonymous page). */

/* file.c: Implementation of memory backed file object (mmaped object). */

이들을 토대로 정리하면:

1) VM_UNINT

모든 페이지_정보_구조체는 해당 종류로 생성된다. 페이지_정보_구조체를 생성하려면 vm_alloc_page_with_initializer라는 함수를 사용하라고 스켈레톤 코드에 나와 있으며, 해당 함수와 주석은 아래와 같다.

/* Create the pending page object with initializer. If you want to create a
 * page, do not create it directly and make it through this function or
 * `vm_alloc_page`. */
bool
vm_alloc_page_with_initializer (enum vm_type type, void *upage, bool writable,
		vm_initializer *init, void *aux) {

	ASSERT (VM_TYPE(type) != VM_UNINIT)

	struct supplemental_page_table *spt = &thread_current ()->spt;

	/* Check wheter the upage is already occupied or not. */
	if (spt_find_page (spt, upage) == NULL) {
		/* TODO: Create the page, fetch the initialier according to the VM type,
		 * TODO: and then create "uninit" page struct by calling uninit_new. You
		 * TODO: should modify the field after calling the uninit_new. */

		/* TODO: Insert the page into the spt. */
	}
err:
	return false;
}

해당 함수에서는 주어진 upage에 대응하도록 페이지_정보_구조체를 생성한 뒤, 우리가 만들 spt (supplemental page table)에 할당한다. 이 때, 코드 앞 부분에 ASSERT (VM_TYPE(type) != VM_UNINIT)이 있는 것을 볼 때, 이 함수의 입력으로 들어올 수 있는 것은 VM_ANON과 VM_FILE 뿐이며, VM_UNINIT은 임의로 생성할 수 있는 것이 아닌, 시스템 상 임시로만 존재하는 종류라는 것을 알 수 있다. 

 

아직 헷갈리는 것은 uninit.c에 있는 두 주요한 함수의 차이다.

/* DO NOT MODIFY this function */
void
uninit_new (struct page *page, void *va, vm_initializer *init,
		enum vm_type type, void *aux,
		bool (*initializer)(struct page *, enum vm_type, void *)) {
	ASSERT (page != NULL);

	*page = (struct page) {
		.operations = &uninit_ops,
		.va = va,
		.frame = NULL, /* no frame for now */
		.uninit = (struct uninit_page) {
			.init = init,
			.type = type,
			.aux = aux,
			.page_initializer = initializer,
		}
	};
}

/* Initalize the page on first fault */
static bool
uninit_initialize (struct page *page, void *kva) {
	struct uninit_page *uninit = &page->uninit;

	/* Fetch first, page_initialize may overwrite the values */
	vm_initializer *init = uninit->init;
	void *aux = uninit->aux;

	/* TODO: You may need to fix this function. */
	return uninit->page_initializer (page, uninit->type, kva) &&
		(init ? init (page, aux) : true);
}

코드에 사용된 위치를 토대로 생각한 결과는 다음과 같다. uninit_new는 주어진 페이지_정보_구조체 내에 initialize에 필요한 정보를 우선적으로 담는 역할이다. 이에 비해 uninit_initialize는 주어진 페이지_정보_구조체에 담겨진 정보를 토대로 해당 구조체와 연동된 페이지를 initialize 시키는 역할을 한다. 크게 두 가지 정보(함수)가 주어진다. 하나는 구조체의 종류 자체를 VM_ANON이나 VM_FILE로 만들기 위해 추가적으로 필요한 루틴을 수행하기 위한 page_initializer이다. 다른 하나는 페이지_정보_구조체와 연동된 페이지 자체에 담겨져 있어야 할 내용 등을 설정하기 위한 vm_initializer(uninit_initialze에서는 init)이다. 포X몬으로 따지면 uninit_new는 진화 전의 이브이(페이지_정보_구조체)와 진화에 사용될 돌(initializer)을 준비하는 것이며, uninit_initialize는 준비된 이브이를 실제로 진화시키는 것이라고 할 수 있겠다. 

 

왜 이렇게 번거롭게 나눠놨을까 하고 생각을 해 봤다. 고민한 결과 페이지_정보_구조체를 할당해 임시 매핑을 만드는 시점과 페이지를 실제로 할당해야 할 시점을 따로 잡아 놓으면 이점이 있어서이다. 유저 프로세스가 특정 주소에 접근하기 전까지는 페이지 할당을 실제로 하지 않고 매핑이 존재한다는 것만 페이지_정보_구조체를 통해 정보를 남겨 놓으면 시간/공간 상의 이점을 챙길 수 있다. 이 때 불리는 함수가 vm_alloc_page_with_initialize이며, 해당 함수가 불리는 시점에 페이지의 실제 할당과 매핑은 되지 않는다. spt로 "임시 매핑"은 존재하지만 pml4 상으로는 valid하지 않는 주소이므로, 후에 해당 주소로 접근할 때는 page fault가 나게 될 것이다. 이 때, 다음 함수들에서 페이지_정보_구조체 내의 swap_in이 호출되며, uninit_initialze가 발동된다.

/* Return true on success */
bool
vm_try_handle_fault (struct intr_frame *f UNUSED, void *addr UNUSED,
		bool user UNUSED, bool write UNUSED, bool not_present UNUSED) {
	struct supplemental_page_table *spt UNUSED = &thread_current ()->spt;
	struct page *page = NULL;
	/* TODO: Validate the fault */
	/* TODO: Your code goes here */

	return vm_do_claim_page (page);
}

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

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

/* uninit.c */
/* DO NOT MODIFY this struct */
static const struct page_operations uninit_ops = {
	.swap_in = uninit_initialize,
	.swap_out = NULL,
	.destroy = uninit_destroy,
	.type = VM_UNINIT,
};

그럼 비로소 페이지_정보_구조체의 종류는 실제 용도로 활용될 종류로 변환되며, pml4을 통한 실제 할당 및 매핑과 함께 반환되는 것이다.

 

현재까지 사용된 메모리 할당 및 매핑은 모두 요청된 즉시 이루어졌으며, 이를 eager loading이라고도 한다. 이와 비교해 앞으로 구현될 방식은 요청 시점과 할당 및 매핑 시점이 분리되어 실제로 필요한 시점에 할당 및 매핑이 이루어지므로 lazy loading이라고 한다. 이를 구현하는 것이 프로젝트 3의 1차적 목표이기도 한 만큼 중요한 개념이다. 

 

요약하자면 VM_UNINIT은 가장 처음 page fault가 날 때 실제 사용될 용도로 구조체를 변화시키기 전 임시적으로 사용되는 type이다. 물론, 해당 페이지에 접근하지 않고 종료되는 경우에 해당 페이지_정보_구조체와 관련된 자원을 해제시킬 경우가 있으므로, 이를 위한 uninit_destroy도 존재한다.

 

VM_UNINIT 종류의 페이지는 그야말로 임시적인 페이지 종류이기 때문에 연결된 프레임이 존재할 수 없다. 만약 연결이 됐으면 다른 페이지 종류로 변환됐을 것이다. 때문에 물리 메모리가 부족해 프레임 중 하나를 골라 없애는 eviction에서 자유로우며, 이때 호출되는 swap_out 함수도 NULL로 설정된 것을 알 수 있다.

2) VM_ANON

본격적으로 임시 type이 아닌 페이지 종류이다. 해당 페이지 종류는 anonymous page를 나타내는 것으로, 이에 대한 정보를 보면 non-disk image에 해당하는 페이지, 파일과 연관되어 있지 않은 페이지를 나타낸다고 한다. 현재 pintos 내에서 VM_ANON을 찾아보면 유의미한 결과가 딱 하나 나온다.

static bool
load_segment (struct file *file, off_t ofs, uint8_t *upage,
		uint32_t read_bytes, uint32_t zero_bytes, bool writable) {
	ASSERT ((read_bytes + zero_bytes) % PGSIZE == 0);
	ASSERT (pg_ofs (upage) == 0);
	ASSERT (ofs % PGSIZE == 0);

	while (read_bytes > 0 || zero_bytes > 0) {
		/* Do calculate how to fill this page.
		 * We will read PAGE_READ_BYTES bytes from FILE
		 * and zero the final PAGE_ZERO_BYTES bytes. */
		size_t page_read_bytes = read_bytes < PGSIZE ? read_bytes : PGSIZE;
		size_t page_zero_bytes = PGSIZE - page_read_bytes;

		/* TODO: Set up aux to pass information to the lazy_load_segment. */
		void *aux = NULL;
		if (!vm_alloc_page_with_initializer (VM_ANON, upage,
					writable, lazy_load_segment, aux))
			return false;

		/* Advance. */
		read_bytes -= page_read_bytes;
		zero_bytes -= page_zero_bytes;
		upage += PGSIZE;
	}
	return true;
}

process_exec때 호출되는 load에서 불리는 함수인데, 프로젝트 3 이후에는 기존 load_segment와 달리 위에 설명한 lazy loading을 활용해 페이지를 할당한다. executable의 loading 외에도 후에 stack growth를 위해 페이지를 할당할 때도 anonymous page를 할당하는 등, 파일과 연관이 되어 있지 않은 페이지를 할당할 때는 모두 VM_ANON 종류를 할당한다. 근데 executable은 파일로 취급 안 하는건가

 

만약 메모리의 공간이 부족해 VM_ANON에 해당되는 페이지에 연결된 프레임이 evict 당했을 경우, 기반이 되는 파일이 없기에 해당 정보를 어딘가에는 임시로 저장할 필요가 있다. 때문에 운영체제는 디스크의 일부를 swap disk라는 공간으로 분리해 evict되는 anonymous page와 대응하는 프레임의 내용을 담아 두어야 한다. 반대로, evict된 프레임이 다시 필요해졌을 때 swap disk에서 메모리로 올려주는 것 또한 필요하다. 이를 각각 swap out / swap in이라고 표현하며 더 자세한 설명이 필요하다면 매뉴얼을 참조하도록 하자. 아무튼 VM_ANON 종류의 페이지가 swap in/out을 당할 때에는 anon_swap_in과 anon_swap_out이 사용되므로 해당 함수의 구현이 필요하다. 

3) VM_FILE

실제 파일이 매핑된 페이지에 사용되는 페이지 종류이다. C/C++을 좀 다뤄본 사람이라면 mmap 함수가 익숙할 것이다. 해당 함수는 파일의 내용을 메모리의 일부에 직접 올려 파일을 다룰 수 있도록 하는 함수로, 디스크에 접근하는 것에 비해 메모리에 접근하는 비용이 저렴하기 때문에 경우에 따라 사용된다. 해당 함수를 구현할 때, 불려온 파일의 내용을 담을 수 있도록 제공하는 페이지의 종류는 모두 VM_FILE이 된다. 

 

VM_ANON 종류와 달리 바탕이 되는 파일이 있어 swap in/out을 당할 때 기반이 되는 파일에서 내용을 읽어오거나 쓰면 된다. swap in의 경우 읽어오는 것은 특별한 문제가 없지만 swap out을 할 경우, 특별히 내용의 변화가 없다면 파일의 내용을 변경할 필요가 없기 때문에 무작정 쓰는 것은 시간을 낭비하는 짓이다. 따라서 이를 위해 페이지에 작성이 가해졌는지를 판별할 수 있도록 하는 dirty bit를 보고 swap out에서의 루틴을 결정하는 것이 좋을 것이다.

 

---

 

여기까지 얼추 페이지의 종류에 대해 살펴 봤으니 이제 이러한 정보를 담고 있는 페이지_정보_구조체를 관리하는 supplemental page table, 줄여서 spt에 대해 생각해보자. 현재의 페이지_정보_구조체의 형태를 다시 살펴보면:

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

	/* Your implementation */

	/* 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다. 따라서 페이지_정보_구조체에 hash_elem을 넣어 관리하도록 하면 될 것이다. pintos에서의 hash의 구현은 다음 포스팅에서 알아보자.

 

이제 눈을 돌려 다른 구조체에도 집중해보자. 페이지와 마찬가지로 프레임 또한 해당 프레임에 관한 정보를 어딘가에는 보관하고 있어야 할 것이다. 이를 struct frame(후술 프레임_정보_구조체)이라는 구조체에 저장하고 이러한 프레임_정보_구조체를 모아둔 것이 Frame Table, 줄여서 ft가 될 것이다. 참고로 현재의 struct frame은 다음과 같다:

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

ft 또한 spt와 마찬가지로 구조가 미정이므로 다음의 사항을 고려하여 설계해야 한다.

 

• 프레임_정보_구조체 삽입
• 프레임_정보_구조체 탐색
• 프레임_정보_구조체 삭제
• 프레임_정보_구조체 순회

이 중 순회가 효율적으로 이루어져야 하는 이유는 eviction policy를 고려해서 메모리 내에서 쫓아낼 프레임을 빠르게 골라낼 수 있어야 하기 때문이다. 나머지를 고려하면 이것도 hash로 만들고 싶기는 한데 과연 hash에 순회기능이 있을까했다. 놀랍게도 hash를 일시적으로 list 상태로 보도록 하여 순서를 임의로 반환하는 순회가 있긴 하다. 문제는 임의로 반환하는 것이라 생각을 좀 해 보아야 할 것 같다.

 

또 고려할 사항은 synchronization, 동기화 문제이다. 각 thread가 하나씩 들고 있어야 하는 spt와 다르게 ft는 모든 thread가 공유하는 하나의 자원이다. 따라서 필연적으로 동기화 문제가 발생할 수 밖에 없으며, 한 번에 하나의 thread가 접근하여 race 없이 관리하기 위해서는 lock을 달아 놓아야 한다. 해당 lock을 acquire해야만 ft와 관련된 함수를 사용할 수 있게끔 한다면 문제는 없을 것이다. ft에 대한 용건이 끝났다면 해당 lock을 release하도록 한다. 

 

여기까지 얼추 필요한 내용들을 살펴봤다. 글이 길어졌으니 여기서 끊고, 다음 포스팅에서 spt와 ft의 구체적인 설계와 함께 매뉴얼 상에서 구현하라고 한 함수들의 요구 사항을 살펴보도록 하자.