[PintOS] Project3 Memory Management (1)

Baedonguri·2022년 6월 17일

Big picture: Running a user program

이번 Project3 : Virtual Memory을 구현하는 이유는 다음과 같다.

물리적 메모리는 제한되어 있지만 많은 프로세스가 물리적 메모리를 사용하려고 한다.
물리적 메모리는 모든 프로세스의 페이지를 항상 저장할 만큼 충분히 크지 않기 때문이다.
물리적 메모리에 페이지가 필요하지 않은 경우 "page out"된다.(스왑 테이블 또는 파일 시스템에 기록됨).
프로세스가 페이지를 필요로 하고 물리적 메모리에 없으면 "page in" 되어야 한다.

현재 Pintos에서는 level4_page_table(pml4)을 사용하여 가상 메모리 주소와 물리 메모리 주소 간의 매핑 정보를 저장하는데, 이것만으로는 충분하지 않다.
따라서 Page Fault와 Resource Management를 수월하게 진행할 수 있도록 Supplemental Page Table을 구현해 페이지에 대한 추가적인 정보들을 저장한다.

Terminology

Page : 가상 메모리의 연속 영역
Frame : 물리적 메모리의 연속 영역
Page Table : 가상 주소를 물리적 주소로 변환하는 데이터 구조 (페이지 → 프레임)
Eviction : 프레임에서 페이지를 제거하고, 잠재적으로 스왑 테이블 또는 파일 시스템에 쓰기
Swap Table : 제거된 페이지가 스왑 파티션에 기록되는 곳

Data structures you must design

다음은 이번 과제에서 구현해야 할 자료구조를 어떻게 설계해야 하는지에 대한 가이드이다.

보충 페이지 테이블 (supplemental page table)
데이터 위치(프레임/디스크/스왑), 해당 커널 가상 주소에 대한 포인터,
active vs. inactive 등과 같은 각 페이지에 대한 보조 데이터를 추적하는 프로세스별 데이터 구조로 설계해야 한다.
프레임 테이블 (Frame table)
할당되거나 사용 가능한 물리적 프레임을 추적하는 전역(global) 데이터 구조로 설계해야 한다.

Many choices for data structures

supplemental page table을 구현할 때, 다음과 같은 방식을 선택할 수 있다.
우리 조는 해쉬테이블을 이용하여 spt를 구현하기로 했다.

Arrays (배열) : 가장 단순한 접근 방식, 하지만 배열이 드물게 채워져 공간을 낭비할 수 있음
Lists (리스트) : 매우 간단하지만, 목록을 탐색하는 데 많은 시간이 소요될 수 있음
Bitmaps (비트맵) : 각각 참 또는 거짓일 수 있는 비트 배열, 동일한 리소스 집합에서 사용률을 추적
Hash Tables : key, value로 데이터를 저장하는 자료구조로, 빠르게 데이터를 검색할 수 있음 (시간복잡도 O(1))

Concept of lazy loading

가상 주소가 생성되면(mmap), pintos는 페이지 구조체를 가상 주소에 연결한다.
각 가상 주소는 익명 메모리(anonymous memory), 파일 지원 메모리(file-backed) 등 다양한 용도로 사용된다.
- 페이지 구조체는 정보를 반영합니다
- 페이지 구조체를 할당한다고 해서 물리적 프레임이 가상 주소에 할당되는 것은 아니다.
  실제 물리적 값은 page→va 에 할당된다.

What is a Supplemental Table Page

기존의 page table을 보완하기 위해 만든 것으로, page들에 대해 추가적인 데이터로 페이지 테이블을 보완하기 위한 목적.
크게 두가지 기능을 수행한다.

Page Fault 발생 시 커널이 spt에서 오류가 발생한 가상 페이지를 조회하여 어떤 데이터가 있어야 하는지 확인한다.
프로세스가 종료될 때 커널이 spt를 참조하여 어떤 리소스를 free시킬 것인지 결정한다.

<추가자료 (참고)>
Supplemental Table Page을 만든 이유

page-table은 page-directory-entry마다 하나씩 가지고있고, 서로 다른 virtual address를 가지지만 같은 physical memory를 참조하는 경우가 충분히 발생할 수 있기 때문이다.
referencing하고있는 table들은 전부 다르지만, 결국 같은 physical address를 가르키고 있는 것이다. 이러한 경우를 다루기 위해서는 하나의 프로세스가 어떠한 physical memory를 참조하고 있는지에 대한 정보가 필요하고, 이를 위해서 추가적인 page table이 필요한 것이다.
기존의 page-table은 physical memory를 향한 일방적인 pointing에 불과하다.
때문에 physical-memory의 값이 바뀌어 있으면 패닉에 빠질 수 밖에 없다.
기존에 어떠한 데이터가 있는지에 대한 정보를 전혀 가지고 있지 않기 때문에 이러한 문제가 발생하면 해결할 수가 없다. 따라서 supplementary page table에는 원래 physical-memory에 들어가 있어야 할 데이터가 어떤 것인지에 대한 정보를 가지고 있어야 한다.

그렇다면 이 spt는 어떻게 생겨먹은 구조체일까?

struct supplemental_page_table {
	struct hash *pages;
};

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

해시 테이블은 (key, value)로 데이터를 저장하는 자료구조로, 빠르게 데이터를 검색할 수 있다고 한다.
(시간복잡도 O(1)).
해시 테이블은 각각의 key값에 해시함수를 적용해 배열의 고유한 index를 생성하고,
이 index를 활용하여 값을 저장하거나 검색한다.
여기서 실제 값이 저장되는 장소를 버킷 또는 슬롯이라고 한다. 해시 테이블의 인덱스 값들이 실제 주소를 가지고 있는 버킷을 찾는다.
spt에서는 프로세스가 요청한 페이지들에 대해서만 물리 페이지를 할당하기 위해서 해시 테이블 자료구조가 사용된다.

Supplemental Table Page Implement

void supplemental_page_table_init (struct supplemental_page_table *spt);

supplemental_page_table_init (struct supplemental_page_table *spt UNUSED) {
	spt->pages = calloc(sizeof(struct hash), 1); 
	hash_init(spt->pages, page_hash, page_less, NULL);
}

우선 supplmental_page_table를 초기화 해주는 작업을 수행하도록 한다.
이 함수는 새 프로세스가 실행될 때 (initd()), 프로세스가 fork될 때, (__do_fork()) 실행된다.
참고로, 이 spt도 프로세스마다 하나씩 갖고 있다.
spt구조체 안에 hash를 포인터로 선언했기 때문에, hash table 사용을 위해 동적 할당을 해준 뒤
hash_init 함수를 호출한다.

hash_init에 들어가는 인자는 hash구조체, hash함수, 비교함수, aux 가 들어간다.

해시 요소에 대한 해시 값을 계산 후 리턴하는 함수의 포인터인데,
va를 hash화해서 고유한 인덱스로 만들고, 어떤 버킷에 넣을지를 결정해주는 역할을 한다.

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

해시 요소를 비교하는 함수의 포인터

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

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

struct page *spt_find_page (struct supplemental_page_table *spt UNUSED, void *va UNUSED) {
	struct page page;
	struct hash_elem *e;
	page.va = pg_round_down(va);
	e = hash_find(spt->pages, &page.hash_elem);
	return e != NULL ? hash_entry (e, struct page, hash_elem) : NULL;
}

지정된 spt에서 va에 해당하는 struct page를 찾기 위한 함수를 정의한다.
해당 va가 속해 있는 페이지 시작 주소를 가지는 page를 생성해준뒤, 해당 page가 spt에 있는지 확인한다.
만약 존재한다면 해당 페이지를 리턴하고, 없다면 NULL을 리턴한다.

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;
	/* TODO: Fill this function. */
	if (!hash_insert(spt->pages, &page->hash_elem))
		succ = true;
	return succ;
}

지정된 spt에 page를 삽입하는 함수이다.
hash_insert 함수는 해당 page가 들어갈 bucket을 찾고 이미 해당 page가 존재하는지 체크한 뒤,
없다면 bucket에 삽입해준다.

struct hash_elem *hash_insert (struct hash *h, struct hash_elem *new) {
	struct list *bucket = find_bucket (h, new);
	struct hash_elem *old = find_elem (h, bucket, new);

	if (old == NULL)
		insert_elem (h, bucket, new);

	rehash (h);

	return old;
}

hash_insert 함수는 삽입에 성공하면 NULL을 리턴하기 때문에 출력값이 NULL일 경우 성공을 리턴한다.

What is a Frame table & Implement

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

/* The representation of "frame" */
struct frame {
  void *kva;
  struct page *page;
};

커널 가상 주소인 kva와 페이지 구조인 page라는 두 개의 필드만 존재하는데,
프레임 관리 인터페이스를 구현할 때 구성원을 추가할 수 있다

static struct frame *vm_get_frame (void)

struct list frame_table
struct lock frame_lock

전역으로 사용할 프레임 테이블 선언

static struct frame *vm_get_frame (void) {
	struct frame *frame = (struct frame*)calloc(1,sizeof(struct frame));
	/* TODO: Fill this function. */
	ASSERT (frame != NULL);
	ASSERT (frame->page == NULL);

	frame->kva = palloc_get_page(PAL_USER); 
	if (frame->kva == NULL){
		PANIC("to do");
	}
	 list_push_back(&frame_table, &frame->frame_elem);

	 frame->page = NULL;

	return frame;
}

또한 프레임 리스트와 lock를 초기화 해준다.

void vm_init(void){
	...
#endif
	register_inspect_intr();

    list_init(&frame_list);
    lock_init(&frame_lock);

    ...

실제 물리 프레임을 얻는 작업을 수행하는 함수이다.
palloc_get_page를 호출하여 사용자 풀에서 새 실제 페이지를 가져온다.
페이지를 성공적으로 가져오면 프레임도 할당하고 구조체의 멤버을 초기화한 뒤 리턴해준다.
만약 페이지 할당에 실패하는 경우는 swap out을 처리해야 하지만, 지금은 gitbook 요구사항에 따라
PANIC("todo")로 설정해준다.

bool vm_do_claim_page (struct page *page)

static bool
vm_do_claim_page (struct page *page) {
	struct frame *frame = vm_get_frame ();
	struct thread *t = thread_current();
	/* Set links */
	frame->page = page;
	page->frame = frame;
	/* TODO: Insert page table entry to map page's VA to frame's PA. */

	if (pml4_get_page(t->pml4, page->va) == NULL &&  pml4_set_page (t->pml4, page->va, frame->kva, page->writable)){
		return swap_in(page, frame->kva);
	}
	return false;
}

claim은 물리적 프레임인 페이지를 할당하는 것을 의미하는데, 즉, 유저 가상 메모리 공간에 있는 페이지를
물리 프레임에 할당하는 것이다.
먼저 vm_get_frame을 호출해서 새 프레임을 얻고 인자로 받은 page와 서로 연결 시킨 뒤,
pml4_set_page를 통해 가상주소에서 물리주소로 매핑하는 작업을 수행한다.

만약 매핑 작업이 성공했다면 swap_in을 수행하고, 실패했다면 false를 리턴한다.

bool vm_claim_page (void *va)

bool vm_claim_page (void *va UNUSED) {
	struct page *page = NULL;
	// struct thread *t = thread_current();
	/* TODO: Fill this function */
	page = spt_find_page(&thread_current()->spt, pg_round_down(va));
	if (page == NULL){
		return false;
	}
	return vm_do_claim_page (page);
}