Pintos 프로젝트3 고찰같다

모기·2025년 6월 4일
gochal

Pintos.Gochal

목록 보기
7/7

WARNING

<코드를 따라가기 전에 주의할 사항>
구현 중간중간에 자잘한 버그들을 잡기위해 코드가 수시로 수정을 했기 때문에 기록이 완벽하지 않을 수 있다. 따라서 구현 중 생기는 버그들은 스스로 고치거나, 혹은 COMPLETION 부분을 참고하길 바란다.

####

pintos 코드 작성을 시작하면 항상 고민을 하게 되는게 있다.

뭐부터 시작해야 되지?

프로젝트 1부터 항상하게 되는 고민이다.
gitbook 순서가 정답이니, 일단 gitbook을 따라가보려고 한다.

가장 먼저 구현해야할 것은

IMPLEMENTATION

Implement supplemental page

이다.

여기서 언급했듯이, thread 내부의 vm이 supplemental page에 해당한다.

vm의 구조는 hash table이고, vm의 bucket 안에 vm_entry라는 것이 있다.
여기서 vm_entry는 supplemental_page와 같다.

그럼 어떻게 구현해야 할까?
우선 pintos의 해시테이블 구조를 확인하고 오자.

무엇을 해야할지 목록을 적고 구현해보자.

  1. supplemental page를 해시테이블의 형태로 만들 예정이므로 구조체에 해시테이블을 추가한다.
struct supplemental_page_table {
	struct hash sup_page_hash;
};
  1. page끼리 연결될 예정이므로 page 내부에도 hash_elem을 추가한다.
    또한 초기화함수에 wriable이라는 bool값이 매개변수로 주어지는데, 이를 저장할 멤버 변수도 추가한다.
struct page {
	const struct page_operations *operations;
	void *va;              /* Address in terms of user space */
	struct frame *frame;   /* Back reference for frame */

	/* Your implementation */
	struct hash_elem hash_elem;
	bool writable;

	/* Per-type data are binded into the union.
	 * Each function automatically detects the current union */
	union {
		struct uninit_page uninit;
		struct anon_page anon;
		struct file_page file;
#ifdef EFILESYS
		struct page_cache page_cache;
#endif
	};
};
  1. supplemental page가 초기화될 때 해시테이블도 동시에 초기화 시켜준다.
/* Initialize new supplemental page table */
void
supplemental_page_table_init (struct supplemental_page_table *spt UNUSED) {
	hash_init(&spt->sup_page_hash, va_to_hashvalue, hash_value_comparer, NULL);
}
  • 근데 해시테이블을 초기화할 때 해시함수와 해시값비교 함수가 필요하다.
uint64_t
va_to_hashvalue(struct hash_elem *e, void* aux) {
	struct page* tmp_page = hash_entry(e, struct page, hash_elem);
	return hash_bytes(&tmp_page->va, sizeof(void *));
}

가상주소를 해시 값으로 변환하는 함수다.
리턴 부분은 gpt 도움을 받았다..

bool
hash_value_comparer(struct hash_elem* a, struct hash_elem* b, void *aux) {
	uint64_t pva_a; 
	uint64_t pva_b;

	struct page* tmp_a = hash_entry(a, struct page, hash_elem);
	struct page* tmp_b = hash_entry(b, struct page, hash_elem);

	pva_a = tmp_a->va;
	pva_b = tmp_b->va;

if (pva_a < pva_b)
    return true;
else
    return false;
}

해시 엘리먼트로 페이지를 얻고
페이지가 가지고 있는 va값으로 비교하는 함수다.

  1. 스레드에 spt를 위한 공간을 추가한다.(는 이미 추가돼 있다.)

그리고 여기를 보면 vm_entry == page 즉 page를 말록을 사용해서 할당한다.

	if (spt_find_page (spt, upage) == NULL) {
		/* TODO: Create the page, fetch the initialier according to the VM type,
		 * TODO: and then create "uninit" page struct by calling uninit_new. You
		 * TODO: should modify the field after calling the uninit_new. */
		struct page* new_page = malloc(sizeof(struct page));

할당했다.

모든 페이지들은 처음에 초기화되지 않도록 설계돼있다. 따라서 최초에 생성되는 페이지는 uninit new로 건드려야한다.

그래서 케이스를 나누고, 함수 포인터를 할당한 뒤에 uninit new로 page를 초기화하고
spt에 insert하는 코드를 추가했다.

다음은 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;

	/* 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,
		 * TODO: and then create "uninit" page struct by calling uninit_new. You
		 * TODO: should modify the field after calling the uninit_new. */
		struct page* new_page = malloc(sizeof(struct page));
		if (new_page == NULL) {
			goto err;
		}

		bool (*init_func)(struct page *, enum vm_type, void *);

		switch (VM_TYPE(type))
		{
		case VM_ANON:
			init_func = anon_initializer;
			break;
		case VM_FILE:
			init_func = file_backed_initializer;
			break;
		
		default:
			goto err;
		}
		uninit_new(new_page, upage, init, type, aux, init_func);
		new_page->writable = writable;

		/* TODO: Insert the page into the spt. */
		if (!spt_insert_page(spt, new_page)) {
			//TODO: Release page
			goto err;
		}
		return true;
	}
err:
	return false;
}

Implement frame

Frame management에서는 다음을 할 차례라고 한다.

• vm_get_frame
• vm_claim_page
• vm_do_claim_page

get_frame은 물리메모리에 해당하는 커널 가상 주소를 받는 함수이다.
이건 userprog 때 많이 봤을 것이다. palloc을 활용하면 된다.

static struct frame *
vm_get_frame (void) {
	struct frame *frame = malloc(sizeof(struct frame));
	/* TODO: Fill this function. */
	frame->kva = palloc_get_multiple(PAL_ZERO, 1);
	frame->page = NULL;
	if (frame == NULL || frame->kva == NULL) {
		PANIC("TODO");
		// ADD evict func
		//frame NULL과 kva NULL 분리하기
	}

	ASSERT (frame != NULL);
	ASSERT (frame->page == NULL);
	return frame;
}

PANIC("TODO") 역시 깃북에서 그러라고 해서 했다.

처음에 살짝 헷갈렸다. frame 안에 kva라는 게 없는줄 알아서 frame 구조체를 palloc으로 할당받았다.
frame 구조체 자체는 malloc으로 할당받고, frame의 kva자체는 palloc으로 할당받는게 맞는 것같다.

그 다음은 vm_claim_page이다.
코드가 너무 간단한데, page와 va밖에 없다.
그럼 간단하게 생각하면 va를 이용해서 page를 얻으라는 게 아닐까
여기서 말했듯이 모든 페이지 정보는 spt에 있다. 따라서 spt에서 찾아보자.

/* Claim the page that allocate on VA. */
bool
vm_claim_page (void *va UNUSED) {
	struct page *page = NULL;
	/* TODO: Fill this function */
	page = spt_find_page(&thread_current()->spt, va);

	return vm_do_claim_page (page);
}

그리고 마지막으로 do claim에서는 pte에 등록할 차례다.

/* 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 */
	frame->page = page;
	page->frame = frame;

	/* TODO: Insert page table entry to map page's VA to frame's PA. */
	uint64_t* cur_pml4 = thread_current()->pml4;
	if (pml4_get_page(cur_pml4, page->va) != NULL) {
		return false;
	} else {
		if (!pml4_set_page(cur_pml4, page->va, frame->kva, page->writable)) {
			return false; 
		}
	}

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

그럼 이제 anonymous page로 넘어가보자.

Anonymous page

여기선 anonymous 관련 함수를 다루게 된다.
깃북에 굉장히 설명이 많은데, 찬찬히 읽어보니 앞에서 다 구현된 내용들이다.
우리는 vm_alloc_page_with_initializer에서 페이지에 대해 전반적인 설정을 해둔 상태이다.

페이지 폴트가 일어나서 핸들러가 vm_try_handle_fault를 실행하면 lazy load를 하게된다.
이때 uninit_initialize 함수가 page 구조체 내부의 타입을 참고하여 관련 함수를 호출한다.

우선 우리가 해야할 것은 페이지 폴트가 유효한 접근인지 확인하는 것이다.
유효하지 않은 페이지 폴트에 대해서는 깃북에 나와있다.
lazy-loaded 페이지. 즉, 이미 load된 페이지이다.
스왑된 페이지. 이건 아직 우리가 구현하지 못했다.
쓰기 방지된 페이지. 추가적인 내용이 있는지 모르겠지만, 일단은 write를 활용하면 되지 않을까?
근데 정확히 write의 정체가 뭔지는 모르니 주석처리만 해둘 생각이다.

살짝 주의할 필요는 있다.

/* 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;
	uint64_t* cur_pml4 = thread_current()->pml4;
	
	addr = pg_round_down(addr);

	/* TODO: Validate the fault */
	if (pml4_get_page(cur_pml4, addr) != NULL) {
		return false;
	}

	//TODO: check this if
	// if (write) {
	// 	return false;
	// }

	/* TODO: Your code goes here */
	page = spt_find_page(spt, addr);
	if (page == NULL) {
		return false;
	}

	return vm_do_claim_page (page);
}

try_handle_fault도 어느 정도 된 것 같고 이제 lazy loading으로 넘어가보자.

우리가 먼저 손봐야되는 함수는 load_segment와 lazy_load_segment다.
lazy_load를 한다면 딱 부족한 부분만 파일에서 읽어서 올려야한다.

깃북에서는 aux를 수정하라고 했는데, 솔직히 어떻게 해야할지 감이 잡히지 않았다.
우선은 user_prog의 load_segment를 참고했다.

거기서 어떤 작업들이 필요한지 확인했다.

load_segment user_prog.ver

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

보면 kpage나 upage에 관한 정보는 page 구조체에 이미 있다.
그리고 더 필요한 정보들, 예를 들면 writable이나 현재 읽고 있는 페이지의 위치, read byte와 zero byte 등
정보를 aux에 넣으면 될 것 같다.

그래서 일단 다음과 같이

struct file_aux_info {
	struct file* file;
	off_t ofs;
	uint32_t read_bytes;
	uint32_t zero_bytes;
};

file_aux_info라는 구조체를 만들고

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 file_aux_info* aux_info = malloc(sizeof(struct file_aux_info));
		aux_info->file = file;
		aux_info->ofs = ofs;
		aux_info->read_bytes = page_read_bytes;
		aux_info->zero_bytes = page_zero_bytes;

		void *aux = aux_info;
		if (!vm_alloc_page_with_initializer (VM_FILE, upage,
					writable, lazy_load_segment, aux))
			return false;

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

안에 정보들을 저장했다. 특히 lazy load에서는 파일의 특정 부분을 읽어야하므로
ofs에 신경을 썼다.
그리고 이를 바탕으로 lazy load segment를 수정했다.
역시 load_segment를 많이 참고했다.

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. */
	uint8_t* upage = page->va;
	uint8_t* kpage = page->frame->kva;
	
	struct file_aux_info* aux_info = (struct file_aux_info*)aux;
	struct file* file = aux_info->file;
	off_t ofs = aux_info->ofs;
	size_t page_read_bytes = aux_info->read_bytes;
	size_t page_zero_bytes = aux_info->zero_bytes;

	ASSERT ((page_read_bytes + page_zero_bytes) % PGSIZE == 0);
	ASSERT (pg_ofs (upage) == 0);
	ASSERT (ofs % PGSIZE == 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. */

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

	free(aux);
	return true;
}

사실 거의 복붙하고 뺄거만 뺐다.
그리고 aux는 이제 필요없으니 free 시켰다.

어떤 결과가 나올지 모르겠다. make check로 관측하기 전까지는 말이다...
현재 성공과 실패가 중첩된 상태다.

그 다음은 setup_stack이다.
깃북을 참고하니 해야할 리스트는 다음과 같다.
1. 첫 번째 스택 페이지는 프로그램이 로드될 때 지연 로딩 없이 바로 할당하고 초기화한다.
2. 스택임을 식별할 수 있는 방법을 제공한다. (ex. VM_MARKER_0)
3. 페이지 폴트가 발생한 주소에 해당하는 페이지 구조체를 찾아야 한다.

/* Create a PAGE of stack at the USER_STACK. Return true on success. */
static bool
setup_stack (struct intr_frame *if_) {
	bool success = true;
	void *stack_bottom = (void *) (((uint8_t *) USER_STACK) - PGSIZE);
	bool writable = true;

	/* 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 */
	if (!vm_alloc_page_with_initializer(VM_ANON, stack_bottom, writable, NULL, NULL)) {
		return false;
	}
	if (!vm_claim_page(stack_bottom)) {
		return false;
	}
	if_->rsp = USER_STACK;
	return success;
}

페이지 만들고 바로 할당했다.

디버깅

  1. 구조체 만들 때 멤버 변수를 구조체 포인터로 만들어놓고 말록을 안해서 오류가 났다. 그래서 그냥 포인터 아닌 구조체를 넣었다.

  2. 그 밖에 타입 실수라든지 아이디어 수정은 GPT의 도움을 받았다. 어떻게 보면 정답이 있는 문제이기 때문에 내가 상상한 방향과 다를 때가 많다.

예를 들면 나는 페이지의 주소를 그냥 해시 함수에 넣으려고 했고
해시값을 비교하려고 했었다.
이런 부분이 어려운 것 같다.

  1. if_->rsp를 USER_STACK으로 바꾸지 않아서 틀렸다. 이건 똑띠 도움을 받았다. make test로 바로 pass 나오는 거 보면서 같이 깜짝 놀랐다.

  2. ptr error를 처리할 때 pml4에서 NULL이면 에러 처리를 했지만, 이제 페이지 폴트가 알아서 처리하기 때문에 syscall.c의 내용을 수정했다.
    그냥 삭제해도 될 것 같기도 하고..

static bool ptr_error (char* input_ptr, void* aux) {
	if (input_ptr == NULL) {
		return true;
	}
	//address is user area
	if ((enum waddr)aux == UADDR) {
		if (!is_user_vaddr(input_ptr)) {
			return true;
		}
		if (pml4_get_page(thread_current()->pml4, input_ptr) == NULL) {
			return false;
		}
	}
	
	if ((enum waddr)aux == KADDR) {
		if (!is_kernel_vaddr(input_ptr)) {
			return true;
		}
	}

	return false;
}

중간점검

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
FAIL tests/userprog/fork-once
FAIL tests/userprog/fork-multiple
FAIL tests/userprog/fork-recursive
FAIL tests/userprog/fork-read
FAIL tests/userprog/fork-close
FAIL tests/userprog/fork-boundary
FAIL tests/userprog/exec-once
FAIL tests/userprog/exec-arg
FAIL tests/userprog/exec-boundary
pass tests/userprog/exec-missing
pass tests/userprog/exec-bad-ptr
FAIL tests/userprog/exec-read
FAIL tests/userprog/wait-simple
FAIL tests/userprog/wait-twice
FAIL tests/userprog/wait-killed
pass tests/userprog/wait-bad-pid
FAIL tests/userprog/multi-recurse
FAIL tests/userprog/multi-child-fd
pass tests/userprog/rox-simple
FAIL tests/userprog/rox-child
FAIL tests/userprog/rox-multichild
pass tests/userprog/bad-read
pass tests/userprog/bad-write
FAIL tests/userprog/bad-read2
FAIL tests/userprog/bad-write2
pass tests/userprog/bad-jump
FAIL 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
FAIL tests/vm/page-parallel
FAIL 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
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
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
pass tests/vm/mmap-bad-off
pass 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
FAIL tests/filesys/base/syn-read
pass tests/filesys/base/syn-remove
FAIL 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
FAIL tests/threads/priority-change
FAIL tests/threads/priority-donate-one
FAIL tests/threads/priority-donate-multiple
FAIL tests/threads/priority-donate-multiple2
FAIL tests/threads/priority-donate-nest
FAIL tests/threads/priority-donate-sema
FAIL tests/threads/priority-donate-lower
pass tests/threads/priority-fifo
pass tests/threads/priority-preempt
FAIL tests/threads/priority-sema
FAIL tests/threads/priority-condvar
FAIL tests/threads/priority-donate-chain
FAIL tests/vm/cow/cow-simple
60 of 141 tests failed.

드디어 영접했다. 그럼 다시 들어가보자.

이제는 fork를 향해 나아가게 될 것이다.
supplemental page table copy/kill을 구현해야 한다.

bool supplemental_page_table_copy (struct supplemental_page_table *dst,
    struct supplemental_page_table *src);

여기서 src spt를 dst spt로 복사해야한다.
사실상 spt는 해시 테이블을 의미하므로
(spt를 가리키고 있는 스레드도 추가하긴 했다.)

해시테이블 복사를 기반으로 페이지를 복사하는 것이라고 생각해도 될 것 같다.
그래서 해시테이블에 함수를 하나 추가했다.

사용자 정의 복사 함수를 이용해서 src 해시테이블을 dst 해시테이블로 복사하는 함수이다.
먼저 매개변수로 넣을 사용자 정의 복사 함수를 hash.h에 typedef으로 정의한다.

(hash.h)
/* Performs copy */
typedef struct hash_elem* hash_copy_func (struct hash_elem* src);

그 다음 hash.c에 hash_copy 함수를 만든다.

(hash.c)
void
hash_copy (struct hash* dst, struct hash* src, hash_copy_func *copy_func) {
	struct hash_iterator tmp_iterator;
	struct hash_elem* old_elem;
	struct hash_elem* new_elem;
	
	hash_first(&tmp_iterator, src);
	
	int total_elem_cnt = hash_size(src);
	for (int i = 0; i < total_elem_cnt; i++) {
		old_elem = tmp_iterator.elem;
		new_elem = copy_func (old_elem);
		if (new_elem == NULL) {
			return;
		}
		hash_insert(dst, new_elem);
		hash_next(&tmp_iterator);
	}
}

솔직히 핀토스하는 거보다 이런거 구현하는게 더 재밌다.

원리는
1. iterator를 사용하여 해시테이블을 순회하며 old hash element(old_elem)를 얻는다.
2. old_elem를 복사함수에 넣으면 new hash element(new_elem)이 반환된다.
3. new_elem를 새로운 해시테이블에 삽입하는 식으로 복사한다.

이제 copy_func에 넣을 복사함수를 만들면된다.
마지막으로 vm.c에 복사함수를 하나 생성한다.
copy_page라는 이름의 복사함수인데, 페이지를 똑같이 복사하다보니
약간의 쌔함을 느꼈다.

설마 다 복사해야하나?

그래서 뚝딱 구현했다. 아무래도 uninit된 페이지와 init된 페이지는 구분해야할 것 같아서

struct hash_elem*
copy_page (struct hash_elem* src_elem) {
	struct page* old_page = hash_entry(src_elem, struct page, hash_elem);
	struct page* new_page = malloc(sizeof(struct page));
	//TODO: determine true or false

	switch (old_page->now_type)
	{
		case VM_UNINIT:
			printf("uninit\n");
			uninit_new(new_page, old_page->va, old_page->uninit.init, old_page->uninit.type, old_page->uninit.aux, old_page->uninit.page_initializer);
			break;
		case VM_ANON:
			printf("vm anon\n");
			vm_copy_claim_page(old_page, new_page);
			break;
		case VM_FILE:
			printf("vm file\n");
			vm_copy_claim_page(old_page, new_page);
			break;
	
		default:
			break;
	}

	return &new_page->hash_elem;
}

현재 구현한 함수인데, 어째서인지 해시 테이블에 모르는 녀석이 하나 더 들어가?있어서
hash_copy 함수에서 hash size는 8인데 스택 페이지까지 복사하지 못해서 오류가 난다.
아무튼 그래서 프린트 문이 좀 잔뜩 들어가있다.

아래는 ANON이랑 FILE일 때 사용하는 함수다.

bool
vm_copy_claim_page (struct page* old_page, struct page* new_page) {
	new_page->operations = old_page->operations;
	new_page->va = old_page->va;
	new_page->now_type = old_page->now_type;
	new_page->writable = old_page->writable;
	printf("copy va: %p\n", new_page->va);

	//to obtain kva
	struct frame *frame = vm_get_frame ();

	/* Set links */
	frame->page = new_page;
	new_page->frame = frame;

	/* TODO: Insert page table entry to map page's VA to frame's PA. */
	uint64_t* cur_pml4 = thread_current()->pml4;
	if (pml4_get_page(cur_pml4, new_page->va) != NULL) {
		printf("this false 1\n");
		return false;
	} else {
		if (!pml4_set_page(cur_pml4, new_page->va, frame->kva, new_page->writable)) {
			printf("this false 2\n");
			return false; 
		}
	}
	memcpy(new_page->frame->kva, old_page->frame->kva, PGSIZE);
	return true;
}

그럼 어떻게 스택 페이지가 못 들어간 줄 알았냐?

당연히 프린트 문을 잔뜩 찍었다.
hash elem의 주소를 위주로 찍었다.

위에서 차례대로 내려오는 주소와 아래에서 차례대로 올라가는 주소가 같다.
근데 딱 하나
i: 0의 elem 주소가 0x8004243018이고
stack hash elem의 주소가 0x8004243438로 다르다.

누구냐 넌

이번엔 같은 해시에 들어갔는지 확인을 해보겠다.

확실하다.
아마도 rehash 하면서 hash 주소가 달라진 것 같은데,
같은 해시로 들어갔다는 것은 확인이 가능하다.

혹시나 해서 total_elem_cnt에 1을 더해서 for문을 돌리니
사라졌던 elem이 나타났다.

해시 문서를 읽어보니 설명이 잘 나와있었음에도 불구하고 잘못 돌렸던 것이었다.

/* Initializes I for iterating hash table H.

   Iteration idiom:

   struct hash_iterator i;

   hash_first (&i, h);
   while (hash_next (&i))
   {
   struct foo *f = hash_entry (hash_cur (&i), struct foo, elem);
   ...do something with f...
   }

   Modifying hash table H during iteration, using any of the
   functions hash_clear(), hash_destroy(), hash_insert(),
   hash_replace(), or hash_delete(), invalidates all
   iterators. */

그래서 다음과 같이 수정했다.

bool
hash_copy (struct hash* dst, struct hash* src, hash_copy_func *copy_func) {
	struct hash_iterator tmp_iterator;
	struct hash_elem* old_elem;
	struct hash_elem* new_elem;
	
	hash_first(&tmp_iterator, src);
	int total_elem_cnt = hash_size(src);

	while (hash_next (&tmp_iterator))
	{
		old_elem = tmp_iterator.elem;
		new_elem = copy_func (old_elem);
		if (new_elem == NULL) {
			//TODO: FREE
			return false;
		}
		hash_insert(dst, new_elem);
	}

	return true;
}

fork가 잘 돌아간다.

그 다음으로 봉착한 문제는 fork-read 문제였다.
복사된 파일을 lazy loading하는 문제인데,

이렇게 나와서
lazy_loading 부분의 page_read_bytes와 page_zero_bytes을 프린트문으로 출력했다.
할당을 담당했던 페이지 주소랑 lazy loading의 페이지 주소도 출력해서 비교했다.

fork 과정에서는 복사가 잘 된 것 같은데 왜 lazy load page zero가 떴을까 생각했다.
이번에는 페이지말고 유저 가상 주소를 찍어봤다. 그랬더니 드러났다.

va 주소가 같다. 그 말인 즉슨 lazy load에서 page read와 page zero를 담당하는 구조체에 문제가 생긴건 아닐까 생각해보니

두 페이지 모두 같은 구조체를 가리키고 있다. aux를 깊은 복사가 아닌 참조 복사를 하고 free를 시켜서 생긴 문제이다.

그래서 복사할 때 aux는 깊은 복사를 했다.
copy page를 살짝 수정했다.

(vm.c)
struct hash_elem*
copy_page (struct hash_elem* src_elem) {
	struct page* old_page = hash_entry(src_elem, struct page, hash_elem);
	struct page* new_page = malloc(sizeof(struct page));
	//TODO: determine true or false

	switch (old_page->now_type)
	{
		case VM_UNINIT:
			vm_copy_uninit_page (old_page, new_page);
			break;
		case VM_ANON:
			vm_copy_claim_page(old_page, new_page);
			break;
		case VM_FILE:
			vm_copy_claim_page(old_page, new_page);
			break;
	
		default:
			break;
	}

	return &new_page->hash_elem;
}

bool
vm_copy_uninit_page (struct page* old_page, struct page* new_page) {
	return uninit_copy_page(new_page, old_page->va, old_page->uninit.init, old_page->uninit.type, old_page->uninit.aux, old_page->uninit.page_initializer);
}

그리고 리팩토링을 좀 했다.
먼저 file.h로 file_aux_info를 옮기고

(file.h)
struct file_aux_info {
	struct file* file;
	off_t ofs;
	uint32_t read_bytes;
	uint32_t zero_bytes;
};

uninit new 대신 uninit copy page 함수를 만들었다.

bool
uninit_copy_page (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);
	struct file_aux_info* new_aux;

	switch (type)
	{

	case VM_ANON:
		break;
	case VM_FILE:
		new_aux = malloc(sizeof(struct file_aux_info));
		memcpy(new_aux, aux, sizeof(struct file_aux_info));
		aux = new_aux;
		break;
	
	default:
		break;
	}

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

결과는 통과다.

마지막으로 fork-boundary가 날 괴롭혔는데,
솔직히 프린트 문 진짜 많이 찍으면서 돌렸다.
결국 어떤 프린트 문까지 찍었냐면, 페이지 구조체의 writable 멤버 변수가 어떻게 되는지까지 찍었다.
무엇이 문제였고, 어떻게 해결했는지를 말하자면

bool
vm_copy_uninit_page (struct page* old_page, struct page* new_page) {
	return uninit_copy_page(new_page, old_page->va, old_page->uninit.init, old_page->uninit.type, old_page->uninit.aux, old_page->uninit.page_initializer);
}

처음엔 이런 상태였다.
그리고 writable이 0이 나오길래, 내가 설정을 따로 안해줘서 그런가보다 하고

bool
vm_copy_uninit_page (struct page* old_page, struct page* new_page) {
	new_page->writable = old_page->writable;
	return uninit_copy_page(new_page, old_page->va, old_page->uninit.init, old_page->uninit.type, old_page->uninit.aux, old_page->uninit.page_initializer);
}

이렇게 추가를 해줬는데 여전히 같았다.
나는 lazy load 같은 다른 곳에서 문제가 생기나하고 쭉쭉 찾아보다가
uninit copy page 함수를 다시 들여다봤다.

bool
uninit_copy_page (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);
	struct file_aux_info* new_aux;

	switch (type)
	{

	case VM_ANON:
		break;
	case VM_FILE:
		new_aux = malloc(sizeof(struct file_aux_info));
		memcpy(new_aux, aux, sizeof(struct file_aux_info));
		aux = new_aux;
		break;
	
	default:
		break;
	}

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

여기서

	*page = (struct page) {
		.operations = &uninit_ops,
		.va = va,
		.frame = NULL, /* no frame for now */
		.now_type = VM_UNINIT,
		.uninit = (struct uninit_page) {
			.init = init,
			.type = type,
			.aux = aux,
			.page_initializer = initializer,
		}

이 부분이 문제였는데,
이건 page.operations = &uninit_ops를 하는 것과 다른 결과가 나온다는 사실이었다.
그냥 새로운 구조체를 덮어쓰는 형태인 것 같다.
그래서 해당 필드에 writable 값이 없으니 당연히 0이 돼버렸다.

bool
vm_copy_uninit_page (struct page* old_page, struct page* new_page) {
	bool succ = false;
	succ = uninit_copy_page(new_page, old_page->va, old_page->uninit.init, old_page->uninit.type, old_page->uninit.aux, old_page->uninit.page_initializer);
	new_page->writable = old_page->writable;
	new_page->owner = thread_current();
	return succ;
}

위와 같이 수정하니 아주 잘 돌아간다.

bad-jump2도 fail날텐데 이건 알아서 해결할 수 있을 것이다.

Stack Growth

	if ((now_rsp > addr) && (addr >= now_rsp - sizeof(void*)) && (addr >= USER_STACK - (1<<20)));
	{
		if (stack_full < 20) {
			vm_stack_growth(rdown_addr);
		} else {
			return false;
		}
	}

에러에러에러에ㅓ레어레어레어에ㅓ레어레어레러

FAIL tests/userprog/open-bad-ptr
FAIL tests/userprog/read-bad-ptr
FAIL tests/userprog/write-bad-ptr
FAIL tests/userprog/exec-bad-ptr
FAIL tests/userprog/bad-read
FAIL tests/userprog/bad-write
FAIL tests/vm/pt-grow-bad
pass tests/vm/pt-big-stk-obj
43 of 141 tests failed.

어쩌다보니 bad ptr이 맛이 가버렸다.
해결 중이다. 해결했다.
놀랍게도 if문 뒤에 세미콜론을 붙인게 문제였다.
위에 보이는지..?
저렇게 써놓고 2시간을 고민했다.

...

정리가 됐다.
이래저래 많이 손봤다.
시스템 콜의 ptr error 함수도 간소화시켰고 다른 것들도 이래저래 건드렸다.
혹시나 이 블로그 글을 따라서 하고 있다면 그 밖에 터지는 버그들은 알아서 디버깅하길 바란다.

아무튼 아래는 수정된 stack growth를 포함한 vm_try_handle_fault이다.

/* 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;
	uint64_t* cur_pml4 = thread_current()->pml4;
	if (!is_user_vaddr(addr)) {
		return false;
	}
	// printf("try fault cur: %s\n", thread_current()->name);
	// printf("try fault through \n");

	void* rdown_addr = addr;
	rdown_addr = pg_round_down(rdown_addr);
	uint64_t now_rsp = user ? f->rsp : thread_current()->user_rsp;
	// printf("user: %d\n", user);
	// printf("rsp : %p\n", now_rsp);
	// printf("addr: %p\n", addr);
	// printf("maximum: %p\n", USER_STACK - (1<<20));
	
	/* TODO: Validate the fault */
	if (pml4_get_page(cur_pml4, rdown_addr) != NULL) {
		return false;
	}
	
	if ((USER_STACK >= addr) && (addr >= now_rsp - sizeof(void*)) && (addr >= USER_STACK - (1<<20)))
	{
		if (stack_full < 20) {
			// printf("growth\n");
			// printf("user stack: %p\n", USER_STACK);
			// printf("addr: %p\n", rdown_addr);
			vm_stack_growth(rdown_addr);
		} else {
			return false;
		}
	}

	/* TODO: Your code goes here */
	page = spt_find_page(spt, rdown_addr);
	if (page == NULL) {
		return false;
	}

	if (write && !(page->writable)) {
		return false;
	}

	return vm_do_claim_page (page);
}

아래는 수정된 syscall ptr error이고

static bool ptr_error (char* input_ptr) {
	if (input_ptr == NULL) {
		return true;
	}
	
	if (!is_user_vaddr(input_ptr)) {
		return true;
	}

	return false;
}

아래는 수정된 syscall read이다.

int read (int fd, void *buffer, unsigned length) {
	if (ptr_error(buffer)) {
		exit(-1);
	}

	struct page* get_page = spt_find_page(&thread_current()->spt, pg_round_down(buffer));
	if (get_page != NULL && !(get_page->writable)) {
		exit(-1);
	}

	if (fd == 0) {
		for (unsigned i = 0; i < length; i++) {
			((uint8_t *)buffer)[i] = input_getc();
		}
		return length;
	}

	struct thread* curr = thread_current();
	if (fd >= FD_MAX || fd < 0 || curr->file_dt[fd] == NULL) {
		return -1;
	}

	unsigned int read_len;
	read_len = file_read(curr->file_dt[fd], buffer, length);

	return read_len;
}

없는 페이지를 읽을 수 없으니 그냥 에러다. 기억나는 건 여기까지이다.
위 코드를 올리고 나서도 세 번은 다시 또 수정해서 올렸다.

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
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
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
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
pass tests/vm/mmap-bad-off
pass 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
FAIL tests/threads/priority-change
FAIL tests/threads/priority-donate-one
FAIL tests/threads/priority-donate-multiple
FAIL tests/threads/priority-donate-multiple2
FAIL tests/threads/priority-donate-nest
FAIL tests/threads/priority-donate-sema
FAIL tests/threads/priority-donate-lower
pass tests/threads/priority-fifo
pass tests/threads/priority-preempt
FAIL tests/threads/priority-sema
FAIL tests/threads/priority-condvar
FAIL tests/threads/priority-donate-chain
FAIL tests/vm/cow/cow-simple
32 of 141 tests failed.

알람 관련 fail이 11개 있다.

Memory Mapped Files

구현 방법은 간단했다.
사실 load segment랑 거의 다를바 없다.
mmap에서 load segment랑 비슷하게 구현해주고
mmap lazy load를 따로 만들어서 lazy load segment와 비슷하게 구현해주면 된다.
중요한건 mmap이 성공했을 때 void*를 반환하는 것이다
나는 *를 대충 보고 지나쳐서 반환값이 없게 만들었다가 다시 고쳤다.

다만 load segment는 read bytes와 zero bytes를 따로 구해주지만
여기서는 우리가 구해야한다.
구하는 방법도 어렵지 않긴 하다. 특히 load를 참고하면 된다.
혼자서 고민해볼만하다.

void *
do_mmap (void *addr, size_t length, int writable,
	struct file *file, off_t offset) {
	off_t total_len = file_length(file);
	uint32_t read_bytes = total_len - offset;
	uint32_t zero_bytes = ROUND_UP(read_bytes, PGSIZE) - read_bytes;
	off_t ofs = offset;
	uint8_t* upage = addr;

	// printf("do mmap cur: %s\n", thread_current()->name);
	// printf("do mmap va: %p\n", addr);
	// printf("do mmap total len: %d\n", total_len);
	// printf("do mmap read bytes: %d\n", read_bytes);
	// printf("do mmap zero bytes: %d\n", zero_bytes);
	// printf("do mmap offset: %d\n", ofs);
	// printf("do mmap writable: %d\n", writable);
	
	while (read_bytes > 0 || zero_bytes > 0) {
		// printf("do mmap while\n");
		/* 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 file_aux_info* aux_info = calloc(1, sizeof(struct file_aux_info));
		if (aux_info == NULL) {
			return NULL;
		}
		aux_info->file = file;
		aux_info->ofs = ofs;
		aux_info->read_bytes = page_read_bytes;
		aux_info->zero_bytes = page_zero_bytes;

		void *aux = aux_info;
		if (!vm_alloc_page_with_initializer (VM_FILE, upage,
					writable, lazy_load_mmap, aux)) {
						free(aux_info);
						return NULL;
					}

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

	return addr;
}

munmap을 구현 방향에 대해 고민 중이다.
현재 두 가지 문제에 봉착했는데,

첫 번째는 파일 전체 할당 해제와 관련된 것이다.
munmap을 하게되면 해당 주소와 관련된 file 페이지 전체를 할당해제해야 한다.
예를 들어 mmap을 주소 1000번에다가 했는데 파일이 생각보다 커서
1000번, 2000번, 3000번 주소에 나눠서 할당이 됐다고 하자.
만약 munmap이 2500번을 가리키더라도 1000, 2000, 3000에 있는 파일 모두를 해제해야할 것이다.
그래서 이를 어떻게 관리할지 고민중이다.

두 번째는 파일 타입과 관련된 것이다.
mmap을 해서 가상 메모리에 공간를 할당했다고 하자. 그 중에서는 fault를 일으켜 lazy load되는 녀석들도 있을 것이고, 그렇지 않은 녀석들도 있을 것이다.
문제는 이 둘의 타입이 다르다는 것이다.
하나는 uninit일테고, 하나는 file일 것인데 첫 번째 문제와 관련된 정보를 어디에 저장해야 하는지도 고민이다.

그래서 mmap된 파일 전체를 관리하는 리스트나 해시테이블을 따로 하나 생성할지
단지 관련있는 파일의 페이지끼리 리스트로 연결할지 고민이다.
최소한의 함수와 최소한의 구조체와 최소한의 멤버 변수를 쓰고 싶다.

일단 해결 방법을 좀 더 구체화시켜야할 것 같다.

  1. 한 페이지에서 다른 관련 페이지로 어떻게 접근할 것인가?
    두 가지 해결 방법이 생각난다.

  • (1안)페이지 구조체에 다른 페이지로 접근할 수 있는 방법 만들기
    이 방법은 구조체 안에 다른 무언가를 만들어야 한다.

  • (2안)페이지 구조체 자체의 가상 주소를 활용해서 접근하기
    이 방법은 페이지 가상 주소가 2000이면 ±1000하는 식으로 접근하는 방법이다.

  1. 접근한 페이지가 동일한 파일에 매핑된 페이지인지 어떻게 알 것인가?
    위 문제에서 1안은 사실상 무조건적으로 매핑된 파일에 접근하게 된다. 따라서 별도의 정보를 추가하지 않아도 된다.
    하지만 2안은 이 파일이 어떤 파일을 매핑하고 있는지, mmap된 파일인지 정보가 필요하다.
    따라서 결국 파일에 정보를 추가해야 한다면, 2안은 보안상의 문제라든지 버그를 일으킬 가능성이 높기 때문에
    1안으로 가야한다.

  2. 그렇다면 어떤 구조체에 어떤 멤버 변수를 추가하고, 어떤 형태로 관리할 것인가?
    mmap을 할 때, mmap 관리 리스트를 커널 힙에 만들고
    페이지에는 mmap 관리 리스트를 가리키는 포인터 하나와 리스트 엘리먼트 하나를 만들면 될 것같다.

해서

struct page {
	struct hash_elem hash_elem;
	const struct page_operations *operations;
	void *va;              /* Address in terms of user space */
	struct frame *frame;   /* Back reference for frame */

	/* Your implementation */
	bool writable;
	struct thread* owner;
	
	/* For mmaped page */
	struct list* mmaped_list;
	struct list_elem mmaped_elem; 

	/* Per-type data are binded into the union.
	 * Each function automatically detects the current union */
	union {
		struct uninit_page uninit;  
		struct anon_page anon;
		struct file_page file;
#ifdef EFILESYS
		struct page_cache page_cache;
#endif
	};
};

구조체를 하나 만들어주고 file.c의 함수들도 업데이트 했다.

static bool
lazy_load_mmap (struct page *page, void *aux) {
	// printf("mmap lazy load\n");

	uint8_t* upage = page->va;
	uint8_t* kpage = page->frame->kva;
	
	struct file_aux_info* aux_info = (struct file_aux_info*)aux;
	struct file* file = aux_info->file;
	off_t ofs = aux_info->ofs;
	size_t page_read_bytes = aux_info->read_bytes;
	size_t page_zero_bytes = aux_info->zero_bytes;

	ASSERT ((page_read_bytes + page_zero_bytes) % PGSIZE == 0);
	ASSERT (pg_ofs (upage) == 0);
	ASSERT (ofs % PGSIZE == 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. */

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

	file_close(file);
	free(aux);
	return true;
}

/* Do the mmap */
void *
do_mmap (void *addr, size_t length, int writable,
	struct file *file, off_t offset) {
	addr = pg_round_down(addr);

	off_t total_len = file_length(file);
	uint32_t read_bytes = total_len - offset;
	uint32_t zero_bytes = ROUND_UP(read_bytes, PGSIZE) - read_bytes;
	off_t ofs = offset;
	uint8_t* upage = addr;
	
	struct list* mmap_pages_list = malloc(sizeof(struct list));
	list_init(mmap_pages_list);
	struct page* tmp_page;
	struct file* new_file;
	
	while (read_bytes > 0 || zero_bytes > 0) {
		// printf("do mmap while\n");

		new_file = file_open(file->inode);
		if (new_file == NULL) {
			return NULL;
		}
		/* 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 file_aux_info* aux_info = calloc(1, sizeof(struct file_aux_info));
		if (aux_info == NULL) {
			file_close(new_file);
			free(mmap_pages_list);
			return NULL;
		}
		aux_info->file = new_file;
		aux_info->ofs = ofs;
		aux_info->read_bytes = page_read_bytes;
		aux_info->zero_bytes = page_zero_bytes;

		void *aux = aux_info;
		if (!vm_alloc_page_with_initializer (VM_FILE, upage,
					writable, lazy_load_mmap, aux)) {
						file_close(new_file);
						free(mmap_pages_list);
						free(aux_info);
						return NULL;
					}

		tmp_page = spt_find_page(&thread_current()->spt, upage);
		tmp_page->mmaped_list = mmap_pages_list;
		list_push_back(mmap_pages_list, &tmp_page->mmaped_elem);

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

	return addr;
}

/* Do the munmap */
void
do_munmap (void *addr) {
	addr = pg_round_down(addr);
	struct page* munmap_page = spt_find_page(&thread_current()->spt, addr);
	if (munmap_page == NULL) {
		return;
	}

	struct list* mapped_pages = munmap_page->mmaped_list;
	if(mapped_pages == NULL) {
		return;
	}

	struct list_elem* mapped_page_elem;
	struct page* tmp_page;
	while (!list_empty(mapped_pages)) {
		mapped_page_elem = list_pop_front(mapped_pages);
		tmp_page = list_entry(mapped_page_elem, struct page, mmaped_elem);
		vm_dealloc_page(tmp_page);
	}
	free(mapped_pages);
}

추가적으로 mmap_close 테스트를 통과하기 위해 코드를 수정했는데,
close를 해도 mmap lazy load가 가능해야하기 때문에
mmap 시 같은 inode의 새로운 파일 하나를 열고, lazy load시 닫아주는 코드로 수정했다.

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
FAIL tests/vm/page-merge-par
FAIL tests/vm/page-merge-stk
FAIL 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
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
FAIL tests/threads/priority-change
FAIL tests/threads/priority-donate-one
FAIL tests/threads/priority-donate-multiple
FAIL tests/threads/priority-donate-multiple2
FAIL tests/threads/priority-donate-nest
FAIL tests/threads/priority-donate-sema
FAIL tests/threads/priority-donate-lower
pass tests/threads/priority-fifo
pass tests/threads/priority-preempt
FAIL tests/threads/priority-sema
FAIL tests/threads/priority-condvar
FAIL tests/threads/priority-donate-chain
FAIL tests/vm/cow/cow-simple
18 of 141 tests failed.

SWAP

이쯤되니 약간 포기하고 싶어진다.
할 수 있는 최대한 코드를 작성해보고 싶은데
심적으로 지치는 단계인 것 같다.

swap은 물리메모리에 등록된 페이지가 그 대상이므로
물리메모리에 등록되지 않은 uninit 페이지는 swap의 대상이 되지 않는다.

swap을 구현하게 되면 어떤 자료구조를 어디에 어떻게 쓰는게 좋을까 고민을 많이 하게 되는 것 같다.
그 부분도 천천히 고찰해볼 예정이다.

disk와 관련된 disk.c나 disk.h 내용을 알아둬야 한다.

여기서 볼 수 있듯이 pintos-mkdisk swap.dsk -- n 이 명령어를 사용해서 swap-disk를 만들긴 했다. 근데 반드시 만들어야 하는지, 만들지 않아도 되는지는 잘 모르겠다.

그리고 우리가 필요한 것은 swap table인데,
이 테이블을 배열로 구현할 지, 리스트로 구현할 지, 해시 테이블로 구현할지도 고민 중이다.

또한 페이지를 swap out하는 방식도 생각해야한다.
페이지 교체 정책을 참고하자.

우리가 할 것은

  1. 페이지 교체 정책 결정하기

  2. swap in, swap out 구현하기

  3. 페이지 스왑 테이블 자료구조 결정하고 구현하기

솔직히 말해, 난 이런 거에 좀 욕심이 있다.
쓸데없이 거창하게 시작하는 것에 욕심이 있다. 용두사미파다.

우선 거창쇼를 시작하기 위해

enum evicting_policies {
	FIFO,
	LRU,
	LFU,
	MFU,
	NUR
};

#define evicting_policy FIFO

위 코드를 vm.c 위쪽에 선언해주고, vm_get_victim을 아래와 같이 수정했다.

static struct frame *
vm_get_victim (void) {
	struct frame *victim = NULL;
	 /* TODO: The policy for eviction is up to you. */

	switch (evicting_policy)
	{
	case FIFO:
		/* code */
		break;
	case LRU:
		/* code */
		break;
	case LFU:
		/* code */
		break;
	case MFU:
		/* code */
		break;
	case NUR:
		/* code */
		break;
	
	default:
		break;
	}

	return victim;
}

물론 여기서 FIFO 내지는 LRU? 만 구현할 거다. 거창쇼는 여기서 끝이다.
그럼 이제 swap_in과 swap_out을 구현하자.
아마 swap_out이 좀 더 구현하기 쉬울 듯하다.

그 전에, 페이지 교체 정책을 보면 '가장 적게' 혹은 '가장 많게'라는 단어들이 보인다.
사실 난 이 '가장'이라는 단어를 보면 '그 자료구조'를 못 참는다.
정말 못 참겠다.

나는 핀토스에서 '힙'을 구현할 것이다.

힙을 보면 눈이 돌아버리는 나는 힙돌맨이다.

라고 생각했으나
생각해보니 힙 안에서 값이 바뀌면 힙 갱신이 좀 복잡해질 것 같아
일단 틀만 남겨두고 swap 구현이 끝난 다음에 만져볼 생각이다.
우선은 대충 list 만들어서 fifo로 관리하고, 그 다음에 수정을 할 예정이다.

결국 시간이 없어서 끝내지 못했다.
나만무 준비 기간에 하고 싶었으나 개인적인 일정과 겹쳐서 마무리하지 못했다.

COMPLETION

코드를 모두 옮겨쓸까 생각했으나
역시 깃허브가 편할 것 같다.
https://github1s.com/mogiyoon/pintos/tree/mogiyoon
보기 편하게 VSCODE 버전으로 링크를 걸어놨다.

profile
모기
안녕
이전 포스트

Pintos 구조 of 프로젝트 3 고찰같다 (2)

0개의 댓글