Memory Management

Implement Supplemental Page Table

@gitbook👇

Although more complex data structures may yield better performance or other benefits, they may also needlessly complicate your implementation. Thus, we do not recommend implementing any advanced data structure (e.g. a balanced binary tree) as part of your design.

보조 테이블(spt, Supplementary Page Table)의 자료구조로 lib/kernel/hash.h에 정의되어있는 해시테이블을 사용하기로했다. 리스트는 직관적이고 중간 삽입/삭제가 용이하지만 매번 페이지를 조회할 때 마다 여기저기 흩어져있는 주소들을 선형 탐색해야 해 보조테이블의 자료구조로 적합하지 않다고 생각했다.
해시테이블은 충돌을 처리하기 위해 버킷과 부가적인 연결 리스트를 할당해야 해서 공간 오버헤드가 생길 수 있지만, 주어진 주소를 기반으로 특정 페이지를 검색할 때 작은 시간 복잡도 O(1) 로 보조 테이블의 자료구조로 쓰이기에 적합하다.

---

Supplemental Page Table 관련 함수들

lib/kernel/hash.h 를 참조해 함수들을 활용해 어렵지 않게 구현할 수 있었다.

/* Initialize new supplemental page table */
void
supplemental_page_table_init (struct supplemental_page_table *spt UNUSED)
{
	hash_init(&spt->spt_hash_table, hash_func, hash_less, NULL);
}

보조 테이블 초기화, process.c 의 initd() 함수로 새로운 프로세스가 시작하거나 process.c의 __do_fork()로 자식 프로세스가 생성될 때 호출된다.

---

인자로 넘겨진 spt 에서 가상주소va 와 대응되는 페이지 구조체를 찾아서 반환한다. 실패했을경우 NULL 반환.

/* Find VA from spt and return page. On error, return NULL. */
struct page *
spt_find_page (struct supplemental_page_table *spt UNUSED, void *va UNUSED)
{
	struct page page;
	page.va = pg_round_down(va);
	struct hash_elem *e = hash_find (&spt->spt_hash_table, &(page.hash_elem));
	return e ? 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. */
	int success = false;
	if(hash_insert(&(spt->spt_hash_table), &(page->hash_elem)) == NULL) {
		success = true;
	}
	return success;
}

인자로 주어진 spt에 페이지 구조체 삽입. 테이블에 가상 주소가 존재하는지 확인해야한다. hash_insert() 함수는 새로 넣으려는 값이 이미 해시테이블에 존재한다면 0이 아닌 값, 없다면 0이 아닌 값이 리턴 돼 삽입이 됐는지 안됐는지 확인 할 수 있다.

/* Inserts NEW into hash table H and returns a null pointer, if
no equal element is already in the table.
If an equal element is already in the table, returns it
without inserting NEW. */
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;
}

---

frame은 쉽게 말해 'page가 삽입될 수 있는 물리 주소의 슬롯' 이라고 할 수 있을 것 같다. 커널 가상주소와 페이지를 가지고 있는 구조체로 선언 되어있다.include/vm/vm.h

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

---

Anonymous Page

Page Initialization & Lazy Loading

지연 로딩(Lazy Loading)은 페이지를 할당 하고 보조테이블에 삽입만 해 놓고 컨텐츠 로딩은 pagefault() 가 일어났을 때 행해진다. 다시 말해 대응되는 페이지 구조체는 있지만 연결된 물리 메모리 프레임은 아직 없고 페이지에 대한 실제 컨텐츠들이 아직 로드되지 않았다는 것이다. 여태 Project 2 까지는 가상 주소 공간 할당 시점에 디스크로부터 물리 메모리로 ELF이미지를 바로 읽어왔지만 Lazy Loading을 적용함으로써 오버헤드를 줄일 수 있다.

@gitbook👇

In lazy loading, when a process starts it execution, only the memory parts that are immediately needed are loaded onto the main memory. This can reduce the overhead compared to eager loading, which loads all binary image into the memory at once.

---

Lazy Loading for Exe

process_exec()에 의해 load가 호출되고 바로 컨텐츠가 로드되던 지금까지의 load_segment() 와 달리 Project3-VM 의 load_segment()는 Lazy loading을 위해 파일의 정보를 받아와 auxiliary data(aux) 를 설정 해 주고 lazy_load_segment() 와 다른 정보들을 vm_alloc_page_with_initializer()에 넘겨준다.

static bool
load_segment(struct file *file, off_t ofs, uint8_t *upage, uint32_t read_bytes, uint32_t zero_bytes, bool writable)
{
	ASSERT((read_bytes + zero_bytes) % PGSIZE == 0);
	ASSERT(pg_ofs(upage) == 0);
	ASSERT(ofs % PGSIZE == 0);
	while (read_bytes > 0 || zero_bytes > 0) {
		/* Do calculate how to fill this page.
		* We will read PAGE_READ_BYTES bytes from FILE
		* and zero the final PAGE_ZERO_BYTES bytes. */
		size_t page_read_bytes = read_bytes < PGSIZE ? read_bytes : PGSIZE;
		size_t page_zero_bytes = PGSIZE - page_read_bytes;
		/* TODO: Set up aux to pass information to the lazy_load_segment. */
		struct aux_struct *tmp_aux = (struct aux_struct *)malloc(sizeof(struct aux_struct));
		tmp_aux->vmfile = file;
		tmp_aux->ofs = ofs;
		tmp_aux->read_bytes = page_read_bytes;
		tmp_aux->zero_bytes = page_zero_bytes;
		tmp_aux->writable = writable;
		tmp_aux->upage = upage;
		void *aux = tmp_aux;
		if(!vm_alloc_page_with_initializer(VM_ANON, upage, writable, lazy_load_segment, aux))
			return false;
		/* Advance. */
		read_bytes -= page_read_bytes;
		zero_bytes -= page_zero_bytes;
		upage += PGSIZE;
		ofs += page_read_bytes;
	}
	return true;
}

그러면 vm_alloc_page_with_initializer()는 VM_TYPE 매크로를 통해 vm_type 를 가져와 알맞는 initializer 와 함께 uninit_new() 함수에 넘겨 uninit_page를 만들고 spt에 삽입 해 준다.

static bool
lazy_load_segment(struct page *page, struct aux_struct *aux)
{
	/* TODO: This called when the first page fault occurs on address VA. */
	/* TODO: VA is available when calling this function. */
	/* ---- Project 3 ---- */
    /* TODO: Load the segment from the file */
	if(file_read_at(aux->vmfile, page->frame->kva, aux->read_bytes, aux->ofs)
			!= (int)aux->read_bytes) {
			
			palloc_free_page(page->frame->kva);
			free(aux);
			return false;
	}
	memset(page->frame->kva + aux->read_bytes, 0, aux->zero_bytes);
	free(aux);
	
	return true;
}

*file_read_at() 함수는 파일 내에서 지정된 오프셋 file_ofs에서 시작해 지정된 크기size만큼의 데이터를 읽어서 버퍼 buffer에 저장해 준다.

*Anonymous Page(익명 페이지) & *File-backed Page(파일 기반 페이지) :
파일 기반 페이지는 파일로 부터 매핑된 페이지, 익명 페이지는 파일로부터 매핑되지 않은 페이지로서 커널로부터 할당된 페이지다. 디스크에 있던 프로그램이 실행될 때 코드 섹션과 데이터 섹션은 메모리에 파일 기반 페이지로 load 되지만 스택과 힙 섹션은 익명 페이지로 메모리에 할당되게 된다.

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)
	bool success = false;
	struct supplemental_page_table *spt = &thread_current()->spt;
	/* Check wheter the upage is already occupied or not. */
	if (spt_find_page (spt, upage) == NULL) {
	/* TODO: Create the page, fetch the initialier according to the VM type*/
    struct page *uninit = (struct page *)malloc(sizeof(struct page));
	/* TODO: and then create "uninit" page struct by calling uninit_new. You
	* TODO: should modify the field after calling the uninit_new. */
		switch(VM_TYPE(type)) {
			case VM_ANON:
				uninit_new(uninit, pg_round_down(upage), init, type, aux, anon_initializer);
				break;
			case VM_FILE:
				uninit_new(uninit, pg_round_down(upage), init, type, aux, file_backed_initializer);
				break;
	}
	uninit->writable = writable;
	/* TODO: Insert the page into the spt. */
	success = spt_insert_page(spt, uninit);
	return success;
}
err:
	return success;
}

uninit 페이지는 말 그대로 bogus-page fault가 일어나기전에 initialize 되지 않고 대기(?) 하고있는 페이지로 이해했다. uninit_new()로 인해 uninit 페이지의 "swap in 핸들러"(page 구조체의 operations)는 자동적으로 페이지 타입에 맞게 페이지 초기화되고 주어진 aux를 인자로 삼는 init 함수를 호출하게된다.

---

page_fault가 발생하면 vm_try_handle()는 fault가 발생한 원인에 따라 처리한다.

@gitbook👇

Your page fault handler needs to do roughly the following:

1. Locate the page that faulted in the supplemental page table. If the memory reference is valid, use the supplemental page table entry to locate the data that goes in the page, which might be in the file system, or in a swap slot, or it might simply be an all-zero page. If you implement sharing (i.e., Copy-on-Write), the page's data might even already be in a page frame, but not in the page table. If the supplemental page table indicates that the user process should not expect any data at the address it was trying to access, or if the page lies within kernel virtual memory, or if the access is an attempt to write to a read-only page, then the access is invalid. Any invalid access terminates the process and thereby frees all of its resources.
2. Obtain a frame to store the page. If you implement sharing, the data you need may already be in a frame, in which case you must be able to locate that frame.
3. Fetch the data into the frame, by reading it from the file system or swap, zeroing it, etc. If you implement sharing, the page you need may already be in a frame, in which case no action is necessary in this step.
4. Point the page table entry for the faulting virtual address to the physical page. You can use the functions in threads/mmu.c.

There are three cases of bogus page fault: lazy-loaded, swapped-out page, and write-protected page. For now, just consider the first case, lazy-loaded page. If it is a page fault for lazy loading, the kernel calls one of the initializers you previously set in vm_alloc_page_with_initializer to lazy load the segment. You will have to implement lazy_load_segment in userprog/process.c.

"bogus" 페이지 폴트가 일어나는 3가지 케이스는 Lazy loading, Swapped-out page, Write-protected page가 있다. 만약 지연 로딩으로 인한 page fault였다면, vm_do_claim_page() 로 프레임과 페이지를 링크해주고, pml4 를 통해 물리 메모리에 페이지를 적재 해준다.

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;
	/* -- Project 3 -- */
	struct page *page = spt_find_page(spt, addr);
	/* TODO: Validate the fault */
	/* TODO: Your code goes here */
	if(is_kernel_vaddr(addr))
		return false;
	
	uint16_t STACK_LIMIT = USER_STACK - (1<<20);
	uint64_t limit = f->rsp - 8;

	if(page == NULL && limit == addr) {
		if(f->rsp > STACK_LIMIT && USER_STACK > f->rsp) {
			while(limit <= thread_current()->stack_bottom) {
				vm_stack_growth(thread_current()->stack_bottom - 8);
				thread_current()->stack_bottom -= PGSIZE;
			}
			return true;
		}
		return false;
	}
	if(page && not_present)
		return vm_do_claim_page(page);
	
	return false;
}

/* Claim the PAGE and set up the mmu. */
static bool
vm_do_claim_page (struct page *page)
{
	struct frame *frame = vm_get_frame ();
	/* Set links */
	if(frame == NULL) {
		frame = vm_evict_frame();
	}
	/* 링크 */
	frame->page = page;
	page->frame = frame;
	/* TODO: Insert page table entry to map page's VA to frame's PA. */
	pml4_set_page(thread_current()->pml4, page->va, frame->kva, page->writable);
	
	return swap_in (page, frame->kva);
}

---

FAQ

Q : anonymous page 및 lazy loading 관련 함수를 구현하던 중 의문이 생겨 질문드리게 되었습니다. vm_alloc_page_with_initializer() 함수를 부르는 곳을 확인해보니 load_segment() 함수에서 항상 vm_alloc_page_with_initializer(VM_ANON, upage, writable, lazy_load_segment, aux) 와 같이 VM_ANON 타입으로 페이지를 할당받는 것으로 확인하였습니다. load_segment()를 호출하는 load()는 executable file 등 file을 읽어오는 것에 사용하는 함수인데 왜 file-backed가 아닌 anonymous로 페이지를 할당받게 되는지 질문드립니다!

더불어, segment 종류에 따라 bss는 anonymous 페이지로, code/text 같은 경우에는 file-backed 페이지로 로딩되는 것이 일반적일 것이라 생각되는데, 현재 load() 함수에서는 segment 종류에 따라서 로딩 방식이 달라지지 않는 것 같아 그 이유가 궁금합니다.

A : load_segment() 에서는 ELF format으로 저장된 응용 프로그램을 로드하는데, 현재 로드하고 있는 섹션이 .text인지, .bss인지, .data인지 알기 위해서는 추가적인 작업이 필요합니다. 응용 프로그램을 로딩하는 운영체제의 입장에서 섹션을 정확하게 구분하여 로드 방식을 구분하는 데는 큰 메리트가 없습니다. 이미 .bss와 같이 파일로부터 읽을 데이터가 없는 경우는 anonymous page처럼, .text처럼 파일로부터 읽어와야 하는 데이터가 잔뜩 있는 경우에는 lazy loading을 구현한 경우 file-backed와 비슷한 메커니즘을 사용하게 될 테니까요. 오히려 말씀하신 방식대로 segment 종류에 따라 로딩 방식을 달리한다면 모든 종류의 segment에 따라 처리를 달리해 줘야 하는데, 거기로부터 오는 성능 손실과 구현의 복잡도가 오른다는 디메리트가 있을 것 같습니다.

file-backed를 쓰지 않는 이유는 용도가 맞지 않아서입니다. file-backed memory의 경우, 이 영역에 데이터를 쓰게 되면 이게 파일에 자동으로 반영이 되도록 디자인 된 페이지 타입인데, 응용프로그램 파일로부터 .bss나 .data와 같은 영역을 불러와서 실행 중에 이 영역에 저장된 값이 바뀐다 하더라도 실제 파일을 바꾸진 않을 것이니까 file-backed를 쓰지 않습니다. 그리고 page out된 후 page in되었을 때 실행 중 변경된 값을 그대로 복원하기 위해 swap disk를 이용하는 anonymous page를 이용합니다.

---

Q : vm.h 파일을 보면 enum vm_type 에 VM_MARKER_0 라는 값이 있습니다.구글링을 해보니 VM_MARKER_0를 사용하면 stack 영역인지 확인하는 용도로 사용한다고 하는데 정확히 이해가 가지않습니다.

A :enum vm_type은 일종의 비트 필드입니다. 하위 2비트는 이 page가 어떤 종류인지 (uninit, anon, …) 나타내고, 그 위의 비트들은 자유롭게 마커를 추가해서 사용할 수 있습니다.
따라서 vm_alloc_page() 등을 이용해 page를 만들 때 vm_type에 VM_ANON | VM_MARKER_0 처럼 전달해주면, 나중에 그 페이지에 마커가 있는지 확인해 볼 수 있습니다.