[Pintos-KAIST] Project 3 : Memory Management

👩🏻‍💻 GITHUB 레포지토리
👩🏻‍💻 GITHUB Extend File Descriptor 이슈

프로젝트3 진입 전 주의사항 및 사전 설정

1️⃣ 두번째 과제인 Anonymous Page를 완성하기 전까지 VM 테스트 진행이 불가하다. (threads는 되어야함)
2️⃣ .vscode/c_cpp_properties.json defindes에 VM 추가

{
    "configurations": [
        {
            "name": "Linux",
            "includePath": [
                "${workspaceFolder}/**"
            ],
            "defines": [
                "USERPROG",
                "VM"
            ],
            "cStandard": "c17",
            "cppStandard": "gnu++17",
            "intelliSenseMode": "linux-gcc-x64"
        }
    ],
    "version": 4
}

---

코바코 (코드 바이 코드... 본인 코드에 해당 안되는걸수도 있음)
3️⃣ include/threads/thread.h #define USERPROG 삭제

4️⃣ threads/thread.c #ifdef USERPROG 추가

---

과제 설명

현재 핀토스에서는 레벨 4 페이지 테이블(pml4)을 사용하여 가상 메모리 주소와 물리 메모리 주소 간의 매핑 정보를 저장한다. 하지만 이것만으로는 충분하지 않다. Supplemental Page Table을 구현해 페이지에 대한 추가적인 정보들을 저장하게 되면 Page Fault와 Resource Management를 수월하게 진행할 수 있다.

💡 Supplemental Page Table

supplemental page table은 기존의 page table을 보완하기 위해 만든 것이다.

역할

크게 두 가지 역할을 수행한다.

• 페이지 폴트 시 커널이 추가 페이지 테이블에서 오류가 발생한 가상 페이지를 조회하여 어떤 데이터가 있어야 하는지 확인
• 프로세스가 종료될 때 커널이 추가 페이지 테이블을 참조하여 어떤 리소스를 free시킬 것인지 결정

struct supplemental_page_table 구현

먼저 추가 페이지 테이블의 구조체 struct supplemental_page_table을 구현한다. 그 후에 추가 테이블 구조체에 관계된 함수를 구현한다.

Supplemental page table을 구현하는 방식은 여러 가지가 있을 수 있다. 배열이나, 비트맵, 해시 테이블도 가능하다. hash table로 구현하자.

💡 frame table

frame table은 물리 메모리 내의 각 프레임의 정보를 갖고 있다.

역할

Frame table은 frame entry의 리스트로 구성되는데,
각 엔트리는 물리 메모리 프레임 테이블로 인해 eviction 정책, 즉 SWAP OUT/IN을 위한 프레임 교체 정책을 수행할 수 있게 된다.

struct frame_table 구현

• 사용 가능한 빈 프레임들의 집합
• frame_table은 리스트로 구현한다.
• frame_table은 전역적으로 구현해야한다.

---

구현

Supplemental Page Table

1. hash, hash_elem 구조체 추가

• include/vm/vm.h

1-1. hash.h include

#define VM_VM_H
#include <stdbool.h>
#include "threads/palloc.h"
#include <hash.h> /** Project 3-Memory Management */
...

1-2. spt_hash 추가

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

struct supplemental_page_table {
	 struct hash spt_hash; /** Project 3-Memory Management */
};

1-3. hash_elem 추가

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

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
	};
	/** Project 3-Memory Management */
	struct hash_elem hash_elem;
};

2. supplemental_page_table_init() 구현

• vm/vm.c
• supplementary page table을 초기화한다.
• hash table을 사용하기로 했으므로 hash_init을 사용하여 초기화한다.
• hash_init에서 필요한 page_hash와 page_less는 3번과 4번에 설명되어 있다.

void
supplemental_page_table_init (struct supplemental_page_table *spt UNUSED) {
	/** Project 3-Memory Management */
	hash_init(spt, page_hash, page_less, NULL);
}

3. page_hash() 구현

• spt에 넣을 인덱스를 해시 함수를 돌려서 도출한다.
• hash table이 hash elem을 원소로 가지고 있으므로 페이지 자체에 대한 정보를 가져온다.
• 인덱스를 리턴해야하므로 hash_bytes로 리턴한다.

3-1. 선언

• include/vm/vm.h

/** Project 3-Memory Management */
uint64_t page_hash(const struct hash_elem *e, void *aux);

3-2. 구현

• vm/vm.c

/** Project 3-Memory Management */
uint64_t 
page_hash(const struct hash_elem *e, void *aux)
{
	struct page *page = hash_entry(e, struct page, hash_elem);
	return hash_bytes(page->va, sizeof *page->va);
}

4. page_less() 구현

• 체이닝 방식의 spt를 구현하기 위한 함수이다.
• 해시 테이블 버킷 내의 두 페이지의 주소값을 비교한다.

4-1. 선언

• include/vm/vm.h

/** Project 3-Memory Management */
uint64_t page_hash(const struct hash_elem *e, void *aux);
bool page_less(const struct hash_elem *a, const struct hash_elem *b, void *aux);

4-2. 구현

• vm/vm.c

/** Project 3-Memory Management */
bool 
page_less(const struct hash_elem *a, const struct hash_elem *b, void *aux)
{
	struct page *page_a = hash_entry(a, struct page, hash_elem);
	struct page *page_b = hash_entry(b, struct page, hash_elem);

	return page_a->va < page_b->va;
}

5. spt_find_page() 구현

• vm/vm.c
• supplementary page table에서 va에 해당하는 구조체 페이지를 찾아 반환한다.

struct page *
spt_find_page (struct supplemental_page_table *spt UNUSED, void *va UNUSED) {

	/** Project 3-Memory Management */
	struct page *page = (struct page *)malloc(sizeof(struct page));     
    page->va = pg_round_down(va);                                       
    struct hash_elem *e = hash_find(&spt->spt_hash, &page->hash_elem);  
    free(page);                                                         

    return e != NULL ? hash_entry(e, struct page, hash_elem) : NULL;
}

6. spt_insert_page() 구현

• vm/vm.c
• supplementary page table에 struct page를 삽입한다.
• 가상 주소가 이미 supplementary page table에 존재하면 삽입하지 않고, 존재하지 않으면 삽입한다.

bool
spt_insert_page (struct supplemental_page_table *spt UNUSED,
		struct page *page UNUSED) {
	/** Project 3-Memory Management */
	return hash_insert(&spt->spt_hash, &page->hash_elem) ? false : true;
}

Frame Management

7. frame_table 구조체 추가

7-1. frame_table 추가 및 초기화

• vm/vm.c

/* vm.c: Generic interface for virtual memory objects. */

#include "threads/malloc.h"
#include "vm/vm.h"
#include "vm/inspect.h"

/** Project 3-Memory Management */
static struct list frame_table; 

/* Initializes the virtual memory subsystem by invoking each subsystem's
 * intialize codes. */
void
vm_init (void) {
	vm_anon_init ();
	vm_file_init ();
#ifdef EFILESYS  /* For project 4 */
	pagecache_init ();
#endif
	register_inspect_intr ();
	/* DO NOT MODIFY UPPER LINES. */
	
	/** Project 3-Memory Management */
	list_init(&frame_table);
}

7-2. frame_elem 추가

• include/vm/vm.h

struct frame {
	void *kva;
	struct page *page;
	/** Project 3-Memory Management */
	struct list_elem frame_elem; 
};

8. vm_get_frame() 구현

• vm/vm.c
• palloc_get_page 함수를 호출하여 사용자 풀에서 새로운 physical page(frame)를 가져온다.
• 사용 가능한 page가 없다면 swap out을 수행한다.

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

	/** Project 3-Memory Management */
	struct frame *frame = (struct frame *)malloc(sizeof(struct frame));
	ASSERT (frame != NULL);

	frame->kva = palloc_get_page(PAL_USER | PAL_ZERO);  

    if (frame->kva == NULL)
        frame = vm_evict_frame();  
    else
        list_push_back(&frame_table, &frame->frame_elem);

    frame->page = NULL;

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

9. vm_claim_page() 구현

• vm/vm.c
• 인자로 주어진 va에 페이지를 하나 할당한다.
• 해당 페이지로 vm_do_claim_page를 호출한다.

bool
vm_claim_page (void *va UNUSED) {
	struct page *page = NULL;
	/** Project 3-Memory Management */
	struct page *page = spt_find_page(&thread_current()->spt, va);

    if (page == NULL)
        return false;

	return vm_do_claim_page (page);
}

10. vm_do_claim_page() 구현

• vm_get_frame() 함수를 통해 프레임 하나를 얻는다.
• 프레임의 페이지로 얻은 페이지를 연결한다.
• 프레임의 물리적 주소로 얻은 프레임을 연결한다.
• 현재 페이지 테이블에 가상 주소에 따른 frame을 매핑한다.

10-1. writable 구조체 추가

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
	};
	/** Project 3-Memory Management */
	struct hash_elem hash_elem;
	bool writable;
};

10-2. mmu.h include

• vm/vm.c

/** Project 3-Memory Management */
#include "threads/mmu.h"
static struct list frame_table; 

10-3. vm_do_claim_page() 구현

• vm/vm.c

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

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

    if (!pml4_set_page(thread_current()->pml4, page->va, frame->kva, page->writable))
        return false;

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