[PintOS] Project3-1 Supplement Page Table

Supplement Page Table

보충 페이지 테이블은 각 페이지에 대한 추가 데이터를 가지고 있어 페이지테이블을 보완한다. 보충 페이지 테이블이 필요한 이유는 크게 두가지다

• 페이지 폴트 발생 시, 커널이 보충 페이지 테이블을 참고해 프레임과 매핑이 안되었는지 안되었을때 프레임에 할당해야할 데이터는 어떤 데이터인지를 확인한다.
• 커널은 프로세스가 종료될 때 메모리 누수를 막기위해 해제해야할 페이지를 보충 페이지 테이블을 참조해 결정한다.

---

 

페이지 폴트 처리

페이지 폴트 발생시 커널은 anonymous page인지 file-backed페이지인지 확인한다. 파일 또는 스왑 슬롯에서 페이지를 가져와야 한다면. userprog/exception.c의 페이지 폴트 핸들러 page_fault()는 vm/vm.c의 페이지 폴트 핸들러 vm_try_handle_fault()를 호출한다. 페이지 폴트 핸들러는 대략 다음과 같은 작업을 수행한다:

1. 보충 페이지 테이블에서 폴트가 발생한 페이지를 찾는다. 메모리 참조가 유효한 경우, 보충 페이지 테이블 항목을 사용하여 페이지에 들어갈 데이터의 위치를 찾는다. 이 데이터는 파일 시스템, 스왑 슬롯 또는 0으로 초기화된 페이지다. 보충 페이지 테이블을 참조해 사용자 프로세스가 액세스하려고 하는 주소에서 데이터를 예상해서는 안 된다고 나타내거나, 페이지가 커널 가상 메모리 내에 있거나, 액세스가 읽기 전용 페이지에 쓰기를 시도하는 경우 프로세스를 종료시키고 그에 따라 모든 리소스를 해제한다.
2. 페이지를 저장할 사용가능한 물리 메모리의 프레임을 얻는다.
3. 파일 시스템이나 스왑에서 읽거나, 0으로 만드는 등의 방법으로 데이터를 프레임으로 가져온다.
4. 폴트가 발생한 가상 주소에 대한 페이지 테이블 항목을 threads/mmu.c 물리 페이지와 매핑한다.

---

구현

supplement_page_table

/* Representation of current process's memory space.
 * We don't want to force you to obey any specific design for this struct.
 * All designs up to you for this. */
struct supplemental_page_table {
    struct hash h;
};

보충 페이지 테이블을 해시자료구조를 사용해 만든다.

page구조체는 uinit_page, anon_page, file_page의 추상화다

struct page를 보면 union 구조체로 페이지들을 가지고 있다. union공용체 는 모든 멤버가 동일한 메모리 위치를 공유하는 사용자 정의 형식이라고한다. 즉 page는 타입에따라 uinit_page의 정보를 가지고 있을 수 있고 anon_page의 정보를 가질 수 있고, file_page의 정보를 가질 수 있다.

supplement_page_table에 page를 삽입하여 page들을 관리한다. page 각각의 공용체에는 특화된 데이터 필드를 정의하고 page 구조체에는 공통된 필드를 정의힌다.

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;
    
    /* 공통 필드 */
	bool writable;

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

pml4 페이지 테이블이 있는데 보충 테이블이 필요한 이유가 뭘까?

페이지 테이블은 단순 페이지와 프레임이 매핑이 되었는지 즉, 가상주소가 현재 물리프레임과 매핑이되었는지의 정보만 가지고 있다 그렇기 때문에 페이지 테이블을 보충(supplement)하는 테이블이 필요한거다.

이때 보충 페이지 테이블은 할당받은 페이지에 대한 정보(unint, anonymouse, file-backed)를 가지고 있다. 페이지 폴트 발생시 커널은 supplement_page_table에서 페이지 폴트가 발생한 주소의 페이지를 가져와 알당되지 않은 lazy load하는 페이지라면 프레임을 할당하고 페이지와 매핑을 한다.

supplement_page_table_init

/* Initialize new supplemental page table */
void supplemental_page_table_init(struct supplemental_page_table *spt UNUSED)
{
	if (!hash_init(&spt->spt_hash, page_hash, page_less, NULL))
		exit(-1);
}

spt의 해시테이블을 초기화 해야한다 요소들을 어느 버킷에 담을지 hash_hash_func, 체이닝 기법으로 구현된 해시 테이블의 버킷 리스트에에 어느 기준으로 삽입할지 hash_less_func인자를 정해준다. 이 인자는 함수형 포인터를 사용한다.

page_hash

/* Returns a hash value for page p. */
uint64_t
page_hash(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);
}

page_less

/* Returns true if page a precedes page b. */
bool page_less(const struct hash_elem *a_,
			   const struct hash_elem *b_, void *aux UNUSED)
{
	const struct page *a = hash_entry(a_, struct page, hash_elem);
	const struct page *b = hash_entry(b_, struct page, hash_elem);

	return a->va < b->va;
}

버킷 리스트에 어느 기준으로 삽일할지 정하는 hash_less_func를 정한다. 가상주소 오름차순으로 정렬한다.

---

spt_insert_page

보충 페이지 테이블에 struct page의 hash_elem을 삽입한다

bool
spt_insert_page (struct supplemental_page_table *spt UNUSED,
		struct page *page UNUSED) {
	int succ = false;
	
	/* insert에 성공하면 e == NULL이 된다.(hash_insert에 의해) */
	if (!hash_insert(&spt->spt, &page->hash_elem))
		succ = true;

	return succ;
}

---

spt_find_page

보충 페이지 테이블에 삽입된 페이지를 찾는다.

struct page *
spt_find_page (struct supplemental_page_table *spt UNUSED, void *va UNUSED) {
	struct page *page = NULL;
	/* va가 page의 시작점을 가리키고 있지 않을 수 있으므로
		round_down을 통해 page 시작점의 주소를 구한다. */
	page->va = pg_round_down(va);
	
	/* page->va에 해당하는 주소에 위치한 hash_elem을 찾아온다. */
	struct hash_elem *e = hash_find(&spt->spt, &page->hash_elem);
	
	/* 해당하는 hash_elem을 찾을 수 없으면 NULL을 리턴한다. */
	if (e == NULL)
		return NULL;
	
	/* 해당하는 page가 존재하므로 page 구조체를 구해서 리턴한다. */
	page = hash_entry(e, struct page, hash_elem);

	return page;
}

---

supplement_page_table_kill

보충 페이지 테이블에 존재하는 페이지들을 제거하는 함수다 여기서 주의해야할 점은 spt 자체를 삭제하는것이 아닌 page를 제거하는 것이다. spt는 쓰레드 구조체에 멤버 변수로 선언되어있으니 쓰레드가 할당 해제될때 같이 제거된다.

/* Free the resource hold by the supplemental page table */
void supplemental_page_table_kill(struct supplemental_page_table *spt UNUSED)
{
	/* 1. hash_destroy에서 buckets에 달린 page와 vme를 삭제해주어야 한다. */
	/* bucket에 대한 해제는 hash_destroy에서,
		page와 vme에 대한 해제는 hash_free_func에서 수행한다. */
	hash_clear(&spt->spt_hash, hash_free_func);
}

hash_destroy가 아닌 hash_clear를 사용하는 이유

supple_ment_page_kill 흐름도

2. supplemental_page_table_init

spt의 hash table 내의 bucket을 할당

6. hash_destroy or hash_clear?

if) hash_destroy → free(h→bucket) and free(page)
if) hash_clear → free(page)

hash_destroy: buckets를 해제한 후 hash_clear를 호출한다.
hash_clear : buckets를 순회한다. -> hash_elem에 대해 destructor를 호출한다. -> list를 초기화한다.

❌ hash_destroy를 호출하면 spt_init에서 기껏 할당해준 bucket들을 다시 해제하게 된다.

⭕️ hash_clear를 사용해 bucket 내의 page만 destroy하고, bucket 자체는 free 하지 않는다.

💭 hash_action_func에서 hash_elem에 대해서는 free를 수행하면 안된다. hash_elem이 해시 테이블 내에서 전후 관계 정보를 담고 있기 때문이다.

---

hash_free_func

page가 가지를 리소스를 destroy하고 구조체 page를 할당해제해준다

/* page 및 hash_elem 제거*/
void 
hash_free_func (struct hash_elem *e, void *aux) {
	/* hash_elem에 맞는 page를 찾는다. */
	struct page *p = hash_entry(e, struct page, hash_elem);
	
	destroy(p); // 물리 메모리에 올라간 page를 제거한다
	free(p); // 우리가 만든 page 자체를 제거한다
}

---

참고

https://casys-kaist.github.io/pintos-kaist/project3/introduction.html