Project 3 : Anonymous Page 구현
무엇을 하는가?
anonymous page를 구현하는 것이 목표이다.
anonymous page가 무엇인가?
anonymous page는 file-backed page와 달리 contents를 가져올 file이나 device가 없는 page를 말한다. 이들은 프로세스 자체에서 런타임 때 만들어지고 사용된다. stack 과 heap 영역의 메모리들이 여기에 해당된다.
vm_alloc_page_with_initializer()를 구현해야 한다. 이 함수의 역할은 전달된 vm_type에 따라 적절한 initializer를 가져와서 uninit_new를 호출하는 역할이다.
// vm/vm.c
/* Create the pending page object with initializer. If you want to create a
* page, do not create it directly and make it through this function or
* `vm_alloc_page`. */
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;
/* Check whether 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* page = (struct page*)malloc(sizeof(struct page));
typedef bool(*initializerFunc)(struct page *, enum vm_type, void *);
initializerFunc initializer = NULL;
// vm_type에 따라 다른 initializer를 부른다.
switch(VM_TYPE(type)){
case VM_ANON:
initializer = anon_initializer;
break;
case VM_FILE:
initializer = file_backed_initializer;
break;
}
/* TODO: and then create "uninit" page struct by calling uninit_new.
* you should modify the field after calling the uninit_new.*/
uninit_new(page, upage, init, type, aux, initializer);
// writable 설정
page->writable = writable;
/* TODO: Insert the page into the spt. */
return spt_insert_page(spt,page);
}
err:
return false;
}vm_alloc_page_with_initializer는 무조건 uninit type의 page를 만든다. 그 후에 uninit_new에서 받아온 type으로 이 uninit type이 어떤 type으로 변할지와 같은 정보들을 page 구조체에 채워준다.
// vm/uninit.c
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) {
.operations = &uninit_ops,
.va = va,
.frame = NULL, /* no frame for now */
.uninit = (struct uninit_page) {
.init = init,
.type = type,
.aux = aux,
.page_initializer = initializer,
}
};
}이 함수는 언제 호출될까?
load_segment
load_segment() → vm_alloc_page_with_initializer (VM_ANON, upage, writable, lazy_load_segment, aux)
user process 실행할 때 발생하는데, 파일을 다 올리지 않고 uninit으로 만든다음 나중에 user의 행동에 따라 달라짐, 이 때 init 값으로 lazy_load_segment 가 들어간다.
setup_stack
setup_stack() → vm_alloc_page(VM_ANON | VM_MARKER_0, stack_bottom, 1)
- vm_alloc_page_with_initializer의 wrapper 함수(정의되어 있음)
#define vm_alloc_page(type, upage, writable) \
vm_alloc_page_with_initializer ((type), (upage), (writable), NULL, NULL)여기서는 init값으로 NULL을 넣는다.
lazy load
demand paging과 lazy load의 관계
computer operating system에서 demand paging은 virtual memory 관리의 한 방법이다. demand page를 사용하는 시스템에서 OS는 disk page에 액세스를 시도하고 해당 page가 memory에 아직 없는 경우에만(즉, page fault가 난 경우) disk page를 physical memory에 복사한다. 따라서 physical memory에 page가 없는 상태에서 프로세스가 실행되기 시작하며, 프로세스의 작업 페이지 집합(working set of pages)이 physical memory에 위치할 때까지 많은 page fault가 발생한다. 이것은 lazy loading technique의 일종이다. - Demand paging (wikipedia)
project2까지 PintOS 상황
실행파일이 탑재될 때 전체 프로세스 주소공간이 할당된다. 주소공간 각 페이지의 물리적 주소가 결정된다.
ELF의 이미지의 segment들을 전부 읽어 physical memory에 할당한다.
load_segment()로 Data, Code segment 읽음setup_stack()으로 stack의 physical memory 할당
Demand Paging 과정
핀토스는 프로그램의 모든 segment에 대해 physical page를 할당하고 있었다. 그래서 page fault가 발생하면 강제 종료가 되었다.
demand paging을 사용하면 요청한 page에 대해서만 physical page를 할당할 수 있다.
project 2까지 프로세스가 실행될 때 segment를 physical memory에 직접 load하는 방식을 사용했다. 그런 이유로 page fault가 발생하면 kernel이나 user program에서 나타나는 bug였는데, 이제는 그렇지 않다. 우리는 spt에 필요한 정보를 넣어서 page fault가 발생했을 때 메모리에 load하는 방식인 lazy load 방식을 구현하려고 한다.
#ifndef VM 블록 안에 있는 함수들은 project 2에서만 사용하는 함수이므로 #else 블록에서 수정해 줘야 한다.
lazy-load에 대한 page fault인 경우 kernel은 이전에 당신이 vm_alloc_page_with_initializer에서 설정한 초기 initializers중 하나를 호출하여 segment를 lazy load 하고, 이걸 위한 함수다.
// userprog/process.c
static 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. */
/* TODO: VA is available when calling this function. */
// project 3
struct file *file = ((struct container *)aux)->file;
off_t offsetof = ((struct container *)aux)->offset;
size_t page_read_bytes = ((struct container *)aux)->page_read_bytes;
size_t page_zero_bytes = PGSIZE - page_read_bytes;
file_seek(file, offsetof);
// 여기서 file을 page_read_bytes만큼 읽어옴
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);
return true;
}lazy_load_segment 는 vm_alloc_page_with_initializer의 4번째 argument로 제공된다(load_segment 안에서). 이 함수는 executable’s page의 initializer이며 page fault 발생시에 실행된다. 이 함수는 page struct와 aux를 arguments로 받는다. aux는 load_segment에서 설정하는 정보다. 당신은 이 정보를 사용하여 segment를 읽을 file을 찾아 segment를 메모리로 읽어야(read) 한다.
성공하면 true를 반환하고 메모리 할당 오류 혹은 disk 읽기 오류가 발생하면 false를 반환한다.
이 함수 안에서 처음부는 container라는 구조체를 사용하기 때문에 process.h에 구현해주자.
// project 3
struct container{
struct file *file;
off_t offset;
size_t page_read_bytes;
};우리는 현재 lazy loading 방식을 취하고 있고 이는 파일 전체를 다 읽어오지 않는다. 그때 그때 필요할 때만 읽어오는데, 그걸 위해서는 우리가 어떤 파일의 어떤 위치에서 읽어와야 할지 알아야 하고 그 정보가 container안에 들어가 있다.
// userprog/process.c
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. */
// project 3
// void *aux = NULL;
struct container *container = (struct container *)malloc(sizeof(struct container));
container->file = file;
container->page_read_bytes = page_read_bytes;
container->offset = ofs;
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;
}loop를 돌 때마다 vm_alloc_page_with_initializer를 호출하여 보류중인 페이지 개체를 생성한다. page fault가 발생하면 segment가 file에서 실제로 load된다.
stack 할당을 새로운 memory management system에 맞추려면 setup_stack( in userprog/process.c)을 조정해야 한다.
// userprog/process.c
/* Create a PAGE of stack at the USER_STACK. Return true on success. */
static bool
setup_stack (struct intr_frame *if_) {
bool success = false;
void *stack_bottom = (void *) (((uint8_t *) USER_STACK) - PGSIZE);
/* TODO: Map the stack on stack_bottom and claim the page immediately.
* TODO: If success, set the rsp accordingly.
* TODO: You should mark the page is stack. */
/* TODO: Your code goes here */
// project 3
if(vm_alloc_page(VM_ANON | VM_MARKER_0, stack_bottom, 1)){
success = vm_claim_page(stack_bottom);
if(success){
if_->rsp = USER_STACK;
thread_current()->stack_bottom = stack_bottom;
}
}
return success;
}stack은 disk에서 file을 읽어올 필요가 없으니까 lazy load 할 필요가 없다.(그래서 init에 NULL을 넣어주나 보다)
anon page로 만들 uninit page를 stack_bottom에서 위로 1page만큼 만든다. 이 때 type에 VM_MARKER_0 flag를 추가함으로써 이 page가 stack임을 표시
stack_bottom을 thread.h에 추가해준다.
// include/thread.h
#ifdef VM
/* Table for whole virtual memory owned by thread. */
struct supplemental_page_table spt;
void *stack_bottom;
#endif마지막으로 spt_find_page를 통해 supplemental page table을 참조하여 vm_try_handle_fault 함수를 수정해서 faulted address에 해당하는 page struct를 해결한다.
// vm/vm.c
/* Return true on success */
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;
/* TODO: Validate the fault */
/* TODO: Your code goes here */
// project 3
if(is_kernel_vaddr(addr)){
return false;
}
void *rsp_stack = is_kernel_vaddr(f->rsp) ? thread_current()->rsp_stack : f->rsp;
if(not_present){
if(!vm_claim_page(addr)){
if(rsp_stack - 8 <= addr && USER_STACK - 0x100000 <= addr && addr <= USER_STACK){
vm_stack_growth(thread_current()->stack_bottom - PGSIZE);
return true;
}
return false;
}
else
return true;
}
return false;
// return vm_do_claim_page (page);
}여기서 사용한 rsp_stack도 thread.h의 struct thread에 추가해준다.
#ifdef VM
/* Table for whole virtual memory owned by thread. */
struct supplemental_page_table spt;
void *stack_bottom;
void *rsp_stack;
#endifcheck_address도 수정해줘야 한다. 기존에는 rsp값으로 check_address를 진행했는데 방식이 바뀌었기 때문.
struct page * check_address(void *addr){
if(is_kernel_vaddr(addr)){
exit(-1);
}
return spt_find_page(&thread_current()->spt,addr);
}read write에서 buffer를 위해 함수를 새로 만들어줘야 한다.
void check_valid_buffer(void* buffer, unsigned size, void* rsp, bool to_write){
for(int i=0; i<size; i++){
struct page* page = check_address(buffer + i);
if(page == NULL)
exit(-1);
if(to_write == true && page->writable == false)
exit(-1);
}
}이 때, syscall.c에서의 syscall_handler도 수정해주자.
case SYS_READ:
{
check_valid_buffer(f->R.rsi, f->R.rdx, f->rsp, 1);
f->R.rax = read(f->R.rdi, f->R.rsi, f->R.rdx);
break;
}
case SYS_WRITE:
{
check_valid_buffer(f->R.rsi, f->R.rdx, f->rsp, 0);
f->R.rax = write(f->R.rdi, f->R.rsi, f->R.rdx);
break;
}anon type과 관련한 함수들을 수정해주자.
일단 anon_page에 swap_idx라는 멤버 설정해준다.
struct anon_page {
int swap_index; // project 3
};anon_initializer는 프로세스가 uninit page에 접근해서 page fault가 일어나면, page fault handler에 의해 호출되는 함수다.
/* Initialize the file mapping */
bool
anon_initializer (struct page *page, enum vm_type type, void *kva) {
/* Set up the handler */
struct uninit_page *uninit = &page->uninit;
memset(uninit, 0, sizeof(struct uninit_page));
// operation을 anon_ops으로 지정
page->operations = &anon_ops;
struct anon_page *anon_page = &page->anon;
anon_page->swap_index = -1;
return true;
}이 함수는 어떻게 불러와질까?
page_fault 안에 vm_try_handle_fault가 있고,
static void
page_fault (struct intr_frame *f) {
...
#ifdef VM
/* For project 3 and later. */
if (vm_try_handle_fault (f, fault_addr, user, write, not_present))
return;
...
}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) {
...
if(not_present){
if(!vm_claim_page(addr)){
if(rsp_stack - 8 <= addr && USER_STACK - 0x100000 <= addr && addr <= USER_STACK){
vm_stack_growth(thread_current()->stack_bottom - PGSIZE);
return true;
}
return false;
}
else
return true;
}
...
}vm_claim_page가 있고
vm_claim_page 안에
bool
vm_claim_page (void *va UNUSED) {
...
return vm_do_claim_page (page);
}vm_do_claim_page가 있고
vm_do_claim_page 안에
static bool
vm_do_claim_page (struct page *page) {
if(install_page(page->va, frame->kva, page->writable)){
return swap_in(page, frame->kva);
}
}swap_in이 있고
swap_in은
#define swap_in(page, v) (page)->operations->swap_in ((page), v)page -> operations -> swap_in을 실행시키고 처음 할당받아온 모든 page는 uninit page이기 때문에
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) {
.operations = &uninit_ops,
.va = va,
.frame = NULL, /* no frame for now */
.uninit = (struct uninit_page) {
.init = init,
.type = type,
.aux = aux,
.page_initializer = initializer,
}
};
}uninit_new에서 고쳐줬던 operation에 uninit_ops가 들어가 있으므로 uninit_ops가 실행된다.
static const struct page_operations uninit_ops = {
.swap_in = uninit_initialize,
.swap_out = NULL,
.destroy = uninit_destroy,
.type = VM_UNINIT,
};위 함수에 따라서 uninit_initialize를 부르고
static bool
uninit_initialize (struct page *page, void *kva) {
struct uninit_page *uninit = &page->uninit;
/* Fetch first, page_initialize may overwrite the values */
vm_initializer *init = uninit->init;
void *aux = uninit->aux;
/* TODO: You may need to fix this function. */
return uninit->page_initializer (page, uninit->type, kva) &&
(init ? init (page, aux) : true);
}여기서 page의 type에 따라 initializer()와 vm_init()을 부른다.
현재 anon type이므로 anon_initializer()가 드디어 불러지게 된다.
- 페이지에 프로그램이 접근했는데 만약 uninit page라면 page fault handler가 호출된다.
vm_do_claim_page()에서 해당 page와 physical frame을 연결시켜주고uninit_initialize()에서 type에 맞게 page를 초기화해주는 것이다.
Supplemental page table - revisit
copy 및 clean up을 지원하기 위해 supplemental page table 인터페이스를 다시 방문한다. 이 작업은 creating이나 destroying할 때 필요하다.
supplemental_page_table_copy를 구현해보자.
bool
supplemental_page_table_copy (struct supplemental_page_table *dst UNUSED,
struct supplemental_page_table *src UNUSED) {
// project 3
struct hash_iterator i;
hash_first(&i, &src->pages);
while(hash_next(&i)){
struct page *parent_page = hash_entry(hash_cur(&i),struct page, hash_elem);
enum vm_type type = page_get_type(parent_page);
void *upage = parent_page->va;
bool writable = parent_page->writable;
vm_initializer *init = parent_page->uninit.init;
void* aux = parent_page->uninit.aux;
if(parent_page->uninit.type & VM_MARKER_0){
setup_stack(&thread_current()->tf);
}
else if(parent_page->operations->type == VM_UNINIT){
if(!vm_alloc_page_with_initializer(type, upage, writable, init, aux))
return false;
}
else{
if(!vm_alloc_page(type, upage, writable))
return false;
if(!vm_claim_page(upage))
return false;
}
if(parent_page->operations->type != VM_UNINIT){
struct page* child_page = spt_find_page(dst,upage);
memcpy(child_page->frame->kva, parent_page->frame->kva, PGSIZE);
}
}
return true;
}src에서 dst로 spt를 복사한다. 이는 child가 parent의 실행 context를 상속해야 할 때 사용된다(즉, fork()할 때).
supplemental_page_table_kill 함수를 구현해보자.
void
supplemental_page_table_kill (struct supplemental_page_table *spt UNUSED) {
/* TODO: Destroy all the supplemental_page_table hold by thread and
* TODO: writeback all the modified contents to the storage. */
// project 3
struct hash_iterator i;
hash_first(&i, &spt->pages);
while(hash_next(&i)){
struct page *page = hash_entry(hash_cur(&i), struct page, hash_elem);
if(page->operations->type == VM_FILE){
do_munmap(page->va);
}
}
hash_destroy(&spt->pages, spt_destructor);
}make check가 안되면 supplement_page_table_kill의 내용을 주석처리하고 넘어가도록 하자.
spt_destructor 함수는 아래에 정의해준다.
// project 3
void spt_destructor(struct hash_elem *e, void* aux){
const struct page *p = hash_entry(e, struct page, hash_elem);
free(p);
}