[Pintos-Kaist] Project3 - Memory Management

핀토스 프로젝트 3에서는 Virtual Memory에 관한 내용들을 토대로 구현을 시작합니다.

 

우선 첫 번째 구현 요소인 Memory Management에 대해서 알아보겠습니다.

 

Memory Management

 

• 가상 메모리 시스템을 지원하려면 가상 페이지와 물리적 프레임을 효과적으로 관리해야 합니다.
  • 즉, 어떤 (가상 또는 물리적) 메모리 영역이 어떤 목적으로, 누가, 어떤 용도로 사용되고 있는지 등을 추적해야 합니다.
• 먼저 보충 페이지 테이블을 다룬 다음 물리적 프레임을 다룰 것입니다. 이해를 돕기 위해 가상 페이지에는 '페이지'라는 용어를, 물리적 페이지에는 '프레임'이라는 용어를 사용한다는 점에 유의하세요.

 

 

 

Struct page

 

• struct page에 hash_elem 멤버를 추가해서 해당 페이지를 해시 테이블에 저장합니다.

struct page {
	const struct page_operations *operations;
	void *va;              
	struct frame *frame;   
	struct hash_elem hash_elem; //추가

	union {
		struct uninit_page uninit;
		struct anon_page anon;
		struct file_page file;
#ifdef EFILESYS
		struct page_cache page_cache;
#endif
	};
};

 

 

 

Supplemental Page Table

 

• 핀토스에는 메모리의 가상 및 물리적 매핑을 관리하기 위한 페이지 테이블(pml4)이 있습니다.
• 페이지 오류 및 리소스 관리를 처리하기 위해 각 페이지에 대한 추가 정보를 저장할 보조 페이지 테이블도 필요합니다.
• 따라서 프로젝트 3의 첫 번째 과제로 보충 페이지 테이블에 대한 몇 가지 기본 기능을 구현하는 것이 좋습니다.

struct supplemental_page_table {
	// 페이지 정보를 저장하는 해시 테이블
	struct hash pages;
};

 

 

 

 

1️⃣ void supplemental_page_table_init(struct supplemental_page_table *spt UNUSED)

 

• supplemental page table을 초기화합니다.
• hash_init함수를 이용해서 해시 테이블을 초기화하고 비교 함수(less_func)와 해시 함수(hash_func)를 설정합니다.

void supplemental_page_table_init(struct supplemental_page_table *spt UNUSED) {
    // 페이지 해시 테이블을 초기화합니다.
    // hash_init 함수는 주어진 해시 테이블을 초기화하고 비교 함수와 해시 함수를 설정합니다.
    // pages 멤버는 페이지를 저장하는 해시 테이블입니다.
    hash_init(&spt->pages, hash_func, less_func, NULL);
}

 

 

1-1) hash_func()

// 해시 함수: 주어진 hash_elem 구조체를 사용하여 페이지의 가상 주소에 대한 해시 값을 계산합니다.
uint64_t hash_func(const struct hash_elem *e, void *aux) {
    const struct page *pg = hash_entry(e, struct page, hash_elem);

    return hash_bytes(&pg->va, sizeof(*pg->va));
}

 

 

1-2) less_func()

// 비교 함수: 주어진 두 hash_elem 구조체를 사용하여 페이지의 가상 주소를 비교합니다.
// 가상 주소가 큰 페이지가 작은 페이지보다 앞에 오도록 true 또는 false를 반환합니다.
bool less_func(const struct hash_elem *a, const struct hash_elem *b, void *aux) {
    const struct page *pg_a = hash_entry(a, struct page, hash_elem);
    const struct page *pg_b = hash_entry(b, struct page, hash_elem);

    return pg_a->va > pg_b->va;
}

 

 

2️⃣ struct page *spt_find_page (struct supplemental_page_table *spt, void *va)

 

• va가 속해있는 페이지가 spt 테이블에 있으면 해당 페이지를 return하고 없으면 NULL을 반환합니다.

struct page *
spt_find_page (struct supplemental_page_table *spt UNUSED, void *va UNUSED) {
	// 대상 페이지 생성 및 가상 주소 설정
	struct page target_page;
	target_page.va = va;

	// 페이지 테이블에서 페이지 검색
	struct hash_elem *elem = hash_find(&spt->pages, &target_page.hash_elem);

	// 페이지를 찾은 경우 해당 페이지 반환
	if (elem != NULL) {
		struct page *found_page = hash_entry(elem, struct page, hash_elem);
		return found_page;
	}
	// 페이지를 찾지 못한 경우 NULL 반환
	else {
        return NULL;
    }
}

 

 

 

3️⃣ bool spt_insert_page (struct supplemental_page_table *spt, struct page *page)

 

• 주어진 추가 페이지 테이블에 구조체 페이지를 삽입합니다.
• 이 함수는 주어진 추가 페이지 테이블에 가상 주소가 없는지 확인해야 합니다.

bool
spt_insert_page (struct supplemental_page_table *spt UNUSED,
		struct page *page UNUSED) {
	int succ = false;
	// 페이지를 해시 테이블에 삽입
	struct hash_elem *elem = hash_insert(&spt->pages, &page->hash_elem);

	//hash_insert함수는 성공하면 NULL반환
	if (elem == NULL)
		succ = true;
	
	return succ;
}

 

 

4️⃣ static struct frame * vm_get_frame(void)

 

• palloc_get_page를 호출하여 사용자 풀에서 새 물리 페이지를 가져옵니다.
• 사용자 풀에서 페이지를 성공적으로 가져온 경우, 프레임을 할당하고 멤버를 초기화한 후 반환합니다.
• 페이지 할당에 실패하는 경우 현재는 Panic을 사용해서 처리합니다.

static struct frame *
vm_get_frame (void) {
	struct frame *frame = NULL;
	void *kva = NULL;
	/* TODO: Fill this function. */

	if((kva = palloc_get_page(PAL_USER))==NULL){
		PANIC("To do");
	}
	else{
		frame = malloc(sizeof(struct frame));
		frame->kva = kva;
		frame->page = NULL;
	}

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

 

 

 

5️⃣ static bool vm_do_claim_page (struct page *page)

 

• 먼저 템플릿에서 이미 완료된 vm_get_frame을 호출하여 프레임을 가져옵니다.
• 가상 주소에서 페이지 테이블의 실제 주소로 매핑을 추가합니다. 
• 반환 값은 작업이 성공했는지 여부를 나타내야 합니다.

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. */
	void *page_va = page->va;
    void *frame_pa = frame->kva;

    // 현재 스레드의 페이지 테이블에서 페이지의 VA가 매핑되어 있는지 확인합니다.
    if (pml4_get_page(thread_current()->pml4, page_va) == NULL &&
        // 페이지 테이블에 페이지의 VA를 프레임의 PA로 매핑합니다.
        pml4_set_page(thread_current()->pml4, page_va, frame_pa, true)) {
        // 매핑이 성공하면 디스크로부터 페이지를 프레임으로 스왑 인합니다.
        return swap_in(page, frame_pa);
    }

    return false;
}

 

 

 

6️⃣ bool vm_claim_page(void *va UNUSED)

 

• 주어진 가상 주소 (VA)를 기반으로 페이지를 할당하고 프레임에 매핑하는 작업을 수행합니다.
• SPT에서 주어진 가상 주소 va에 해당하는 페이지를 찾아 변수 page에 할당합니다.
• 페이지가 NULL인 경우 false를 반환하여 페이지 할당에 실패했음을 나타냅니다.

bool
vm_claim_page (void *va UNUSED) {
	struct supplemental_page_table *spt = &thread_current()->spt;
	//spt에서 주어진 가상 주소 va에 해당하는 페이지를 찾아 변수 page에 할당합니다.
	struct page *page = spt_find_page(spt, va);
	/* TODO: Fill this function */
    if (page == NULL) {
        return false; 
    }

	return vm_do_claim_page (page);
}

 

 

 

 

---

 

여기까지 구현을 하면 Git book에 나와있는 Memory management를 순서대로 구현한 부분입니다. 

 

make check를 통해 작성한 코드가 작동하는지 확인을 해보려고하니 아래와 같이 대부분의 테스트가 Fail to launch initd가 뜨는 걸 확인할 수 있었습니다.

 

 

 

원인이 무엇이고 backtrace를 확인해보니 kernel_thread와 initd 부분에서 오류가 발생하는 걸 확인할 수 있었습니다.

오류를 확인해보기위해 PANIC의 문자가 출력되는 부분이 initd의  아래 조건이 발생하면 출력되는 형식입니다.

 

if (process_exec (f_name) < 0)
	PANIC("Fail to launch initd\n");

 

process_exec 함수의 반환값을 알아보기 위해 print를 찍어보다가 load 되는 부분에서 아래와 같이 Success value값이 false(0)으로 넘어와서 return -1을 넘겨주기 때문에 위와 같은 오류가 계속 발생하는 것을 확인할 수 있었습니다.

 

 

 

load에서 값이 0으로 넘어오는이유는 load 코드 안에 load_segment함수에서  vm_alloc_page_with_initializer함수를 호출하는데 

아래와 같이 아직 구현이 되어있지 않기때문에 err부분의 return false가 반환되는 것이었습니다. Git book에서는 아래 함수에 대한 언급이 Memory management에 없었어서 오류를 파악하느라 시간이 걸렸지만 이제 뒤에 Anonymous Page부분에 아래 함수를 구현하는 부분이 있으니 Anonymous Page까지 구현한 후에 다시 make check를 해보겠습니다.

 

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