[Pintos-KAIST] Project 3 : Copy On Write

👩🏻‍💻 GITHUB 레포지토리
👩🏻‍💻 GITHUB Copy On Write 이슈

과제 설명

Copy-on-write는 동일한 물리 페이지의 인스턴스를 이용하여 더 빠른 복제 작업을 가능하게 하는 리소스 관리 기술이다. 일반적으로, 어떤 리소스가 여러 프로세스에 의해 사용되는 경우, 충돌이 발생하지 않도록 각 프로세스에는 해당 리소스의 고유한 복사본이 있어야 한다. 하지만 리소스가 수정되지 않고 읽기만 하는 경우에는 물리 메모리에 해당 리소스에 대한 여러개의 복사본이 있을 필요가 없다.

그래서 fork를 할 때에는 새로운 물리 페이지를 할당하지 않고 부모와 같은 물리 페이지를 매핑만 해주었다가 추후에 write를 시도할 때에만 새로운 물리 페이지를 할당해 주면 된다.

---

구현

1. page 구조체에 accessible 추가

• include/vm/vm.h
• 부모와 같은 page에 write하려고 하는 것인지 아니면 진짜로 작성하면 안되는 페이지를 요청한 것인지 구분할 필요가 있다.
• 따라서 새로운 accessible 구조체 추가

strutc page {
...
	/** Project 3-Memory Management */
	struct hash_elem hash_elem;
	bool writable;
	/** Project 3-Copy On Write */
	bool accessible;
};

2. supplemental_page_table_copy() 수정

• vm/vm.c
• 기존에는 anonymous page를 fork할 때 새로운 페이지를 만들고 kva 또한 할당하여 물리 메모리를 그대로 복제하는 방식
• 이것을 맵핑만 해놓고 kva는 생성하지 않고 기존의 kva를 받아오는 copy_claim_page라는 함수를 새로 만들기

void
supplemental_page_table_init (struct supplemental_page_table *spt UNUSED) {
	/** Project 3-Memory Management */
	hash_init(spt, page_hash, page_less, NULL);
}

/* Copy supplemental page table from src to dst */
bool
supplemental_page_table_copy (struct supplemental_page_table *dst UNUSED,
		struct supplemental_page_table *src UNUSED) {
	
	/** Project 3-Memory Mapped Files */
 	struct hash_iterator iter;
    hash_first(&iter, &src->spt_hash);
    while (hash_next(&iter)) {
        struct page *src_page = hash_entry(hash_cur(&iter), struct page, hash_elem);
        enum vm_type type = src_page->operations->type;
        void *upage = src_page->va;
        bool writable = src_page->writable;

        if (type == VM_UNINIT) {
            void *aux = src_page->uninit.aux;
            vm_alloc_page_with_initializer(page_get_type(src_page), upage, writable, src_page->uninit.init, aux);
        }

        else if (type == VM_FILE) {
            struct vm_load_arg *aux = malloc(sizeof(struct vm_load_arg));
            aux->file = src_page->file.file;
            aux->ofs = src_page->file.offset;
            aux->read_bytes = src_page->file.page_read_bytes;

            if (!vm_alloc_page_with_initializer(type, upage, writable, NULL, aux))
                return false;

            struct page *dst_page = spt_find_page(dst, upage);
            file_backed_initializer(dst_page, type, NULL);
            dst_page->frame = src_page->frame;
            pml4_set_page(thread_current()->pml4, dst_page->va, src_page->frame->kva, src_page->writable);
        }

        else {                                          
            if (!vm_alloc_page(type, upage, writable)) 
                return false;

			/** Project 3-Copy On Write */
            // if (!vm_claim_page(upage))  
            //     return false;

            // struct page *dst_page = spt_find_page(dst, upage); 
            // memcpy(dst_page->frame->kva, src_page->frame->kva, PGSIZE);

			if (!vm_copy_claim_page(dst, upage, src_page->frame->kva, writable)) 
                return false;
        }
    }

    return true;
}

3. vm_copy_claim_page() 구현

• vm/vm.c
• 함수에서 frame을 새로 만드는 것까지는 동일하지만, 기존의 kva를 가리키게 만들고 accessible을 설정해 준 후 pml4를 writable을 false로 swap_in을 수행한다.
• 이제 fork된 페이지에 대해서 writable가 무조건 false이기 때문에 해당 페이지에 write를 시도하면 page_fault가 발생한다.

/** Project 3-Copy On Write */
static bool 
vm_copy_claim_page(struct supplemental_page_table *dst, void *va, void *kva, bool writable) {
    struct page *page = spt_find_page(dst, va);

    if (page == NULL)
        return false;

    struct frame *frame = (struct frame *)malloc(sizeof(struct frame));

    if (!frame)
        return false;

    page->accessible = writable; 
    frame->page = page;
    page->frame = frame;
    frame->kva = kva;

    if (!pml4_set_page(thread_current()->pml4, page->va, frame->kva, false)) {
        free(frame);
        return false;
    }

    list_push_back(&frame_table, &frame->frame_elem); 

    return swap_in(page, frame->kva);
}

4. vm_try_handle_fault() 수정

• vm/vm.c
• 이에 따라서 try_handle_fault 에서 이를 구분할 수 있어야 한다.
• 그 동안은 writable이 금지된 페이지에 write를 시도했을 때 무조건 false를 반환했었는데 이를 accessible을 검사하는 함수를 호출하도록 수정한다.

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-Copy On Write */
    struct page *page = spt_find_page(&thread_current()->spt, addr);

    if (addr == NULL || is_kernel_vaddr(addr))
        return false;

    if (!not_present && write)
        return vm_handle_wp(page);

    if (!page) {
        void *rsp = user ? f->rsp : thread_current()->stack_pointer;
		if (STACK_LIMIT <= rsp - 8 && rsp - 8 == addr && addr <= USER_STACK){
			vm_stack_growth(thread_current()->stack_bottom - PGSIZE);
			return true;
		}
		else if (STACK_LIMIT <= rsp && rsp <= addr && addr <= USER_STACK){
			vm_stack_growth(thread_current()->stack_bottom - PGSIZE);
			return true;
		}
        return false;
    }

    return vm_do_claim_page(page);  
}

5. vm_handle_wp() 구현

• vm/vm.c
• 먼저 페이지에 대해서 검사하는데 access가 금지되어 있다면 fork된 페이지가 아니라 실제로 접근해서는 안되는 페이지이기 때문에 바로 false를 리턴한다.
• 만약 access 가능하다면 이는 fork된 페이지기 떄문에 먼저 기존 kva을 백업해주고 kva에 user_pool에서 새로운 페이지를 할당한다.
  이 때 용량이 꽉 차서 할당할 수 없다면 evict_frame을 수행하여 만들어준다.
• 그 후 원본 kva를 현재 frame에 복원하고 pml4에 할당해준다.

static bool
vm_handle_wp (struct page *page UNUSED) {
	/** Project 3-Copy On Write */
    if (!page->accessible)
        return false;

    void *kva = page->frame->kva;

    page->frame->kva = palloc_get_page(PAL_USER | PAL_ZERO);

    if (page->frame->kva == NULL)
        page->frame = vm_evict_frame();  
		
    memcpy(page->frame->kva, kva, PGSIZE);

    if (!pml4_set_page(thread_current()->pml4, page->va, page->frame->kva, page->accessible))
        return false;

    return true;
}

6. anon_destroy() 수정

• vm/anon.c
• 자식 프로세스가 할 일 모두 끝내고 종료할 때 process_cleanup을 수행하게 되는데 이 때 spt를 지우는 것 뿐만 아니라 pml4도 같이 파괴한다.
• 우리의 프로세스가 부모의 Anonymous_Page를 가져와서 write를 시도하지 않은 페이지들은 아직 부모의 kva를 참조하고 있다면, 자식이 exit 할 때 해당 kva까지 파괴해버림 -> 그래서 추후에 부모가 접근하면 fault가 뜨는 문제가 발생. 🚨
• pml4_destroy를 막고 pml4_clear만 수행하여 kva의 연결만 끊은 상태로 만들어 재가용하게 돌려준다. 그리고 나중에 OS가 종료될 때만 kva를 destory시키도록 한다.

static void
anon_destroy (struct page *page) {
	struct anon_page *anon_page = &page->anon;
	/** Project 3-Swap In/Out */
    if (anon_page->page_no != BITMAP_ERROR)
        bitmap_reset(swap_bitmap, anon_page->page_no);

    if (page->frame) {
		lock_acquire(&swap_lock);
        list_remove(&page->frame->frame_elem);
		lock_release(&swap_lock);
        page->frame->page = NULL;
        free(page->frame);
        page->frame = NULL;
    }
	pml4_clear_page(thread_current()->pml4, page->va); /** Project 3-Copy On Write */
}

---

테스트 결과

pass tests/userprog/args-none
pass tests/userprog/args-single
pass tests/userprog/args-multiple
pass tests/userprog/args-many
pass tests/userprog/args-dbl-space
pass tests/userprog/halt
pass tests/userprog/exit
pass tests/userprog/create-normal
pass tests/userprog/create-empty
pass tests/userprog/create-null
pass tests/userprog/create-bad-ptr
pass tests/userprog/create-long
pass tests/userprog/create-exists
pass tests/userprog/create-bound
pass tests/userprog/open-normal
pass tests/userprog/open-missing
pass tests/userprog/open-boundary
pass tests/userprog/open-empty
pass tests/userprog/open-null
pass tests/userprog/open-bad-ptr
pass tests/userprog/open-twice
pass tests/userprog/close-normal
pass tests/userprog/close-twice
pass tests/userprog/close-bad-fd
pass tests/userprog/read-normal
pass tests/userprog/read-bad-ptr
pass tests/userprog/read-boundary
pass tests/userprog/read-zero
pass tests/userprog/read-stdout
pass tests/userprog/read-bad-fd
pass tests/userprog/write-normal
pass tests/userprog/write-bad-ptr
pass tests/userprog/write-boundary
pass tests/userprog/write-zero
pass tests/userprog/write-stdin
pass tests/userprog/write-bad-fd
pass tests/userprog/fork-once
pass tests/userprog/fork-multiple
pass tests/userprog/fork-recursive
pass tests/userprog/fork-read
pass tests/userprog/fork-close
pass tests/userprog/fork-boundary
pass tests/userprog/exec-once
pass tests/userprog/exec-arg
pass tests/userprog/exec-boundary
pass tests/userprog/exec-missing
pass tests/userprog/exec-bad-ptr
pass tests/userprog/exec-read
pass tests/userprog/wait-simple
pass tests/userprog/wait-twice
pass tests/userprog/wait-killed
pass tests/userprog/wait-bad-pid
pass tests/userprog/multi-recurse
pass tests/userprog/multi-child-fd
pass tests/userprog/rox-simple
pass tests/userprog/rox-child
pass tests/userprog/rox-multichild
pass tests/userprog/bad-read
pass tests/userprog/bad-write
pass tests/userprog/bad-read2
pass tests/userprog/bad-write2
pass tests/userprog/bad-jump
pass tests/userprog/bad-jump2
pass tests/vm/pt-grow-stack
pass tests/vm/pt-grow-bad
pass tests/vm/pt-big-stk-obj
pass tests/vm/pt-bad-addr
pass tests/vm/pt-bad-read
pass tests/vm/pt-write-code
pass tests/vm/pt-write-code2
pass tests/vm/pt-grow-stk-sc
pass tests/vm/page-linear
pass tests/vm/page-parallel
pass tests/vm/page-merge-seq
pass tests/vm/page-merge-par
pass tests/vm/page-merge-stk
pass tests/vm/page-merge-mm
pass tests/vm/page-shuffle
pass tests/vm/mmap-read
pass tests/vm/mmap-close
pass tests/vm/mmap-unmap
pass tests/vm/mmap-overlap
pass tests/vm/mmap-twice
pass tests/vm/mmap-write
pass tests/vm/mmap-ro
pass tests/vm/mmap-exit
pass tests/vm/mmap-shuffle
pass tests/vm/mmap-bad-fd
pass tests/vm/mmap-clean
pass tests/vm/mmap-inherit
pass tests/vm/mmap-misalign
pass tests/vm/mmap-null
pass tests/vm/mmap-over-code
pass tests/vm/mmap-over-data
pass tests/vm/mmap-over-stk
pass tests/vm/mmap-remove
pass tests/vm/mmap-zero
pass tests/vm/mmap-bad-fd2
pass tests/vm/mmap-bad-fd3
pass tests/vm/mmap-zero-len
pass tests/vm/mmap-off
pass tests/vm/mmap-bad-off
pass tests/vm/mmap-kernel
pass tests/vm/lazy-file
pass tests/vm/lazy-anon
pass tests/vm/swap-file
pass tests/vm/swap-anon
pass tests/vm/swap-iter
pass tests/vm/swap-fork
pass tests/filesys/base/lg-create
pass tests/filesys/base/lg-full
pass tests/filesys/base/lg-random
pass tests/filesys/base/lg-seq-block
pass tests/filesys/base/lg-seq-random
pass tests/filesys/base/sm-create
pass tests/filesys/base/sm-full
pass tests/filesys/base/sm-random
pass tests/filesys/base/sm-seq-block
pass tests/filesys/base/sm-seq-random
pass tests/filesys/base/syn-read
pass tests/filesys/base/syn-remove
pass tests/filesys/base/syn-write
pass tests/threads/alarm-single
pass tests/threads/alarm-multiple
pass tests/threads/alarm-simultaneous
pass tests/threads/alarm-priority
pass tests/threads/alarm-zero
pass tests/threads/alarm-negative
pass tests/threads/priority-change
pass tests/threads/priority-donate-one
pass tests/threads/priority-donate-multiple
pass tests/threads/priority-donate-multiple2
pass tests/threads/priority-donate-nest
pass tests/threads/priority-donate-sema
pass tests/threads/priority-donate-lower
pass tests/threads/priority-fifo
pass tests/threads/priority-preempt
pass tests/threads/priority-sema
pass tests/threads/priority-condvar
pass tests/threads/priority-donate-chain
pass tests/vm/cow/cow-simple
All 141 tests passed.

ec2 환경에서 swap-fork가 FAIL하였지만, WSL 환경에서 pass하는 것을 확인함.

핀토스 끝!!!!!!!! 😇