[pintos] 3주차 - Anonymous Page 구현 과정과 Pintos가 끝난 후 회고!

vm 공부가 끝나지 않아서 목요일에 구현 시작한 사람이 나예요.. 

(회고는 맨 아래쪽에)

 

젤 첫 번째 과제인 Anonymous Page를 해결해보자 !

이번 과제에서 통과되어야 하는 테스트 중 하나인 lazy-anon.c를 통해 구현 요구사항을 파악해볼 것이다.

선행되어야 하는 개념 

https://nkdev.tistory.com/181

[pintos] 3주차 - Virtual Memory Unallocated/Cached/Uncached 상태, Anonymous page, Lazy Loading

먼저 Anonymous page는 Page fault에 의해 Lazy Loading된다는 것을 알고 있어야 한다.

이 부분은 이전 글 참고!

lazy-anon.c 테스트 코드

익명 페이지가 레이지 로딩 되는지 확인하는 테스트이다.

/* Checks if anonymous pages are lazy loaded  */

#include <string.h>
#include <syscall.h>
#include <stdio.h>
#include <stdint.h>
#include "tests/lib.h"
#include "tests/main.h"

#define PAGE_SIZE 4096
#define CHUNK_PAGE_COUNT 3
#define CHUNK_SIZE (CHUNK_PAGE_COUNT * PAGE_SIZE)

static char buf[CHUNK_SIZE];

void
test_main (void)
{
	size_t i, j;
	void *pa;

	msg ("initial pages status");
	for (i = 0 ; i < CHUNK_PAGE_COUNT ; i++) {
		// All pages for buf should not be loaded yet.
		pa = get_phys_addr(&buf[i*PAGE_SIZE]);
		CHECK (pa == 0, "check if page is not loaded");
	}

	msg ("load pages");
	for (i = 0 ; i < CHUNK_PAGE_COUNT ; i++) {
		msg ("load page [%zu]", i);
		// Pages are loaded here.
		buf[i*PAGE_SIZE] = i;
		for (j = 0 ; j < CHUNK_PAGE_COUNT ; j++) {
			// Pages that have been accessed should be loaded
			// Pages that have not been accessed should not be loaded.
			pa = get_phys_addr(&buf[j*PAGE_SIZE]);
			if (j <= i) {
				CHECK (pa != 0, "check if page is loaded");
				CHECK (buf[j*PAGE_SIZE] == (char) j, "check memory content");
			}
			else {
				CHECK (pa == 0, "check if page is not loaded");
			}
		}
	}
}

테스트 코드 분석

main() 함수가 시작되면 buf[] 배열 각 요소의 가상 주소를 물리 주소로 변환하여 0인지 확인한다.

msg ("initial pages status");
/* (1) */
for (i = 0 ; i < CHUNK_PAGE_COUNT ; i++) {
    // All pages for buf should not be loaded yet.
    pa = get_phys_addr(&buf[i*PAGE_SIZE]);
    CHECK (pa == 0, "check if page is not loaded");
}

이 시점에서 buf는 선언만 됐을 뿐 아직 초기화되지 않았으므로, 매핑된 물리 프레임이 없는 상태이다. 따라서 물리 주소가 없다.

static char buf[CHUNK_SIZE];

 

두 번째 반복문을 보자. 

엇 드디어 buf[] 배열을 초기화했다. 

msg ("load pages");
	/* (2) */
	for (i = 0 ; i < CHUNK_PAGE_COUNT ; i++) {
		msg ("load page [%zu]", i);
		// Pages are loaded here.
		buf[i*PAGE_SIZE] = i; //buf 초기화 !!! -> lazy loading start
        
        	/* (3) */
		for (j = 0 ; j < CHUNK_PAGE_COUNT ; j++) {
			// Pages that have been accessed should be loaded
			// Pages that have not been accessed should not be loaded.
			pa = get_phys_addr(&buf[j*PAGE_SIZE]);
			if (j <= i) {
				CHECK (pa != 0, "check if page is loaded");
				CHECK (buf[j*PAGE_SIZE] == (char) j, "check memory content");
			}
			else {
				CHECK (pa == 0, "check if page is not loaded");
			}
		}
	}

선언만 되어있던 배열에 실제로 값을 저장하려고 할 때 물리 메모리에 공간이 할당되고 그 공간에 값이 저장된다.

1. cpu가 VA의 buf[i*PAGE_SIZE] = i; 라인을 실행
2. MMU가 페이지 테이블을 참조하여 VA와 매핑된 PA가 있는지 확인
3. 없으므로 Page fault 발생, 커널 모드로 전환
4. Page fault handler에 의해 물리 프레임을 할당 받고 VA와 PA를 연결
5. 커널 모드 종료, 마지막 인스트럭션을 다시 실행
6. 페이지가 메모리에 로드되었으므로 Page Hit

그리고 아까와 같이 buf[] 배열의 가상 주소를 물리 주소로 변환해보면서

물리 페이지가 할당되었는지 다시 확인해보고 있다.

 

구현 요구사항

아직 아무것도 구현하지 않은 상태에서 test를 실행해보자.

커널이 유저 프로세스 실행을 시작하는 것조차 실패했다는 결과가 뜬다.

(userprog/process.c:80즉 process_exec()함수에서 커널 패닉이 발생)

FAIL
Kernel panic in run: PANIC at ../../userprog/process.c:79 in initd(): Fail to launch initd
Call stack: 0x8004217e6a 0x800421b557 0x80042077dd
Translation of call stack:
0x0000008004217e6a: debug_panic (lib/kernel/debug.c:32)
0x000000800421b557: initd (userprog/process.c:80)
0x00000080042077dd: kernel_thread (threads/thread.c:477)

 

Lazy loading은 가상 페이지만 할당해뒀다가 그 가상 페이지의 내용이 실제로 필요해져서 접근했을 때 page fault에 의해 내용이 물리 공간에 로드되는 원리다. 테스트가 실패한 이유는 아직 물리 공간에 로드되지 않은 가상 페이지에 접근했기 때문이다.

 

우리는 page fault 발생 시 page fault handler가 anonymous page임을 판별하고 lazy loading을 해주는 로직을 짜주어야 한다.

 

page fault handling 과정 살펴보기

Pintos에서 page fault handler역할을 하는 함수는 userprog/exception.c의 page_fault()이다.

페이지 폴트 핸들러는 vm_try_handle_fault()를 호출한다.

static void page_fault(struct intr_frame *f) {
	...
#ifdef VM
    if (vm_try_handle_fault(f, fault_addr, user, write, not_present))
        return;
#endif
    exit(-1);
    ...
}

 

vm_try_handle_fault()에서 다음 과정이 수행되며 실제로 페이지 폴트가 처리된다.

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

 

(해당 과정은 내가 공부해서 알아낸 것은 아니고 울 팀원이 준 자료를 바탕으로 정리한 것이다. 이런 자료도 참고하지 않으면 절대로 구현 시작을 못할 것 같아서 결국 힌트를 참고했는데, 공부 속도가 확 빨라져서 좋긴 하다. 잘못된 정보가 포함되어있을 수도 있다..!)

1. spt에서 fault가 발생한 페이지를 찾는다.
   1. 만약 valid하다면 spt를 사용해 해당 페이지에 들어갈 데이터를 찾는다.
   2. 이 데이터는 disk file system 또는 swap공간에 존재할 수 있다.
   3. 만약 공유(copy-on-write)를 구현한다면 페이지 데이터는 이미 프레임에 있을 수 있지만 페이지 테이블에는 없을 수도 있다.
   4. spt를 조회했는데 잘못된 va이거나, 읽기 전용 페이지이면 유효하지 않은 접근이므로 segmentation fault처리한다.
   5. 유효하지 않은 접근이 발생하면 프로세스를 강제 종료하고 모든 자원을 해제한다.
   6. +) GitBook Anonymous page 참고하면, 추가로 bogus page fault인지도 확인해야 함! 
2. 페이지의 내용을 저장할 프레임을 할당받는다.
   1. 만약 공유 라이브러리에 접근하는 상황이라면, 해당 데이터가 이미 프레임에 있을 것이므로 해당 프레임을 찾아야 한다.
3. 프레임을 데이터로 채운다.
   1. 파일 시스템이나 스왑 공간에서 데이터를 읽어오거나 0으로 채우는 등 프레임에 데이터를 저장해준다.
   2. 만약 공유 라이브러리에 접근하는 상황이라면 이 단계는 생략해도 된다.
4. fault가 발생한 가상 주소의 페이지와 물리 프레임을 매핑한다.
   1. threads/mmu.c 함수를 이용해서 페이지 테이블 항목이 물리 페이지를 가리키도록 한다.

* cow(copy-on-write) : 공유 데이터를 여러 프로그램이 사용할 때 한 프로그램이 데이터를 수정하려고 할 때까지 동일한 데이터를 프로그램 간에 공유한다. 변경 사항이 없으면 개인 복사본이 생성되지 않아 리소스가 절약된다.

.

.

 

구현하기

spt

먼저 현재 접근한 va가 spt에 등록되어 있는지 확인하여 valid한 va인지 판단해야 한다.

그래서 구조체랑 함수를 봤는데 다 비어있었다. 내가 구현해야 한다.

 

1) spt 구조체이다. 멤버로 뭘 넣어야 될까....

struct supplemental_page_table {
};

 

2) spt를 만들고 초기화하는 함수이다. userprog/process.c의 initd() 또는 do_fork()에서 새로운 프로세스를 만들 때 호출된다.

void
supplemental_page_table_init (struct supplemental_page_table *spt UNUSED) {
}

 

3) spt에서 va에 해당하는 struct page를 찾아 리턴하는 함수이다. 실패하면 NULL을 리턴한다.

struct page *
spt_find_page (struct supplemental_page_table *spt UNUSED, void *va UNUSED) {
	struct page *page = NULL;
	/* TODO: Fill this function. */

	return page;
}

 

4) spt에 struct page를 삽입하는 함수이다. va가 spt에 이미 존재하는지 확인한 후 삽입해야 한다.

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

	return succ;
}

 

spt를 구현하기 전에 먼저 이것부터 생각해보자. spt는 왜 필요할까? 

GitBook의 Project3 Introduction에는 이렇게 설명되어 있다.

 

'보조 페이지 테이블'이라는 이름처럼 가상 공간의 각 페이지에 대한 추가 정보를 관리할 필요가 있기 때문이다.

각 페이지에 대해서 상응하는 kva를 가리키는 포인터의 정보, 해당 페이지의 데이터가 frame, disk, swap 중 어디에 존재하는지, 페이지가 valid한지 등을 알아야 다음과 같은 문제가 발생했을 때 상황에 맞는 적합한 방식으로 처리할 수 있다.

• page fault를 처리해야 하는 경우
• 커널이 프로세스를 종료하고 어떤 자원을 해제할지 고르는 경우

아하, 그렇다면 spt 구조체 안에는 여러 페이지들에 대한 부가 정보가 저장되어야 한다.

include/vm/vm.h에 struct page 구조체가 있다.

얘네를 리스트로 쭉 이어서 spt 안에 넣어야 하지 않을까??

📍 struct page 

struct page는 가상 메모리의 페이지 하나에 대한 정보를 담고 있는 구조체이다.

Project1에서 ready_list를 연속된 struct thread의 리스트로 관리하기 위해 list_elem을 쓴 것처럼

Project3에서도 spt를 연속된 struct page의 리스트로 관리하기 위해 struct page 멤버로 hash_elem 구조체를 추가해준다.

주의 : struct hash_elem *hash_elem 이렇게 포인터로 선언하지 않도록 주의! 구조체 자체를 가지고 있어야 함

struct page {
	const struct page_operations *operations; 	/* 페이지 연산 */
	void *va;              						/* 가상 주소 */
	struct frame *frame;   						/* 물리 프레임 */
    
    /* Your implementation */
	struct hash_elem hash_elem;
    
	union {										/* 페이지 타입 */
		struct uninit_page uninit;				/* Uninit Page */
		struct anon_page anon;					/* Anonymous Page */
		struct file_page file;					/* File-backed Page */
#ifdef EFILESYS
		struct page_cache page_cache;
#endif
	};
};

 

📍 struct supplemental_page_table

spt 테이블을 hash table로 관리하기 위해 struct hash 구조체를 추가해준다.

struct supplemental_page_table {
	struct hash spt_hash;
};

spt는 이런 형태가 된다.

bucket 마다 struct page를 가지고 있고, 각 요소는 hash_elem으로 접근할 수 있다.

📍 supplemental_page_table_init() 

void
supplemental_page_table_init (struct supplemental_page_table *spt UNUSED) {
	hash_init(&spt->spt_hash, page_hash, page_less, NULL);
}

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

📍 spt_find_page(), spt_insert_page()

/* Find VA from spt and return page. On error, return NULL. */
//spt가 va에 해당하는 page를 가지고 있는지 찾아서 리턴, 못 찾으면 NULL 리턴
struct page *
spt_find_page (struct supplemental_page_table *spt UNUSED, void *va UNUSED) {
	struct page p;
	struct hash_elem *e;
	
	/* TODO: Fill this function. */
	//hash table 탐색 : dummy.hash_elem주소를 넣으면 해시 테이블 내부에서 같은 va를 가진 요소를 찾아줌
	e = hash_find(&spt->spt_hash, &p.hash_elem);
	if(e == NULL)
		return NULL;

	//hash_elem 포인터 -> struct page 포인터로 변환
	return hash_entry(e, struct page, hash_elem);	
}

/* 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. */
	//va에 대응하는 struct page의 hash_elem을 spt의 hash table에 등록
	if(hash_insert(&spt->spt_hash, &page->hash_elem) == NULL){
		//hash_insert는 중복 없는 삽입을 성공하면 NULL을 반환
		succ = true;
	}
	return succ;
}

.

.

spt 구현을 어느정도 했으니 다시 page fault handler로 넘어가보자.

📍 vm_try_handle_fault()

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

vm_do_claim_page()에 이미 구현된 코드를 보니 vm_get_frame()으로 새로운 프레임을 palloc받고, 할당받은 프레임과 페이지를 서로 참조하도록 연결해주는것 까지 하고 있다. 

이제 그 밑에 va-pa 매핑 정보를 page table에 추가하는 작업을 해줘야 한다. 

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. */
	/*
	인자로 주어진 page에 물리 프레임을 할당
	1. vm_get_frame()을 호출하여 프레임 하나를 할당받기
	2. mmu 세팅하기
		va-pa 매핑 정보를 page table에 추가하기: threads/mmu.c에 있는 함수 사용하기
	3. 1, 2번 연산이 성공했으면 true 반환, 그렇지 않으면 false 반환
	*/

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

 

깃북에서 threads/mmu.c에 있는 함수를 쓰라길래 찾아봤는데 pml4_create()가 있길래 함 봤다.

움.....커널 풀에 프레임을 할당받고, 할당받은 프레임의 시작 주소를 돌려받아 그 곳에 base_pml4를 memcpy()하는 함수이다.

base_pml4는 threads/init.c의 main()함수에서 맨 처음 페이지를 초기화할 때 paging_init() 호출하는데, 이 때 맨 처음 palloc 할당받은 곳을 가리키는 포인터이다. 즉 맨 처음 페이지의 주소이다. 

이 맨 처음 페이지의 내용을 방금 할당받은 곳에 왜 memcpy()하는거지..?

uint64_t *
pml4_create (void) {
	uint64_t *pml4 = palloc_get_page (0); //플래그로 0을 넘김 -> 플래그 없이 기본 설정값으로 할당을 요청하겠다는 의미. 이 경우 커널 풀에 할당됨
	if (pml4)
		memcpy (pml4, base_pml4, PGSIZE);
	return pml4;
}

 

진짜 어떻게 쓰는지 모르겠어서 GitBook Introduction의 Page Tables 설명을 봤다.

왼쪽의 가상 주소는 page number, offset

오른쪽의 물리 주소는 frame number, offset

을 가지고 있고.. frame number는 물리 주소를 획득하기 위한 미수정된 offset과 결합되어 있다..

                           +----------+
          .--------------->|Page Table|-----------.
         /                 +----------+           |
        |   12 11 0                               V  12 11 0
    +---------+----+                         +---------+----+
    | Page Nr | Ofs|                         |Frame Nr | Ofs|
    +---------+----+                         +---------+----+
     Virt Addr   |                            Phys Addr    ^
                  \_______________________________________/

 

오.....딱히 구현 함수는 알려주지는 않는다. 

그러다가 pml4_set_page()함수를 찾았다.

 

pml4 테이블에 upage라는 사용자 가상 페이지 주소를 kpage라는 커널 가상 주소가 가리키는 물리 프레임에 매핑하는 함수이다.

얘를 사용하면 되겠다!

bool
pml4_set_page (uint64_t *pml4, void *upage, void *kpage, bool rw) {
	ASSERT (pg_ofs (upage) == 0);
	ASSERT (pg_ofs (kpage) == 0);
	ASSERT (is_user_vaddr (upage));
	ASSERT (pml4 != base_pml4);

	uint64_t *pte = pml4e_walk (pml4, (uint64_t) upage, 1);

	if (pte)
		*pte = vtop (kpage) | PTE_P | (rw ? PTE_W : 0) | PTE_U;
	return pte != NULL;
}

아래처럼 구현해보았다.

인자로 사용자 가상 주소, 커널 가상 주소를 넘겨줘야 하므로 page->va, frame->kva를 써준다.

static bool
vm_do_claim_page (struct page *page) {
	struct frame *frame = vm_get_frame ();

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

    /* Insert page table entry to map page's VA to frame's PA. */
	pml4_set_page(thread_current()->pml4, page->va, frame->kva, true);

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

 

page fault가 발생하면 페이지 폴트 핸들러인 vm_try_handle_fault()가 호출된다.

📍 vm_try_handle_fault()

vm_try_handle_fault()는 발생한 page fault가 진짜 잘못된 접근인지, 예정된 page fault인지 판단하여 다르게 처리해야 한다.

여기 구현 요구사항 이해하는게 진짜 제일 어려웠다. 거의 이틀간 얘만 본 것 같다 ㅎㅎ...

https://www.youtube.com/watch?v=8twIUEo1mIs&t=777s

 

이 영상 11:00경 나오는 <Page fault in Pintos with VM> 부분을 보면 page fault handling을 참고하면 좋을 것 같다.

그리고 울 팀원이랑 주변 도움을 통해 내가 이해한 대로 다이어그램도 그려보았다..!

 

(1) page == NULL :  유효하지 않은 페이지에 접근한 경우

만약 1. 존재하지도 않는 이상한 va에 접근했거나(sementation fault) 2. 스택 영역 확장이 필요한 곳에 접근한 경우 현재 cpu가 접근한 va에 해당하는 struct page 자체가 없고 당연히 spt에도 해당 page 엔트리가 없을 것이다. 따라서 spt_find()로 페이지를 찾으면 NULL이 리턴된다. 1의 경우 프로세스를 종료시켜야 하고 2의 경우 스택을 확장한 후 vm_alloc함수로 uninit 페이지를 새로 만들어줘야 한다.

 

(2) page != NULL : bogus fault (메모리 사용 효율을 높이기 위해 page fault가 발생했을 때 frame을 할당함)

현재 cpu가 접근한 va에 해당하는 struct page는 존재하는데 아직 frame 할당이 안 된 상태라면 bogus fault에 해당한다. 1. 코드, 데이터 세그먼트의 lazy load가 필요한 경우 2. 공유 라이브러리의 경우 두 가지가 존재한다. 1의 경우 spt_find()로 페이지를 찾아서 해당 페이지에 대한 frame을 할당한 후 페이지의 데이터를 프레임에 로드해주고 핸들러가 종료된 후 다시 유저모드로 돌아가서 명령어를 재시도하면 된다. 2의 경우 공유 라이브러리이므로 이미 frame이 존재할 것이고, 페이지를 그 frame과 매핑하면 된다.

 

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 */
    
	if(addr == NULL || addr > KERN_BASE)
		return false;
	
	page = spt_find_page(&spt->spt_hash, &addr);

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

일단 NULL인 경우 false를 반환하고 NULL이 아니면 vm_do_claim_page를 호출하게 했다.

page==NULL인 경우 stack_growth인지 판단해서 맞으면 vm_alloc_page_with_initializer()을 호출해야 하는데 일단 그 부분은 나중에 하기로 하고 .. 일단 다음 단계부터 구현해보자

📍vm_alloc_page_with_initializer()

새로운 페이지를 만들고 uninit_new()를 호출하여 페이지를 초기화해줘야 한다.

이 때 uninit_new()에 vm type별로 적절한 initializer을 넘겨줘야 나중에 page->operation을 사용할 때 그에 맞는 함수를 쓸 수 있다.

(곧 설명할 swap_in()부분을 보면 이해가 갈 것이다.)

 

먼저 새 페이지를 생성해보자.

첨에 GitBook을 잘못 해석해서 vm_alloc_page_with_initializer안에서 새로운 페이지를 생성할 때 vm_alloc_page()를 사용하라는줄 알고

struct page* p = vm_alloc_page(type, upage, writable);

이렇게 구현했는데 컴파일 에러가 발생했다.

vm_alloc_page()는 _Bool타입을 반환하기 때문에 struct page*타입 변수를 초기화하지 못한다는 에러이다.

그래서 vm_alloc_page()를 타고 들어가봤는데

#define vm_alloc_page(type, upage, writable) \
	vm_alloc_page_with_initializer ((type), (upage), (writable), NULL, NULL)

이런 매크로가 정의되어있었다.

vm_alloc_page(type, upage, writable)는 vm_alloc_page_with_initializer()의 마지막 두 인자를 NULL로 주고싶을 때 호출하는 함수였다. 즉 vm_alloc_page()는 initializer함수를 따로 안 넘겨줌으로써 페이지 생성만 하고싶을 때 사용하고, vm_alloc_page_with_initializer는 initializer함수를 같이 넘겨줘서 페이지 생성과 동시에 함수를 사용해 초기화한다. 

 

load() 안에서 사용되는 load_segment()에서 lazy_load할 때 이렇게 쓰인다.

 if (!vm_alloc_page_with_initializer(VM_ANON, upage, writable,
                                            lazy_load_segment, load_field))

 

그러면 새로운 페이지 생성을 어떻게 해야 하지..?

그냥 struct page 하나 만들고 malloc으로 할당해주면 되는건지, 이미 구현되어있는 함수를 사용하는 건지 모르겠어서 헤메고 있었는데 palloc_get_page()였다.

 

malloc()도 내부적으로 이 함수를 사용해서 페이지를 할당하는 것을 볼 수 있는데, malloc()은 할당할 size를 지정해주면 그 사이즈에 맞게 palloc_get_page()로 페이지 하나를 할당해주거나 palloc_get_multiple()로 한꺼번에 여러 페이지를 할당해준다.

void *
malloc (size_t size) {
	struct desc *d;
	struct block *b;
	struct arena *a;

	/* A null pointer satisfies a request for 0 bytes. */
	if (size == 0)
		return NULL;

	/* Find the smallest descriptor that satisfies a SIZE-byte
	   request. */
	for (d = descs; d < descs + desc_cnt; d++)
		if (d->block_size >= size)
			break;
	if (d == descs + desc_cnt) {
		/* SIZE is too big for any descriptor.
		   Allocate enough pages to hold SIZE plus an arena. */
		size_t page_cnt = DIV_ROUND_UP (size + sizeof *a, PGSIZE);
		a = palloc_get_multiple (0, page_cnt);
		if (a == NULL)
			return NULL;

		/* Initialize the arena to indicate a big block of PAGE_CNT
		   pages, and return it. */
		a->magic = ARENA_MAGIC;
		a->desc = NULL;
		a->free_cnt = page_cnt;
		return a + 1;
	}
...
}

 

우리는 4KB짜리 1페이지만 만들어줄 거고, flag도 PAL_USER로 지정해서 유저풀에 할당해줘야 하므로 palloc_get_page()를 사용해서 페이지를 할당해준다.

struct page* p = palloc_get_page(PAL_USER);

 

 

이제 uninit_new()로 할당해준 페이지를 초기화해줘야 한다!

초기화할 때 타입별로 다른 initializer을 넘겨줘야 된다.

switch(VM_TYPE(type)){
			case VM_ANON:
				uninit_new(p, p->va, init, type, NULL, anon_initializer);
			case VM_FILE:
				uninit_new(p, p->va, init, type, NULL, file_backed_initializer);				
		}

이렇게..!

uninit_new()를 보면 page구조체의 각 멤버를 넘겨받은 데이터들로 초기화해주고 있다.

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

 

그리고 페이지를 하나 만들었으니 spt에도 넣어줘야 한다.

spt_insert_page(spt, p);

구현한 코드는 아래와 같다.

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

		//vm_alloc_page로 페이지를 하나 만들어주고 vm type에 맞는 initializer를 인자로 갖는 uninit_new함수를 호출한다.
		struct page* p = palloc_get_page(PAL_USER);

		switch(VM_TYPE(type)){
			case VM_ANON:
				uninit_new(p, p->va, init, type, NULL, anon_initializer);
			case VM_FILE:
				uninit_new(p, p->va, init, type, NULL, file_backed_initializer);				
		}	
		/* TODO: Insert the page into the spt. */
		spt_insert_page(spt, p);
	}
	return true;
err:
	return false;
}

 

VM_TYPE(type) 이렇게 연산해준 이유는 

vm_type은 VM_UNINIT, VM_ANON, VM_FILE, VM_PAGE_CACHE 이렇게 나뉘는데 각각 0, 1, 2, 3이다.

이진수로 나타내면 0000, 0001, 0010, 0011이고 하위 2비트만으로 타입을 구분할 수 있다.

 

이 네 가지 타입에 추가적으로 다른 정보 (예를 들면 접근 시 stack_growth가 요구되는 상태인지 등)를 더 추가하고 싶으면 VM_MARKER_N으로 하위 3비트, 4비트, 필요하다면 더 많은 비트를 사용해서 표현할 수 있다. 즉 타입으로 (VM_ANON | VM_MARKER_0)을 넘겨주면 anon타입이면서 stack growth가 요구되는 페이지로 해석할 수 있다. 이때 값 자체는 1001이 될 것이다.

 

근데 어쨌든 우리가 switch문을 분기하려면 marker값을 빼고 하위 2비트만 추출한 값을 사용해야 하므로 marker값이 연산된 경우를 고려해서 VM_TYPE()으로 한번 감싸서 하위 2비트만 추출해줘야 한다.

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,
	/* page that hold the page cache, for project 4 */
	VM_PAGE_CACHE = 3,

	/* Bit flags to store state */

	/* Auxillary bit flag marker for store information. You can add more
	 * markers, until the value is fit in the int. */
	VM_MARKER_0 = (1 << 3),
	VM_MARKER_1 = (1 << 4),

	/* DO NOT EXCEED THIS VALUE. */
	VM_MARKER_END = (1 << 31),
};

📍vm_do_claim_page()

vm_do_claim_page()는 인자로 주어진 페이지에 물리 프레임을 할당하는 함수이다.

1. vm_get_frame()을 호출하여 프레임 하나를 할당받고
2. va-pa 매핑 정보를 page table에 추가하여 mmu를 세팅한다. threads/mmu.c에 있는 함수를 사용하면 된다.
3. 1, 2번 연산이 성공했으면 true를 반환하고 그렇지 않으면 false를 반환한다.

매핑 정보를 pml4 페이지 테이블에 저장해야 한다. pml4_set_page()를 사용하자 ~ 

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

	pml4_set_page(thread_current()->pml4, page->va, frame->kva, true);

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

📍swap_in()

swap_in()은 vm.h에 이렇게 정의되어있다.

이 함수는 수정사항은 없는데 page를 초기화할 때 사용되는 애라서 알고 넘어갈 필요가 있다.

swap_in()이 동작하는 원리.. 쉽게 이해하기 어려웠지만 그래도 해내따...[≡] ✍(・⺫・‶)

 

#define swap_in(page, v) (page)->operations->swap_in ((page), v)

swap_in()은 인자로 받은 page의 operations가 가리키는 swap_in()을 또 호출하고 있다. 

구조가 이상해보이지만 이해하면 별 거 아니다.

 

swap_in()은 사실 인터페이스이고, page의 타입별로 다르게 구현되어있다.

그래서 swap_in(page, v)이렇게 호출하면 해당 페이지의 타입에 맞는 swap_in()함수가 자동으로 호출된다!

 

몬 말인지 코드를 보면서 이해해보자.

GitBook의 Memory Management > Page Operations에 자세히 설명되어 있다.

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;

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

page 구조체 안에는 page_operations라고 페이지 타입 별로 다르게 호출되는 함수를 관리하는 구조체가 있는뎁

/* The function table for page operations.
 * This is one way of implementing "interface" in C.
 * Put the table of "method" into the struct's member, and
 * call it whenever you needed. */
 struct page_operations {
	bool (*swap_in) (struct page *, void *);
	bool (*swap_out) (struct page *);
	void (*destroy) (struct page *);
	enum vm_type type;
};

page_operations의 주석을 해석해보면

구조체 멤버로 함수 포인터를 지정해두면 c언어에서 구조체를 인터페이스처럼 사용할 수 있다고 한다.

 

page_operations 구조체의 swap_in(), swap_out(), destroy()포인터가 페이지 타입별로 각각 다른 swap_in(), swap_out(), destroy()동작을 하게 하는 인터페이스이고 swap_in(page, va) 이렇게 호출했을 때 자동으로 VM_ANON타입 페이지면 anon_swap_in()이, VM_FILE타입 페이지면 file_backed_swap_in()이 호출된다. 

 

이게 어떻게 가능하냐! 면!

우리가 처음 페이지를 생성하는 시점에서 페이지 타입이 VM_ANON이냐 VM_FILE이냐에 따라서 initializer을 다르게 호출해줬던 게 기억나시나요

bool
vm_alloc_page_with_initializer (enum vm_type type, void *upage, bool writable,
		vm_initializer *init, void *aux) {
	...

	struct page* p = palloc_get_page(PAL_USER);

		switch(VM_TYPE(type)){
			case VM_ANON:
				uninit_new(p, p->va, init, type, NULL, anon_initializer);
			case VM_FILE:
				uninit_new(p, p->va, init, type, NULL, file_backed_initializer);				
		}	

		spt_insert_page(spt, p);
...
}

이렇게...타입에 따라 uninit_new()에 initializer을 다르게 넘겨줬었고

initializer을 들어가보면 page->operations을 타입에 맞는 ops들로 초기화하고 있는 거슬 확인할 수 있다.

 

anon이면 이렇게..

bool
anon_initializer (struct page *page, enum vm_type type, void *kva) {
	/* Set up the handler */
	page->operations = &anon_ops;

	struct anon_page *anon_page = &page->anon;
}

static const struct page_operations anon_ops = {
	.swap_in = anon_swap_in,
	.swap_out = anon_swap_out,
	.destroy = anon_destroy,
	.type = VM_ANON,
};

 

file이면 이러케...

bool
file_backed_initializer (struct page *page, enum vm_type type, void *kva) {
	/* Set up the handler */
	page->operations = &file_ops;

	struct file_page *file_page = &page->file;
}

static const struct page_operations file_ops = {
	.swap_in = file_backed_swap_in,
	.swap_out = file_backed_swap_out,
	.destroy = file_backed_destroy,
	.type = VM_FILE,
};

초기화된다.

 

여기까지 구현하면 lazy-loading이 완료된 것이므로 lazy-anon 테스트를 pass할 수 있다.

 

이제 spt를 copy하고 clean up하는 연산을 구현하면 process fork 또는 process exit 관련된 테스트를 pass할 수 있다.

프로세스를 fork할 때 부모 spt를 자식에게 복사해주고, 프로세스를 exit할 때 spt도 같이 할당 해제해줄 수 있게 되기 때문이다.

📍supplemental_page_table_copy()

GitBook에는 이 함수에 대해 이렇게 설명하고 있다 :

인자로 dst와 src라는 이름의 spt 구조체 포인터를 두 개 받아서 dst를 src에 복사하는 함수이다.

부모 프로세스를 fork하여 자식 프로세스를 만들 때 context를 상속하기 위해 사용된다.

 

이 함수를 우클릭하여 go reference를 보면 userprog/process.c의 do_fork()에서 호출된다는 것을 알 수 있다.

do_fork()는 자식 프로세스를 생성하는 함수인데, 자식 프로세스를 생성할 때 parent->spt를 current->spt에 복사하여 부모 spt를 자식 프로세스에게도 상속시켜줘야 한다.

supplemental_page_table_init(&current->spt);
    if (!supplemental_page_table_copy(&current->spt, &parent->spt))
        goto error;

 

요구사항을 정리해보면 다음과 같다.

• 부모 spt의 모든 페이지를 순회하며 자식 spt에도 같은 페이지를 만들어준다.
  • 페이지 타입에 맞게 값을 복사해준다.
    • VM_ANON 타입
      • 프레임이 이미 할당되어 있으면 해당 프레임의 내용을 복사
        • 프레임이 이미 할당되어 있는지 확인하는 방법 :
          1. struct page 내부 구조체의 frame 필드가 NULL이면 아직 할당되지 않은 상태 (lazy load, swap)
          2. NULL이 아니면 이미 프레임이 할당되어 있고 물리 메모리에 올라와 있는 상태
        • 새 프레임을 할당하는 방법 : page_get_frame()
      • lazy load 상태라면 lazy 상태 그대로 복사
      • anonymous page가 swap-out상태인 경우 swap slot 정보도 그대로 복사 (swap-in을 강제하지 않고 slot 정보만 복제해도 됨)
    • VM_FILE 타입
      • 파일, 오프셋, 읽기/쓰기 플래그 등 메타정보를 그대로 복사
      • lazy load 그대로 유지
      • 이미 로드된 상태라면 데이터 복사 필요
• 중간에 실패하면 rollback -> 이전에 복사한 자식 spt 엔트리를 정리해야 함

📍supplemental_page_table_kill()

spt에 의해 유지되던 모든 자원들을 free하는 함수이다. 

프로세스가 exit될 때 사용된다.

PTE(페이지 테이블 엔트리)를 순회하면서 테이블의 페이지에 destroy(page)를 호출해야 한다.

실제 페이지 테이블(pml4)와 palloc된 물리 메모리에 대해 걱정할 필요가 없다. spt가 정리되고 나서 호출자가 정리할 것이기 때문이다.

 

일단 무슨 말인지 다 이해하기 어렵기 때문에 사용할 함수가 뭐가 있는지부터 보자.

우리는 spt를 hash로 관리하기로 했다.

struct supplemental_page_table {
	struct hash spt_hash;
};

 

---

'정글의 꽃은 핀토스'

정글에 지원할 때 이전 기수분들의 블로그를 정독하면서 많이 봤던 말이다.

 

운영체제를 직접 구현해본다니.. 대체 어떤 과정인지 궁금해서 포스팅이 보일 때마다 구경해봤지만 매번 내용이 너무 어렵고 복잡해서 내가 이걸 할 수 있을까 걱정스러운 마음이 들기도 했다.

 

그래도 난 무언가를 이해하려면 직접 만들어보는것만큼 좋은 방법이 없다는 일념이 있어서..!

정글에서 핀토스를 해보고싶은 마음이 가득했다.

 

그렇게 핀토스 주차가 시작되었고, 아......역시 난관의 연속이었다. ㅎㅎㅎ

 

일단 운영체제가 어떤 상황에서 어떻게 동작하는지에 대해 정확히 인지하고 있어야 했고, 과제에서 제시한 테스트코드가 통과되게 하려면 내가 어떤 파일의 어떤 메소드 안에 어떤 메소드/로직을 사용해서 구현해야 하는지 알아내야 했다.

 

이미 짜여져있는 거대한 핀토스 운영체제의 구조를 파악하는 일이 처음에는 너무 어려웠다.

그러나 GitBook 공식 문서와 KAIST 강의를 들으면서 코드를 하루종일 들여다보고 있으니 점점 전체 구조가 눈에 들어오기 시작했다. 물론 실제 구현에 있어서는 동료의 도움을 가장 많이 받았던 것 같다!

 

코드 해석은 끝났는데 요구사항 파악이 부족했거나, 구현을 했는데 뭔가 놓친 로직이 있거나 문법적인 실수를 한 경우에 동료에게 문제 사항을 얘기해주면서 질문을 하면 먼저 앞서간 사람 입장에서는 이미 답을 알고 있으므로 나에게 해결 방법을 바로 알려주지 않고 계속 정답쪽으로 생각하도록 유도를 하면서 대화가 이어진다. ㅋㅋㅋ이 과정이 너무 재밌었다!

 

이건 이거고 저건 저거잔하요.

네. 그럼 저건 이거고 이건 저거겠네요??

(이런 대화를 몇 번 반복한 후...)

네네맞아요!@!!! 쏘영님, 그럼 답이 나왔네요. 여기서 어떻게 해야 될까요????

음..........이렇게저렇게??????

네 바로 그겁니다!!!!

짝짝짝짜가ㅉㄱ

ㅉㅉㅉㅉㅉㅉ

 

대부분 같은 문제에 대해서 고민했어서 그런지 함께 문제를 풀기 위해서 의견을 나누다 보면 서로 알고있는 부분이 채워지기도 하고, 좀 더 오래 기억에 남기도 하고..! 재밌다.

 

그리고... 다른 사람이 볼 땐 어떨지 모르겠지만, 나는 비교적 주먹구구식으로 공부했다.

핀토스 주차 내내 AI에게 코드 생성을 부탁하지도 않았고 다른 사람이 이미 구현한 코드를 참고하지도 않았다.

AI가 짜준 코드를 쓰고싶지 않았다. 일단 c언어에서 함수 쓰려면 포인터 넘겨주고 받는거, 포인터 연산이 중요할 텐데 난 여전히 퀴즈에서 포인터 문제가 나올 때마다 틀리는 실력을 가지고 있기 때문에 ㅋㅋㅋ... 좀 나에게 어려움을 줄 필요가 있다고 생각했다...

 

역시나 포인터 참조값 잘못 넘겨주는 문제때문에 project 3에서는 load_segment함수쪽에서 124 failed in 141 tests가 며칠째 유지되기도 했고, project 1에서는 argument passing 구현할 때 무한루프가 돌아서 timeout이 나기도 했다. 덕분에 앞으로 c언어에서 에러가 발생하면 내가 포인터 연산을 잘못했는가를 먼저 생각할 것 같다. ㅎㅎ...

 

그리고 요구사항 파악이나 개념 공부도 거의 CSAPP, OS 책이나 IBM, 대학 강의 등 믿을만한 자료들을 참고했다.

물론 쉽지 않은 과정이었지만, 나중에 일할 때를 대비해서 미리 습관을 만들어두고 싶었다. 

 

모든 과제를 완성하지는 못 했지만, OS의 내부적인 동작을 직접 구현해보면서 OS의 필요성과 동작 원리에 대한 깊은 이해를 할 수 있었고 더불어 멀티 태스킹 환경에서 발생하는 문제점과 해결 방법 등을 알 수 있었다. 그리고 동료 학습을 하면서 다른 사람들로 부터 소프트 스킬도 많이 배웠다. 

 

모든 대학교에서 핀토스로 OS를 가르쳤으면 좋겠다..! 재밌고.. 재밌고..어렵ㄱ고.. 재밌다. ㅎㅎ

아무튼 수료 전까지 다른 과정이 많이 남았기 때문에 (((나만무))) 이제 핀토스를 놓아줘야겠다. 안녕!!! 나중에 또 보자아아아아