[Pintos-KAIST] Project 3 : Anonymous Page

👩🏻‍💻 GITHUB 레포지토리
👩🏻‍💻 GITHUB Anonymous Page 이슈

과제 설명

💡 Anonymous page라고 불리는 non-disk based image를 구현한다.

Anonymous Page란?

파일을 기반으로 하는 file-backed page와 달리, 이름이 지정된 파일 소스가 없기 때문에 anonymous라고 불리며, 스택과 힙 영역에서 사용된다.

• anon-page는 include/vm/anon.h에 선언되어있다.
• 현재는 구조체가 비어있다.

Page Initialization with Lazy Loading

• Demanding Paging 이라고도 한다.

• 지연 로딩(lazy loading)은 필요시점까지 메모리의 로딩을 지연시킨다. -> 실제 내용이 로드되는 시점은 page fault가 발생할때!

• 페이지가 할당되었다는 것은 대응되는 페이지 구조체는 있지만 연결된 물리 메모리 프레임은 아직 없고, 페이지의 실제 콘텐츠는 아직 로드되지 않음을 의미한다.

• 페이지 폴트로 인해 실제로 콘텐츠가 필요할 때 로드된다. (페이지 폴트로 시그널을 받음)

• 세 가지 페이지 타입(VM_UNINIT, VM_ANON, VM_FILE)을 가지는데 각 페이지별로 초기화 루틴이 다르다.

• 페이지 폴트 처리 절차 중에 uninit_initialize 을 호출하고 이전에 설정한 초기화 함수를 호출한다.

  • 익명 페이지를 위한 초기화 함수 : 'anon_initializer'
  • 파일기반 페이지를 위한 함수 : 'file_backed_initializer'

• 페이지는 초기화→(페이지 폴트 → 지연 로딩 → 스왑 인 → 스왑 아웃 → …) → 삭제 라는 cycle을 가진다.

• 페이지 타입(혹은 VM_TYPE)별 초기화 방법이 다른 것처럼, cycle의 전환마다 페이지 타입별로 다른 프로시저가 요구됨

  💡 각 페이지 타입에 따른 전환(transition processes) 과정을 구현해야한다.

---

구현

1. vm_alloc_page_with_initializer() 구현

• vm/vm.c
• upage가 이미 사용 중인지 확인한다.
• 페이지를 생성한다.
• type에 따라 초기화 함수를 가져온다.
• "uninit" 타입의 페이지로 초기화한다.
• 필드 수정은 uninit_new를 호출한 이후에 해야 한다.
• 생성한 페이지를 SPT에 추가한다.

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 wheter the upage is already occupied or not. */
	if (spt_find_page (spt, upage) == NULL) {

		/** #project3-Anonymous Page */
		struct page *page = malloc(sizeof(struct page));

		if (!page)
			goto err;

		typedef bool (*initializer_by_type)(struct page *, enum vm_type, void *);
		initializer_by_type initializer = NULL;

		switch (VM_TYPE(type))
		{
		case VM_ANON:
			initializer = anon_initializer;
			break;
		case VM_FILE:
			initializer = file_backed_initializer;
			break;
		}

		uninit_new(page, upage, init, type, aux, initializer);
		page->writable = writable;
		
		return spt_insert_page(spt, page);
	}
err:
	return false;
}

2. vm_load_arg 자료구조 추가

• include/vm/vm.h

/** Project 3-Memory Mapped Files */
struct vm_load_arg
{
	struct file *file;
	off_t ofs;
	uint32_t read_bytes;
	uint32_t zero_bytes;
};

3. load_segment(), lazy_load_segment() 수정

3-1. load_segment(),

• userprog/process.c
• 파일의 내용을 upage에 로드하는 함수이다.

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);

	file_seek (file, ofs);
	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;

		/* Get a page of memory. */
		uint8_t *kpage = palloc_get_page (PAL_USER);
		if (kpage == NULL)
			return false;

		/* Load this page. */
		if (file_read (file, kpage, page_read_bytes) != (int) page_read_bytes) {
			palloc_free_page (kpage);
			return false;
		}
		memset (kpage + page_read_bytes, 0, page_zero_bytes);

		/* Add the page to the process's address space. */
		if (!install_page (upage, kpage, writable)) {
			printf("fail\n");
			palloc_free_page (kpage);
			return false;
		}

		/* Advance. */
		read_bytes -= page_read_bytes;
		zero_bytes -= page_zero_bytes;
		upage += PGSIZE;
	}
	return true;
}

3-2. lazy_load_segment()

• userprog/process.c
• 이 함수는 실행 파일의 내용을 페이지로 로딩하는 함수이며 첫번째 page fault가 발생할 때 호출된다.

static bool
lazy_load_segment (struct page *page, void *aux) {
	/** Project 3-Anonymous Page */
    struct vm_load_arg *aux_p = aux;
    struct file *file = aux_p->file;
    off_t offset = aux_p->ofs;
    size_t page_read_bytes = aux_p->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) != (off_t)page_read_bytes) {  
        palloc_free_page(page->frame->kva);                                            
        return false;
    }

    memset(page->frame->kva + page_read_bytes, 0, page_zero_bytes);  

    return true;
}

4. setup_stack() 수정 및 stack용 포인터 생성

4-1. stack용 포인터 생성

• include/threads/thread.h
• 스택의 맨 아래 위치를 가리키는 포인터
• 메모리를 상향으로 증가하기 때문에 페이지크기 만큼 빼준 뒤 공간을 할당해주는 것이다!

#ifdef VM
	/* Table for whole virtual memory owned by thread. */
	struct supplemental_page_table spt;

	/** Project 3-Anonymous Page - stack용 포인터 생성*/
    void *stack_bottom;
    void *stack_pointer;
#endif

4-2. setup_stack()

• userprog/process.c
• 프로세스가 실행될 때 load 함수 안에서 호출되며, STACK의 페이지를 생성하는 함수이다.
• 첫 번째 스택 페이지는 Lazy Loading을 할 필요가 없다. 프로세스가 실행될 때 이 함수가 불리고 나서 command line arguments를 스택에 추가하기 위해 이 주소에 바로 접근하기 때문이다.
• 따라서, 이 주소에서 fault가 발생할 때까지 기다릴 필요없이 바로 물리 프레임을 할당받아 놓는다.
• 페이지를 할당받을 때 이 페이지가 스택의 페이지임을 표시하기 위해서 보조 마커를 사용한다.(VM_MARKER_0를 사용)

static bool
setup_stack (struct intr_frame *if_) {
	bool success = false;
	void *stack_bottom = (void *) (((uint8_t *) USER_STACK) - PGSIZE);

	/** Project 3-Anonymous Page */
    if (vm_alloc_page(VM_ANON | VM_MARKER_0, stack_bottom, 1)) {  // MARKER_0로 STACK에 있는 것을 표시
        success = vm_claim_page(stack_bottom);

        if (success) {
            if_->rsp = USER_STACK;
            thread_current()->stack_bottom = stack_bottom;
        }
    }
	return success;
}

5. vm_try_handle_fault() 구현

• vm/vm.c
• VM 구현 이후부터 페이지 폴트는 vm_try_handle_fault가 처리한다.
• page_fault 핸들러는 페이지 폴트에 대한 제어권을 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;

	/** Project 3-Anonymous Page */
	struct page *page = spt_find_page(&thread_current()->spt, addr);
   
    if (addr == NULL || is_kernel_vaddr(addr))
        return false;

    if (not_present)
    {
        page = spt_find_page(spt, addr);
        if (page == NULL)
            return false;
        if (write == 1 && page->writable == 0)
            return false;
        return vm_do_claim_page(page);
    }
    return false;
}

6. supplemental_page_table_copy() 구현

• vm/vm.c
• 프로세스 생성 시, spt 복사를 수행한다. (자식 프로세스 생성)
• 부모 프로세스의 SPT에 있는 모든 페이지를 각 타입에 맞게 할당을 받는다.
• uninit 상태가 아니라면, 즉 내용이 로딩된 상태라면 바로 매핑을 진행해서 내용까지 그대로 복사한다.
• file-backed page인 경우에는 다른 처리가 필요하지만 anonymous page 파트에서는 필요하지 않다. file-backed page를 할 때 추가한다.

bool
supplemental_page_table_copy (struct supplemental_page_table *dst UNUSED,
		struct supplemental_page_table *src UNUSED) {
	
	/** Project 3-Anonymous Page */
	struct hash_iterator i;
	hash_first(&i, &src->spt_hash);
	while (hash_next(&i))
	{
		struct page *src_page = hash_entry(hash_cur(&i), struct page, hash_elem);
		enum vm_type src_type = src_page->operations->type;

		if (src_type == VM_UNINIT)
		{
			vm_alloc_page_with_initializer(
				src_page->uninit.type,
				src_page->va,
				src_page->writable,
				src_page->uninit.init,
				src_page->uninit.aux);
		}
		else
		{
			if (vm_alloc_page(src_type, src_page->va, src_page->writable) && vm_claim_page(src_page->va))
			{
				struct page *dst_page = spt_find_page(dst, src_page->va);
				memcpy(dst_page->frame->kva, src_page->frame->kva, PGSIZE);
			}
		}
	}
	return true;
}

7. supplemental_page_table_kill() 및 hash_page_destroy() 구현

• 페이지 항목들을 순회하며 테이블 내의 페이지들의 타입에 맞는 destroy 함수를 호출한다.
• destroy 매크로를 사용하면 페이지 타입에 따라서 uninit_destroy 혹은 anon_destroy 함수가 호출된다.
• hash table은 두고 안의 요소들만 지워줘야 한다.
• hash_destroy 함수를 사용하면 hash가 사용하던 메모리(hash->bucket) 자체도 반환하므로, hash_destroy가 아닌 hash_clear를 사용해야 한다.

7-1. hash_page_destroy() 선언

• include/vm/vm.h

/** Project 3-Anonymous Page */
uint64_t page_hash(const struct hash_elem *e, void *aux);
bool page_less(const struct hash_elem *a, const struct hash_elem *b, void *aux);
void hash_page_destroy(struct hash_elem *e, void *aux);
#endif  /* VM_VM_H */

7-2. hash_page_destroy() 구현

• vm/vm.c

/** Project 3-Anonymous Page */
void 
hash_page_destroy(struct hash_elem *e, void *aux)
{
    struct page *page = hash_entry(e, struct page, hash_elem);
    destroy(page);
    free(page);
}

7-3. supplemental_page_table_kill() 구현

• vm/vm.c

void
supplemental_page_table_kill (struct supplemental_page_table *spt UNUSED) {
	/** Project 3-Anonymous Page */
	hash_clear(&spt->spt_hash, hash_page_destroy);
}

8. System Calls 수정

• userprog/syscall.c

#ifndef VM
/** project2-System Call */
void check_address(void *addr) {
    thread_t *curr = thread_current();

    if (is_kernel_vaddr(addr) || addr == NULL || pml4_get_page(curr->pml4, addr) == NULL)
        exit(-1);
}
#else
/** Project 3-Anonymous Page */
struct page *check_address(void *addr) {
    struct thread *curr = thread_current();

    if (is_kernel_vaddr(addr) || addr == NULL || !spt_find_page(&curr->spt, addr))
        exit(-1);

    return spt_find_page(&curr->spt, addr);
}
#endif

• include/userprog/syscall.h

/** Project 3-Anonymous Page */
#ifndef VM
void check_address(void *addr);
#else
/** #Project 3: Anonymous Page */
struct page *check_address(void *addr);
#endif

9. page_fault 조건 수정

• userprog/exception.c

	/** Project 3-Anonymous Page */
	if ((!not_present && write) || (fault_addr < 0x400000 || fault_addr >= USER_STACK))
	{
		exit(-1);
	}

---

테스트 결과

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
FAIL tests/vm/pt-grow-stack
pass tests/vm/pt-grow-bad
FAIL tests/vm/pt-big-stk-obj
pass tests/vm/pt-bad-addr
pass tests/vm/pt-bad-read
pass tests/vm/pt-write-code
FAIL tests/vm/pt-write-code2
FAIL tests/vm/pt-grow-stk-sc
pass tests/vm/page-linear
pass tests/vm/page-parallel
pass tests/vm/page-merge-seq
FAIL tests/vm/page-merge-par
FAIL tests/vm/page-merge-stk
FAIL tests/vm/page-merge-mm
pass tests/vm/page-shuffle
FAIL tests/vm/mmap-read
FAIL tests/vm/mmap-close
FAIL tests/vm/mmap-unmap
FAIL tests/vm/mmap-overlap
FAIL tests/vm/mmap-twice
FAIL tests/vm/mmap-write
FAIL tests/vm/mmap-ro
FAIL tests/vm/mmap-exit
FAIL tests/vm/mmap-shuffle
pass tests/vm/mmap-bad-fd
FAIL tests/vm/mmap-clean
FAIL tests/vm/mmap-inherit
FAIL tests/vm/mmap-misalign
FAIL tests/vm/mmap-null
FAIL tests/vm/mmap-over-code
FAIL tests/vm/mmap-over-data
FAIL tests/vm/mmap-over-stk
FAIL 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
FAIL tests/vm/mmap-off
FAIL tests/vm/mmap-bad-off
FAIL tests/vm/mmap-kernel
FAIL tests/vm/lazy-file
pass tests/vm/lazy-anon
FAIL tests/vm/swap-file
FAIL tests/vm/swap-anon
FAIL tests/vm/swap-iter
FAIL 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
FAIL tests/vm/cow/cow-simple
33 of 141 tests failed.