대체 어떤 끔찍한 말을 썼길래 *발을 거르고 검열당한 것일까
아마 그건 핀토스가 아닐까?

Memory Management

Supplemental Page Table

PintOS는 pml4라는 4단계로 이루어진 페이지 테이블을 이용하여 가상 메모리와 물리 메모리간의 매핑을 관리한다. 하지만 page fault 와 resource management를 위해서 각 페이지에 대한 추가 정보를 가지고 있는 SPT를 만들 필요가 있다. 3주차의 첫 과제는 이 SPT를 구현하는 것이다.

supplement page table은 다양한 방식으로 구현할 수 있다. 이러한 방식은

배열(array), 연결리스트(linked list), 해시 테이블(Hash table), 비트맵(Bitmap)
정도가 있다고 한다.
각 자료구조의 장단점을 살펴보면

• array: 가장 구현이 간단하나 공간복잡도가 크다는 문제(메모리 용량을 낭비)
• linked list: 탐색 시 시간 복잡도 - O(n) 낭비가 크다.
• Hash table: 탐색 시 시간복잡도 O(1)이라는 장점이 있으며 array와 달리 연속적인 공간을 쓰는 개념이 아니기에 공간복잡도 측면에서도 효율적이다.
• Bitmap: 말 그대로 해당 정보를 비트에 매핑시키는 자료구조. 비트로 정보를 저장하기에 공간 복잡도 측면에서 매우 효율적이다. 하지만 구분해야 할 서로 다른 자료가 많으면 많을수록 복잡해진다.

우리 조는 Hash table을 사용하기로 했다. 사실 Hash Table말고 다른 방법을 시도한 (이전 기수의) 기록을 찾는게 더 어렵다..

struct supplemental_page_table 에 hash_elem을 추가

@include/vm/vm.h

struct supplemental_page_table {
	struct hash spt_hash;
};

hash 함수의 원형은 lib/kernel/hash.h에서 확인할 수 있다.

srtuct page 에 hash_elem을 추가

@include/vm/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 */

	//project 3
	//hash.h파일의 주석에 잠재적으로 hash table의 value가 될 수 있는 page는 모두 hash_elem을 멤버로 가져야 한다는 내용이 있다.
	/* hash table을 위한 hash function이 돌아가기 위한 필수 멤버 */
	struct hash_elem hash_elem;
	bool writable;
	//project 3

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

key 로는 page -> va값이 들어가고, value로는 struct page를 받는 hash_elem을 추가해준다.

struct hash

struct hash {
	size_t elem_cnt;            /* Number of elements in table. */
	size_t bucket_cnt;          /* Number of buckets, a power of 2. */
	struct list *buckets;       /* Array of `bucket_cnt' lists. */
	hash_hash_func *hash;       /* Hash function. */
	hash_less_func *less;       /* Comparison function. */
	void *aux;                  /* Auxiliary data for `hash' and `less'. */
};

bucket이라는 list가 있고, 이 list 안에 hash값이 담기는 방식이다. 만약 hash 값이 같은 hash_elem 이 들어온다면 저 bucket 안에 linked list로 연결되어 담기게 된다.

hash_hash_func 와 hash_less_func는 우리가 직접 만들어야 한다. 왜냐하면...

hash_init()

/* Initializes hash table H to compute hash values using HASH and
   compare hash elements using LESS, given auxiliary data AUX. */
bool
hash_init (struct hash *h,
		hash_hash_func *hash, hash_less_func *less, void *aux) {
	h->elem_cnt = 0;
	h->bucket_cnt = 4; // 0, 1, 2, 3
	h->buckets = malloc (sizeof *h->buckets * h->bucket_cnt); 
	h->hash = hash;
	h->less = less;
	h->aux = aux;

	if (h->buckets != NULL) {
		hash_clear (h, NULL);
		return true;
	} else
		return false;
}

hash init 함수의 인자로 hash_hash_func과 hash_less_func를 받기 때문이다.

//project 3
//page의 멤버인 hash_elem을 통해 page를 찾고, 그 page의 virtual address에 hash값을 넣는 함수(hash_hash_func 역할)
unsigned page_hash_func (const struct hash_elem *p_, void *aux UNUSED) {
	const struct page *p = hash_entry(p_, struct page, hash_elem);
	return hash_bytes(&p->va, sizeof(p->va));
}

//해시 태이블 내 두 페이지 요소에 대해 페이지 주소 값을 비교하는 함수(hash_less_func 역할)
static unsigned page_less_func(const struct hash_elem *a, const struct hash_elem *b, void *aux) {
	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 (uint64_t)p_a -> va < (uint64_t)p_b -> va;
}

이 아래에 page_insert() 함수와 page_delete() 함수도 만들어줬다.

//해당 페이지에 들어있는 hash_elem 구조체를 인자로 받은 해시 테이블에 삽입하는 함수
bool page_insert(struct hash *h, struct page *p) {
	if (!hash_insert (h, &p -> hash_elem)) {
		return true;
	} else {
		return false;
	}
}

bool page_delete (struct hash *h, struct page *p) {
  return hash_delete (&h, &p->hash_elem);
}

supplemental_page_table_init()

/* Initialize new supplemental page table */
void
supplemental_page_table_init (struct supplemental_page_table *spt UNUSED) {

	//project 3
	hash_init(&spt -> spt_hash, page_hash_func, page_less_func, NULL );
	//project 3
}

lib/kernel/hash.c에 미리 설정되어있는 hash_init() 함수로 해쉬 테이블을 init할 수 있다.

spt_find_page()

/* Find VA from spt and return page. On error, return NULL. */
struct page *
spt_find_page (struct supplemental_page_table *spt, void *va) {

	//project 3
	struct page *dummy_page = (struct page *)malloc(sizeof(struct page));
	struct hash_elem *e;
	// /include/threads/vaddr.h에 있는 '주소를 인자로 가장 가까운 페이지 경계까지 내림하는 함수'
	dummy_page->va = pg_round_down(va);
	//해시 함수를 이용하여 페이지 검색
	e = hash_find(&spt -> spt_hash, &dummy_page -> hash_elem);

	if (e != NULL) {
		dummy_page = hash_entry(e, struct page, hash_elem);
	} else {
		dummy_page = NULL;
	}

	return dummy_page;
	//project 3
}

인자로 주어진 해시 테이블에서 인자로 받은 va가 있는지 찾는 함수이다. va가 속해있는 page가 해시 테이블 spt에 존재한다면 이를 return 한다. 없으면 NULL을 반환한다.

spt_insert_page()

supplementary page table에 struct page를 삽입하는 함수이다.
이때, 가상 주소가 이미 supplementary page table에 존재하는지 확인하고 존재한다면 삽입하지 않고, 존재하지 않으면 삽입한다.

spt_insert_page (struct supplemental_page_table *spt UNUSED,
		struct page *page UNUSED) {

	//project 3
	return page_insert(&spt -> spt_hash, page);
	//project 3
}

아까 만들었던 page_insert() 함수를 여기서 사용했다.

frame management

struct frame

/* The representation of "frame" */
struct frame {
	void *kva;
	struct page *page;
	//project 3
	struct list_elem frame_elem;
	//project 3
};

frame을 list로 관리하기 위해서 list_elem을 추가했다.
vm.c에 전역변수 frame_table을 추가해서 frame을 관리할 수 있게 해준다.

@vm/vm.c
struct list frame_table;

vm_get_frame()

static struct frame *vm_get_frame (void) {
	//project 3
	//malloc으로 빈 frame 할당
	struct frame *new_frame = (struct frame *)malloc(sizeof(struct frame));
	if (new_frame == NULL || new_frame -> kva == NULL) {
		PANIC("todo");
		return NULL;
	}
	
	//frame의 kva에 user pool의 페이지 할당
	//anonymous case를 위해 일단 PAL_ZERO
	new_frame -> kva = palloc_get_page(PAL_USER | PAL_ZERO);
	//할당이 안 됐을 때 예외처리
	if (new_frame -> kva == NULL) {
		//user pool 이 다 찼다는 뜻이므로 evict_frame 으로 빈자리를 만든다.
		new_frame = vm_evict_frame();
		//hash에서도 삭제하는 코드 필요..?
		new_frame -> page = NULL;
		return new_frame;
		// PANIC("todo");
	}
	//frame_table linked list에 frame_elem 추가
	list_push_back(&frame_table, &new_frame->frame_elem);
	new_frame->page = NULL;
	//project 3
	
	ASSERT (new_frame != NULL);
	ASSERT (new_frame->page == NULL);

	return new_frame;
}

swap 기능을 아직 구현하지 않았다면 user pool이 다 찼을 경우를 대비한 코드를 아직 쓰지 않아도 괜찮다.
이 함수를 구현하는 과정 중 왜 frame은 malloc으로 할당하고, new_frame -> kva는 palloc으로 할당하는지에 대해서 많은 탐구와 토론이 있었지만 다음에 이에 대해 정리할 수 있는 기회가 있을 때 쓰겠다.
한마디로 줄이면 kernel 영역할당에선 malloc, user 영역할당에서는 palloc(PAL_USER)를 쓰는 것이다.
이 함수는 palloc()으로 frame을 가져오는데, 사용가능한 page가 없다면 frame을 제거해서 memory를 확보하는 역할이다.
그리고 새롭게 확보한 frame을 frame table로 관리한다.

vm_claim_page ()

이 함수는 주소 va에 해당하는 page로 vm_do_claim_page 함수를 호출한다.
먼저, va에 해당하는 page(virtual page)를 가져오고
해당 페이지로 vm_do_claim_page()를 호출한다.

/* Claim the page that allocate on VA. */
bool
vm_claim_page (void *va UNUSED) {
	//project 3
	struct page *page = NULL;
	//spt_find_page 함수 내에서 malloc으로 페이지를 할당해준다.
	//이후 va를 가지고 page를 찾아낸다.
	struct supplemental_page_table *spt = &thread_current ()->spt;
	page = spt_find_page (spt, va);
	if (page == NULL) {
		return false;
	}
	
	return vm_do_claim_page (page);
	//project 3
}

vm_do_claim_page()

실제로 page를 claim 하는 함수이다. 인자로 주어진 page에 physical frame을 할당한다.

/* Claim the PAGE and set up the mmu. */
static bool
vm_do_claim_page (struct page *page) {
	//project 3
	// 페이지가 유효하지 않거나, 페이지가 이미 차지된 경우
	if (!page || page->frame)
		return false;

	struct frame *frame = vm_get_frame (); //프레임 할당받음
	struct thread *cur = thread_current ();
	/* Set links */
	frame->page = page;
	page->frame = frame;
	//frame 과 page를 연결해준다
	/* TODO: Insert page table entry to map page's VA to frame's PA. */
	pml4_set_page (cur -> pml4, page -> va, frame->kva, page -> writable);
	
	return swap_in (page, frame->kva);
	//project 3
}

pml4_set_page() 함수를 이용하여 가상 주소와 물리 주소의 매핑을 페이지 테이블에 추가해준다.