Pintos Project 3-1) VM- Lazy loading

이 글은 핀토스 가상메모리 디멘드 페이징에 관한 글입니다.

• Virtual memory란?

• Lazy loading

  • Supplemental Page Table (& vm_alloc_page)
  • Page fault handler (3 cases)
  • get physical frame
  • load file (lazily)

• aux parameter
  

---

프로젝트3 소감

가상 메모리는 OS 프로젝트의 꽃이다.
가상메모리로 구현하고자 한 abstraction의 메인 아이디어는 다음과 같다.

프로세스를 하나의 독립적인 머신처럼

'가상화'의 핵심 아이디어는- 수행 유닛, process 각각을 마치 머신처럼 작동하게 하자는 것인데
독립적 CPU/ 메모리/ 스토리지를 가진 것처럼 착각하게 하려면 '가상화'를 해야 한다.
CPU는 스케줄링을, 메모리는 가상메모리를, 스토리지는 파일을 활용한다.
OS를 디자인한다는 것은 이러한 추상화를 심리스하게 사용할 수 있도록 애플리케이션에 API를 제공하는 것과 같으며, 그것을 '시스템 콜'이라 한다.

Logical vs Physical

<가상 vs 실제> 디자인은 '한 프로세스가 다른 공간에 접근하지 못하도록 하자'는 protection 컨셉이며, 이를 virtual address로 구현한다.
각 프로세스가 하나의 머신이니까 0부터 (가상)주소를 갖도록 하는 것이다.

각 프로세스는 주소공간을 어떤 형태로 갖고 있을까?
a.out 이라는 파일을 실행하고자 메모리로 가져올 때,
a.out 내 코드섹션은 text 세그먼트로, 로컬변수는 stack, <#include><#define>과 같은 헤더는 data 세그먼트로. mmap 할당받은 메모리는 Heap으로 간다.
이처럼 운영체제가 각 세그먼트로 나눠주고, 각 타입에 맞게 메모리를 할당한다.

"Demand paging"

왜 메모리에 처음 접근할 때와 두번째 접근할 때 시간이 10배 이상 차이나는가?
프로세스가 1GB를 쓰겠다고 해서 운영체제가 그냥 주는 것이 아니다. 1GB 중 실제로 쓰려는 부분만 그 타이밍에 맞게 메모리를 할당한다.
두 번째 접근할 때는 이미 memory allocated라 바로 접근이 가능하다. map_populate로 처음부터 1GB를 전부 할당하면 첫번째 접근할 때와 두 번째 접근할 때 시간이 같다.

Data structue design

핀토스에서 가장 많이 얻어갈 수 있었던 점이라 하면,
구조체를 직접 만들고 그에 맞는 Data structure를 디자인해볼 수 있었던 경험이다.

가상메모리 핵심 기능인 Demand paging과 Swap In/Out을 구현하기 위한 구조체는 다음과 같다.

• Demand paging
  page(가상), frame(물리), 그리고 이 둘을 변환하는 page table, 나중에 lazy loading을 할 때 필요한 정보를 담고있는 Supplemental page table 등
• Swap In/Out
  교체할 프레임을 선택해 보낼 swap table 또는 file system, 그리고 프레임 자원을 관리하기 위한 LRU_list 등

이를 구현하는 데 사용한 data structure는 다음과 같다.

• Array: Page Table is an array of page table entries. 연속적인 데이터는 locality가 있어 빠름.
• Linked list: SPT 안의 buckets. 같은 인덱스에 걸려있는 여러 vm_entry(hash_elem)를 연결리스트로 관리
• Hash Table: SPT를 해시테이블로 디자인
  • 페이지 가상주소를 index로 해싱한 vm_entry들의 집합.
  • vm_entry 개수에 따라 해시테이블 크기가 결정되며
  • 해시값을 기준으로 버켓 안에서만 탐색해서 시간이 적게 걸림
• Bitmap: 스왑 테이블을 비트맵으로 디자인
  • 비트맵은 array of bits. 각 비트는 true or false를 나타내며 동일 소스내 usage(사용여부)를 트래킹
  • bit=0인 슬롯에 Swap_out 하고, 반대로 Swap_in 할 때는 bit=1에서 0으로 바꿔줌

Abstraction

mmap() 파트에선 file I/O 추상화 관점도 배울 수 있었다.
'매핑한다'는 것은 가져와서 쓴다는 것이다. read/write() 대신, 파일을 고칠 수 있는 헤더를 anonymous로 가져와서 매핑하면 파일이 '메모리'로 보인다.
이러한 mmap은 다양하게 쓰인다.
파일의 API는 두 종류가 있는데,
1. 파일을 비워놓고 복사해서 매핑하자 = 메모리 할당과 똑같음 -> 그래서 mmap을 메모리 할당용 콜로도 쓰게 되었다. (큰 chunck를 할당할 때는 malloc 대신 mmap)
2. 두 개의 프로세스가 같은 파일에 mmap을 호출하면
파일을 메모리로 보면 같은 곳을 향하고 있고(fd는 다르지만),
따라서 physical memory를 똑같이 할당하고 shared 옵션을 주면
원래 매핑하려고 쓴 mmap 시스템 콜을 Memory Share 용으로도 쓸 수 있다.

C에서 객체지향 메소드 구현

C에서도 객체지향을 구현할 수 있다.
핀토스의 경우 aux 구조체가 대표적이다.
무엇을 상속할 지 pointer만 넘기는데 그것을 void 포인터로 넘김으로써-
page 타입에 맞는 struct type으로 바꿔서 그에 맞는 함수형 포인터를 실행하도록 했다.
이런 작업들을 컴파일러로 떠넘긴 것이 Object oriented Programming의 시작이다.

 

Virtual memory

핀토스에서 구현하는 가상메모리의 근본적 목적은 '물리 메모리의 크기 한계를 극복하는 것'이다.
가상 메모리는 물리 메모리보다 큰 프로세스를 실행할 수 있다. 100MB 물리 메모리에서 200MB 크기 프로세스를 실행할 수 있다면, 그건 Lazy loading의 역할이 크다.
프로세스 이미지를 모두 메모리에 올리지 않고, 현재 실행에 필요한 부분만 메모리에 적재함으로써 가능하다.

Lazy loading

프로젝트3 부터는 기존 프로세스 실행시 물리 메모리로 바로 로드하던 방식이 아닌, 실제 메모리에 접근할 때만 로드하는 방식으로 변경된다.

이 때 핵심적인 역할을 하는 자료구조가 Supplemental Page Table(SPT)다. SPT는 프로세스가 사용하는 각 페이지에 대한 정보들을 담고 있는 테이블이다.
해시 테이블을 사용하며, index는 페이지의 가상주소의 해시값, value는 페이지 정보들을 담고 있다.

SPT에 페이지를 넣을 때 가장 먼저 하는 것이 vm_entry 초기화다. vm_alloc_page_with_initializer()는 vm_entry 페이지를 생성하고 이를 해시테이블(SPT)에 넣는 역할을 한다.

 

Lazy loading, 그리고 vm_entry의 역할

SPT의 page는 어떻게 보조 데이터들을 담고 있는가?

mmap()으로 어떤 가상주소에 파일을 매핑하는 경우를 생각해보자.
하나의 ELF 파일이라도 그 안에 세그먼트가 나뉘고,
저마다 성격에 맞는 가상주소 페이지를 할당받게 된다.
(스택과 힙은 Anonymous page, 코드 및 텍스트는 File-backed page)

mmap 시스템콜을 호출하면, do_mmap()은 해당 파일 타입과 매핑할 수조(addr), 파일명, 오프셋 등 정보를 기반으로 virtual page를 생성해 SPT에 넣는다.

do_mmap

void *
do_mmap (void *addr, size_t length, int writable,
		struct file *file, off_t offset) {
		//obtain a separate and independent reference to the file for each of its mappings.

	// 얼마나 읽을 것인가: 주어진 파일 길이와 length 비교: 읽고자 하는 length와 file 사이즈 중 작은 것
	struct file *file_ = file_reopen(file);
	size_t read_bytes = length > file_length(file) ? file_length(file) : length;
	size_t zero_bytes = PGSIZE - (read_bytes % PGSIZE);
	off_t offset_ = offset ;

	// 시작 주소 : 페이지 확장시 리턴 주소값 변경 방지
	void *start_addr = addr;
	if (file_ == NULL || read_bytes == 0) return NULL;

	/* 가상 페이지 매핑 */
	while (read_bytes > 0 || zero_bytes > 0) {	// 둘 다 0이 될 때까지 반복.
		// 파일을 페이지 단위로 잘라 load_aux에 저장 
		size_t page_read_bytes = read_bytes > PGSIZE ? PGSIZE : read_bytes;		// 마지막에만 read_bytes
		size_t page_zero_bytes = PGSIZE - page_read_bytes;		// 중간에는 0, 마지막에 padding

		struct load_aux *load_aux = (struct load_aux *)malloc(sizeof(struct load_aux));
		load_aux->file = file_;
		load_aux->offset = offset_;
		load_aux->page_read_bytes = page_read_bytes;

		// 대기중인 오브젝트 생성 - 초기화되지 않은 주어진 타입의 페이지 생성. 나중에 UNINIT을 FILE-backed로. 
		if (!vm_alloc_page_with_initializer(VM_FILE, addr, writable, lazy_load_segment, load_aux)) {
			return NULL;
		}
		// 다음 페이지로 이동
		read_bytes -= page_read_bytes;
		zero_bytes -= page_zero_bytes;	// 마지막엔 0
		addr += PGSIZE;
		offset_ += page_read_bytes;
	}
	// 매핑 시작 주소 반환
	return start_addr;
}

여기서 흥미로운 점은 vm_alloc_page가 page를 생성하는 방식인데, 파일 타입에 따라 uninit_new()에 다른 초기화 함수형 포인터(initializer)를 넣고 page를 만든다는 것이다.

보다시피 uninit_new에서 page 구조체에 필요한 정보들이 새겨진다. mmap의 경우 어떤 주소에 어떤 파일을 넣을 것인지, page fault가 발생했을 때 어떤 함수가 실행되어야 하는지(init), 스왑은 어떻게 실행될지(operations)가 전부 이 때 결정된다.

실제 파일에 접근하여 Page fault가 발생했을 때도 page에 들어있는 정보를 기반으로 lazy_load_segment()를 실행한다.

 
vm_alloc_page_with_initializer

bool
vm_alloc_page_with_initializer (enum vm_type type, void *upage, bool writable,
		vm_initializer *init, void *aux) {
	
	ASSERT (VM_TYPE(type) != VM_UNINIT)

	struct supplemental_page_table *spt = &thread_current ()->spt;

	if (spt_find_page (spt, upage) == NULL) { 
		struct page *page = (struct page *)malloc(sizeof(struct page));

		if (type == VM_ANON || type == (VM_ANON | VM_MARKER_0)){
			uninit_new (page, upage, init, type, aux, anon_initializer);
		}
		else if (type == VM_FILE){
			uninit_new (page, upage, init, type, aux, file_backed_initializer);
		}

		page->writable = writable;

		/* TODO: Insert the page into the spt. */
		return spt_insert_page(spt, page);	
	}
err:
	return false;
}

uninit_new

void
uninit_new (struct page *page, void *va, vm_initializer *init,
		enum vm_type type, void *aux,
		bool (*initializer)(struct page *, enum vm_type, void *)) {
	ASSERT (page != NULL);

	*page = (struct page) {				// dereferenced to access actual struct page
		.operations = &uninit_ops,
		.va = va,
		.frame = NULL, /* no frame for now */
		.uninit = (struct uninit_page) {
			.init = init,
			.type = type,
			.aux = aux,
			.page_initializer = initializer,
		}
	};
}

 

Page Fault

현재 물리 메모리에 매핑되지 않은 메모리 페이지에 액세스를 요청할 때.
일단 페이지를 만들어놓고, Page fault가 났을 때 DRAM에 공간 할당.

세 가지 방식

• 처음 접근/디멘드 페이징
  • 운영체제는 필요한 페이지를 디스크에서 물리메모리로 가져와야 함
• 페이지 교체
  • 물리메모리가 가득 차서 새 페이지를 가져와야 하는 경우, OS는 일부 페이지를 디스크에서 교체(evict) 하도록 선택
  • 프로그램이 evicted 페이지에 접근하려 하면 page fault 발생, OS는 다시 메모리로 가져와 다른 페이지와 교체해야 함
• Copy on Write
  • 한 프로세스가 페이지를 수정할 때까지 여러 프로세스간 페이지 공유
  • 프로세스가 공유 페이지에 쓰기를 시도하면 page fault 발생
  • OS는 변경 중인 프로세스에 private copy of page를 제공함으로써 data integrity 보장

어떤 경우든, 페이지 폴트는 프로그램 실행 중 인터럽트를 일으켜 OS가 개입.
OS는 필요한 메모리를 물리메모리에 할당하고, 그것은 FILE 또는 ANON/STACK 타입에 따라 행동이 달라짐.

 
페이지 폴트와 그에 따른 디멘드 페이징의 전체 흐름은 다음과 같다.

page fault() 작동 방식

• 페이지 폴트가 발생하면 커널은 세 가지를 판단

  1. 유효한 주소인지 (커널 영역 X)
  2. Stack growth로 해결 가능한지
  3. 첫 접근시 페이지가 없어서 발생한 폴트인지

• 3의 경우 디멘드 페이징 정책에 따라 물리 메모리 할당

• 페이지 폴트가 발생한 주소(va)를 page로 변환해 물리 프레임과 page 단위로 연결. 여기서 SPT가 중요한 역할.

  • page fault() : 페이지 폴트가 발생한 주소(f_addr)를 전달
  • vm_try_handle_fault() : f_addr -> page로 변환. spt_find_page(va)로 SPT에서 va에 해당하는 페이지를 찾아 리턴.
  • vm_do_claim_page() : 물리 프레임을 받아와 해당 page와 연결

page_fault()

static void
page_fault (struct intr_frame *f) {
	bool not_present;  /* True: not-present page, false: writing r/o page. */
	bool write;        /* True: access was write, false: access was read. */
	bool user;         /* True: access by user, false: access by kernel. */
	void *fault_addr;  /* Fault address. */

	/* Obtain faulting address, the virtual address that was accessed to cause the fault */
	fault_addr = (void *) rcr2();

	/* Turn interrupts back on (they were only off so that we could
	   be assured of reading CR2 before it changed). */
	intr_enable ();

	/* Determine cause. */
	not_present = (f->error_code & PF_P) == 0;
	write = (f->error_code & PF_W) != 0;
	user = (f->error_code & PF_U) != 0;

#ifdef VM
	if (user) {
		thread_current()->rsp_stack = f->rsp;
	}
	if (vm_try_handle_fault (f, fault_addr, user, write, not_present))
		return;
#endif
    exit(-1);
	page_fault_cnt++;
    kill (f);
}

vm_try_handle_fault()

bool
vm_try_handle_fault (struct intr_frame *f UNUSED, void *addr UNUSED,
		bool user UNUSED, bool write UNUSED, bool not_present UNUSED) {

	struct supplemental_page_table *spt UNUSED = &thread_current()->spt;
	struct page *page = NULL;

	/* Validate the fault */
	if (is_kernel_vaddr(addr) || addr == NULL)
		return false;

		// 스택 증가로 page fault 해결 가능한지 판단
		if (f->rsp - 8 <= addr && addr <= USER_STACK && USER_STACK - 0x100000 <= addr) {
			vm_stack_growth(thread_current()->stack_bottom - PGSIZE);
			return true;
	}

	if (not_present) {
		// spt에서 주소에 맞는 페이지 가져오기
		page = spt_find_page(spt, addr);
		if (page == NULL)
			return false;
		if (vm_do_claim_page(page) == false)   // spt에서 찾은 page로 물리페이지 요청
			return false; 
	}
	return true;
}

 

vm_do_claim_page()

Key Question: 가상주소는 어떻게 물리주소를 찾아갈 수 있는가?

vm_do_claim_page()는 가상 page와 물리 frame을 연결하는 함수다.
이 역시 struct page 중심으로 이뤄진다.
page와 frame은 서로를 참조할 수 있는 struct field가 있기 때문에 다음과 같이 링크 설정 가능하다.
frame->page = page;
page->frame = frame;

vm_do_claim_page()

/* Claim the PAGE and set up the mmu. */
static bool
vm_do_claim_page (struct page *page) {
	struct frame *frame = vm_get_frame ();
	struct thread *t = thread_current ();

	ASSERT(frame != NULL);

	/* 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);
	}
	else		// install failed
		return false;
}

vm_do_claim_page() 함수를 보면 pml4에서 va에 해당하는 물리주소를 찾아 커널 주소로 리턴하는 부분이 눈에 띄는데,
사실 유저 가상주소를 물리주소로 변환할 수 있다는 것 자체가 '커널 가상주소' 덕분이다.

가상메모리는 유저 영역과 커널 영역으로 나뉘며, 4KB 페이지 중 1KB가 커널 영역에 할당된다.
이는 시스템콜 등으로 인터럽트가 발생, 커널이 작업 맥락(context)를 저장해두고 나중에 복귀할 때 intr_frame의 레지스터 값을 pop하여 CPU로 가져오는 등 문맥 전환에 필요한 정보들을 저장하는 데 사용된다.

주목할 점은 이 커널 영역이 물리주소와 1:1로 대응한다는 점이다.
즉, 커널 가상주소는 '글로벌'로 쓰인다는 것인데. 어떤 유저 프로세스가 돌아가든 관계없이 항상 같은 방식으로 매핑됨을 뜻한다.
커널 가상주소는 KERN_BASE(0x8004000000)에서 시작하며, 이는 물리주소 0에 해당한다.
따라서 KERN_BASE + 0x1234 라는 가상주소는 물리주소 0x1234와 같다.

 

Page Table에 물리주소와 가상주소 매핑

물리주소와 가상주소를 매핑시키는 곳은 '페이지 테이블'이다.

• 핀토스에서 페이지 테이블이 어떻게 구성되고
• 주어진 가상 page와 frame 주소만 가지고 어떻게 이 둘을 매핑시키는지 알아보자.

페이지는 가상주소(logical) 페이지를 물리주소 프레임으로 매핑시켜주는 정보를 담고있는 테이블이다.
페이지는 4KB로 모두 같은 크기를 지니며, 물리공간(디램) 역시 페이지와 같은 사이즈로 나눠져있므로, 페이지 번호만 변환하면 동일 오프셋으로 찾아갈 수 있다.

• 핀토스 Page Table 구조
  • 페이지 테이블과 페이지 디렉토리(pagedir)를 이용해서 물리주소와 가상주소의 매핑관리
  • 페이지 테이블은 가상주소에 매핑된 물리주소를 가진 엔트리들의 집합이며,
  • 페이지 디렉토리는 페이지 테이블의 주소를 갖고 있음. (한 단계 상위 개념)
  • 가상 메모리 주소에 포함된 index로 entry 접근
  • 가상 메모리 주소의 최하위 비트 12bit가 오프셋이며, 이를 bitmasking하면 Page 단위로 접근 가능(2^12 = 4096 = 4KB)

 

install_page() : 페이지 주소 매핑

페이지 테이블에 물리주소(kpage)와 가상주소(upage)를 매핑시켜주는 함수다.
물리주소는 커널 가상주소와 1:1 대응하므로 kpage로 구한다.
필자는 아래 install_page()를 커스터마이징하여 vm_do_claim_page()의 물리 프레임 할당 후 매핑하는 부분에 넣어주었다.

install_page()

static bool install_page (void *upage, void *kpage, bool writable) {
	struct thread *t = thread_current ();
	return (pml4_get_page (t->pml4, upage) == NULL
			&& pml4_set_page (t->pml4, upage, kpage, writable));
}

실제 매핑은 pml4_set_page()에서 이뤄진다.
페이지 테이블(pml4)에서 유저 가상주소에 해당하는 물리주소를 찾아 이 둘을 페이지 테이블에 매핑한다.

pml4_set_page()

pml4_set_page (uint64_t *pml4, void *upage, void *kpage, bool rw) {
	uint64_t *pte = pml4e_walk (pml4, (uint64_t) upage, 1);
	if (pte)
		*pte = vtop (kpage) | PTE_P | (rw ? PTE_W : 0) | PTE_U;
	return pte != NULL;
}

• 우선 upage에 해당하는 page table entry(PTE) 주소를 찾는다.
• 해당 주소의 page table이 없다면 CREATE = true(1)인 경우 새로운 page table을 만든다.
• vtop (kpage)는 virtual to physical 변환으로, 커널 가상주소가 매핑된 물리주소를 반환하고
• OR 연산자를 통해 pte가 가리키는 주소에 역참조로 PTE 값을 연산해 넣는다.(각각 present bit=1, read-only, user bit=1)

 

lazy_load_segment(): 물리메모리에 파일 쓰기

Key Question:

Lazy loading이라는, 곧바로 수행되지도 않을 함수가
어떻게 올바른 파일 위치를 찾아갈 수 있는가?

• 지금까지 물리메모리를 할당했다면, 이제 실제 디스크 파일을 물리 메모리로 load할 차례
• vm_entry의 <file, offset> 정보를 바탕으로 한 페이지를 커널 가상주소(kva)로 읽어들임
• 4KB를 전부 write하지 못했다면 나머지는 0으로 채워 가상주소를 page-aligned하게 유지

lazy_load_segment()

bool lazy_load_segment (struct page *page, void *aux) {
	/* TODO: Load the segment from the file */
	/* TODO: This called when the first page fault occurs on address VA. */
	
    // aux 정보 가져오기
	struct load_aux *load_aux = (struct load_aux *)aux;
	struct file *file = load_aux->file;
	off_t offset = load_aux->offset;
	size_t page_read_bytes = load_aux->page_read_bytes;
	size_t page_zero_bytes = PGSIZE - page_read_bytes;

	file_seek(file, offset);
	if (file_read(file, page->frame->kva, page_read_bytes) != (int)page_read_bytes) {
		palloc_free_page(page->frame->kva);	
		return false;
	}
	// 남은 바이트는 0으로 세팅
	memset(page->frame->kva + page_read_bytes, 0, page_zero_bytes);
	// free(load_aux);
	return true;
}

 

'aux' parameter

여기서 또 하나 놓칠 수 없는 것이 바로 aux 파라미터다.
우리는 어떻게 lazy loading이라는, 곧바로 수행되지도 않을 함수에 인자를 전달할 수 있는가?
그 방법은 바로 함수형 포인터와 'aux'다.

load_segment() 함수를 보면, 파일을 읽어올 때 필요한 정보들을 load_aux라는 구조체에 담아 vm_alloc_page()에 전달하고 있다. 이 중 네번째 인자에 해당하는 lazy_load_segment()가 load_aux에 담긴 정보(file, file내 오프셋, 가상주소, read_bytes, writable)를 가지고 실제 파일을 메모리로 로딩하게 된다.

aux의 라이프사이클은 중요하다.
malloc으로 메모리를 할당한 aux를 언제 해제할 것인가.
이는 dynamic allocation의 딜레마와 맞닿아 있는데
가비지가 남기도 하고, 또는 미리 해제해버릴 수 있다.

만약 그 시점이 너무 이르면
mumap()에서 aux 정보를 읽지 못해 매핑을 해제하기 전 변경내역을 디스크파일에 반영할 수 없을 것이다.

가장 좋은 방법은 Deep copy로 같은 내용의, 새로운 객체를 만드는 것이다.
malloc을 활용해 주소를 그대로 복사하지 않고, 똑같은 값을 가진 다른 변수를 갖다 쓰면 free 타이밍으로 인한 문제를 피할 수 있다.
Shallow copy는 값 자체가 아닌 주소값을 복사하여 같은 메모리를 가르키는 reference 방식이므로 빠르긴 하나 비동기(Async) 작업의 경우 잘못된 값을 참조하는 문제가 생길 수 있다.