[TIL/06.05] PintOS VM - Memory Management

참고 자료

https://casys-kaist.github.io/pintos-kaist/project3/introduction.html
https://oslab.kaist.ac.kr/pintosslides/

• 🚨 두번째 링크인 Kaist EE 자료는 64비트가 아닌 32비트 기준으로 서술되어 있음

요구사항

AS-IS

• 현재 실행 가능한 파일 전체가 모두 메모리에 적재
  • 실행하지 않는 부분도 메모리에 적재되어 비효율 발생
• 프로세스가 스택을 다 채워 Overflow가 발생하면 프로세스를 Kill

TO-BE

• page fault 핸들러 함수를 수정, Demand Paging(lazy loading) 구현
• Supplemental Page Table 구현
• Frame Table & Swap Table 관리

PintOS Page Fault Flow Chart

• 요약 : Page Fault 발생 -> vm_try_fault_hander -> uninit_initialize -> lazy_load_segment -> pml4_set_page

이걸 좀더 쉽게 그림으로 그려보면

원래라면 kill 하는 것을
1. 첫번째 Page Fault 가 발생
2. SPT(Supplement_page_table)을 탐색하여 메모리에 올라갈 데이터가 있는지를 탐색
3. Demand Paging

• 필요 메모리가 물리 메모리에 올라가 있다면 Page Fault
• struct page 에서 해당하는 필요 메모리 있는지를 확인 하고 주소 확인
• 있다면 Physical Frame을 탐색하여 할당
• disk에서 data를 로딩 => lazy_load_segment
• kernel Virtual Address와 물리 메모리를 1:1 매핑,
• pml4 에 추가 한다.

따라서 위 그림처럼 SPT 구현 -> Frame 관리 -> Anonymous Page & lazy loading으로 진행한다.

SPT 구현

SPT 정의

//vm.h
/* 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 spt_pages;
};

supplemental_page_table 구조체에 해시 자료구조를 사용하여 SPT를 정의한다.

Key는 VA가 될것이고, Value는 hash_elem이 될 것.
그럼 이 hash_elem은 어디다가 선언하냐면 Page 구조체에 선언한다.

// vm.h
/* The representation of "page".
 * This is kind of "parent class", which has four "child class"es, which are
 * uninit_page, file_page, anon_page, and page cache (project4).
 * DO NOT REMOVE/MODIFY PREDEFINED MEMBER OF THIS STRUCTURE. */
struct page
{
	const struct page_operations *operations;
	void *va;						 /* Address in terms of user space */
	struct frame *frame; /* Back reference for frame */

	/* Your implementation */

	/* Hash 자료구조 활용 위한 멤버변수 추가 */
	struct hash_elem hash_elem; /* Hash table element. */
	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;
#ifdef EFILESYS
		struct page_cache page_cache;
#endif
	};
};

SPT 초기화

해시 자료구조이기 때문에 GitBook의 APPENDIX의 HASH FUNCTION 부분을 참고했다.

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

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

/* Initialize new supplemental page table */
void supplemental_page_table_init(struct supplemental_page_table *spt UNUSED)
{
	// 인자로 받은 spt의 pages 해시 테이블을 초기화
	hash_init(spt, page_hash, page_less, NULL);
}

hash_init함수를 사용하기 위한 헬퍼 함수를 두개 선언해주고,
SPT의 초기화를 담당하는 supplemental_page_table_init 함수에 활용하였다.

SPT 관련 함수

• spt_find_page
  spt에서 인자로 들어오는 VA에 해당하는 페이지를 해시 자료구조인 SPT에서 찾는 함수.
  hash_find를 사용했고, 키로 활용할 임시 페이지를 선언하였다.
  이때 pg_round_down를 사용해서 정렬해서 읽어주는 것이 중요하다.

• spt_insert_page
  처음에 따로 유효성 검사가 필요한줄 알고 spt_find_page를 했는데, hash_insert에 유효성 검사 로직이 있어 그대로 가져다 썼다.

/* Find VA from spt and return page. On error, return NULL. */
/*
	주어진 spt에서 주어진 va에 해당하는 struct page 정보를 탐색
*/
struct page *
spt_find_page(struct supplemental_page_table *spt UNUSED, void *va UNUSED)
{
	// struct page *page = NULL;
	struct page p_key;
	// page = malloc(sizeof(struct page));
	struct hash_elem *e;

	// va에 해당하는 hash_elem 찾기
	p_key.va = pg_round_down(va);
	e = hash_find(&spt->spt_pages, &p_key.hash_elem);

	// 있으면 e에 해당하는 페이지 반환
	return e != NULL ? hash_entry(e, struct page, hash_elem) : NULL;
}


/* Insert PAGE into spt with validation. */
bool spt_insert_page(struct supplemental_page_table *spt UNUSED,
										 struct page *page UNUSED)
{
	/* TODO: Fill this function. */
	return hash_insert(&spt->spt_pages, &page->hash_elem) == NULL ? true : false; // 존재하지 않을 경우에만 삽입
}

Frame Management

Frame 구조체

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

현재 이 프레임에 들어가있는 page의 포인터가 있어서 서로 참조와 역참조가 가능하다.

이런 식으로 구성되어있다고 보면 된다.

Frame 관련 함수

• vm_get_frame
  새 물리 프레임의 공간을 확보하는 기능을 담당하는 함수.
  성공적으로 페이지를 받으면 구조체를 위한 메모리를 할당해준다.
  이때 calloc으로 1로 초기화하면 문제가 없지만,

만약 malloc으로 초기화했다면 쓰레기값이 들어갈 수 있다.
frame->page = NULL 을 꼭 넣어주자.

/* palloc() and get frame. If there is no available page, evict the page
 * and return it. This always return valid address. That is, if the user pool
 * memory is full, this function evicts the frame to get the available memory
 * space.*/
/* 사용자 풀에서 새로운 물리 프레임 가져오기.
 * 페이지 교체 로직 추가 전까지는 실패 시 PANIC. */
static struct frame *
vm_get_frame(void)
{
	struct frame *frame = NULL;
	/* TODO: Fill this function. */
	void *kva = palloc_get_page(PAL_USER); // user pool에서 새로운 physical page를 가져온다.

	if (kva == NULL) // page 할당 실패 -> 나중에 swap_out 처리
		PANIC("todo"); // OS를 중지시키고, 소스 파일명, 라인 번호, 함수명 등의 정보와 함께 사용자 지정 메시지를 출력

	frame = calloc(1, sizeof(struct frame));
	if (frame == NULL)
	{												 // malloc 실패 처리
		palloc_free_page(kva); // 이미 할당받은 kva는 반환
		PANIC("vm_get_frame: Malloc 할당 실패");
	}
	frame->kva = kva; // 프레임 멤버 초기화
	// frame->page = NULL; // 명시적 초기화 추가

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

• vm_do_claim_page
  주어진 page에 대해 물리 프레임을 할당(claim) 하고 이 둘을 연결하는 기능을 담당
  앞서 구현한 vm_get_frame()을 호출해서 사용가능한 프레임을 얻고,
  MMU에 이를 매핑시킨다.

즉 pml4에 가상 페이지와 물리 프레임을 매핑시키는 작업까지 진행한다.

• vm_claim_page
  SPT에서 va에 해당하는 페이지를 찾거나 없다면 생성하고
  찾거나 생성한 page를 인자로 하여 vm_do_claim_page를 호출한다.

/* Claim the page that allocate on VA. */
// va로 page를 찾아서 vm_do_claim_page를 호출하는 함수
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. */
	// 가상 주소와 물리 주소를 매핑
	struct thread *current = thread_current();
	pml4_set_page(current->pml4, page->va, frame->kva, page->writable);

	return swap_in(page, frame->kva); // uninit_initialize
}
/* Claim the PAGE and set up the mmu. */
bool vm_claim_page(void *va UNUSED)
{
	struct page *page = NULL;
	/* TODO: Fill this function */
	// spt에서 va에 해당하는 page 찾기
	page = spt_find_page(&thread_current()->spt, va);
	if (page == NULL)
		return false;
	return vm_do_claim_page(page);
}

다음엔 Anonymous Page 구현을 정리해보겠다...