! 주의. project3에 swap 관련에서 에러가 걸린게 여기에 원인 있을 수 있으니 플로우를 참고만 할것.

어중간한 인간은...
project 3을 pass 하지 못하는 것일까...

아니다

어중간한건 인간이 아니다
코드지

내가 쓴 코드가 어중간한 것이다

아무튼 총 정리하다가 번뜩임이 오지 않을까 기대하며 쓰는 총정리

Introduction

...
프로젝트 3는 가장 어렵다고 한다
프로젝트 1234 중 가장 어렵다고....

글쿤아... 했지만
생각보다 초반엔 진도가 쉽게 나가서
어? 갠찬은데? 했지만

지금 8 fail로 살아가는 내 인생 생각하면 어려운게 맞는듯
(all pass 한 동료도 한분 뿐이고...)

그리고 여태까지의 플젝보다 넘나드는 함수가 많고
초반에는 기본 플로우도 안 짜면 디버깅도 불가할 뿐더러
기본 플로우의 개념 자체를 감 잡는 것도 어려운데
개념을 감 잡아도 그게 코드로 어떻게 이어지는지 이해하는건 다른 문제라...

보통 초반에 쉬운거 한두개하면서
자신감을 채우며 나아가기에는 그런 것마저 불가하니
(그리고 구현을 덜하면 어떤 케이스도 통과가 안됨.)
멘탈 잡기가 가장 어려운 프로젝트라고 할 수 있다.

아무리 안풀려도 붙잡는 끈기가 프로그래머의 덕목인걸 알수있는 플젝이었다...
(물론 그거에 더해 어디가 무슨 역할인지 알아야하는 걸 최고로 시험받음)

그런 의미에서 PintOS가 프로그래머가 한번쯤 거쳐볼 플젝임을 느꼈다.
좀 하이레벨이면 어디가 무슨 역할인지 아는게 인터페이스에 가까운 영역이라
그걸로는 상호 인과관계를 최대로 추론할수도 없을 뿐더러
추론할 일도 별로 없고, 개별의 하이레벨 언어로서 독자적으로 쌓인게 많아
다른 언어와 비교하여 차이점을 알아차리기도 어렵고 말이다.

(예를 들어, 아예 로우 레벨에서 시작해서
다른 하이레벨을 확인한다면
이 로우 레벨에서 무엇을 개선하여 이 하이레벨이 되었는지
알 수 있으니까.)

또 코드 양이 많고, 서로 상호관계가 있는 많은 코드를 확인하기에
적합하다는 생각이 들었다.

그걸 뼈저리게 느낀게 이번 프로젝트인데,
여기서 이미 구현한 hash 데이터 구조 함수를 쓰는 것도 쓰는건데,
이미 구현된 함수야 말로, 원래 제작자의 의도를 가장 많이 담고 있는 정보임을 깨닫게 되었기 때문이다.
(함수 명과 주석만으로 유추하게 만들어서 개개개개어려웠고 결국 잘못 유추했지만)

그래서, 다량의 코드에서 추가적으로 함수를 구현할때
필요한 순서를 알게 되었다.

• 전체 플로우를 개념적으로 이해하기.
• 내가 구현할 함수의 기능을 문장으로 순서대로 쓰기.
• 문장에 대응하는 함수가 있는지, 내가 쓸 기능에 대응하는 코드가 들어있는 파일을 전반적으로 확인해서 함수의 기능들을 확인하기.
  (더해, 이걸 보면 내가 쓰는 함수의 디테일을 알 수 있다.)
• 기존 문장에서 내가 알아낸 함수들을 더해 슈도 코드 쓰기.
• 직접 코드를 써보고 내가 구현하려는 알고리즘과 벗어나는 점이 있다면 수정하기....

...
그래서 마지막 swap 시점에서는
솔루션과 거의 유사한 코드가 완성되었으나
안되긴 했지..젠장 아무튼

여기서 관건은

• 전체 플로우를 개념적으로 이해하기
• 내가 구현할 기능을 문장으로 순서대로 쓰기

이 부분이 제대로 되지 않는다면, 내가 기존 코드를 아무리 참고해도,
디버깅을 아무리 해도, 애초에 고려하지 않은 부분이나 그런게 크다면
디버깅 수준으로 해결할 수 없다는 말이다.

그래서 알고리즘, 코딩 문제에서 풀이 떠올리기, 그런게 중요한 거겠지.

또 그만큼 내가 짜려는 코드가 무엇이 효율적인지
이 단계에서 미리 생각하는게 당연히 좋기 때문에

• 내가 구현하려는 기능을 어떻게 순차적으로 전개할 것인지,
• 또 이 기능이 앞으로 어떻게 쓰일 것이므로 어떤 것을 고려하여 보완하였는지,

가 정말 중요하다.
냅다 짜봤자 다 고쳐야하면 시간이 오래걸리기 때문이다.

그래서 개념을 확인하느라 늦거나 코드를 늦게 짜는 것을 두려워할 필요는 없을 것같다.
(진짜 안 짜면 그건 문제지만.)
어느 정도 최대한 알았다! 싶으면 바로 돌입할 줄도 알아야하지만,
어느 정도 알 때까지 기다리는 인내심도 필요하다.

아마 다른 사람에게

이 기능을 이렇게 구현할 건데,
이러한 걸 고려해서,
이런 순차로 전개할 것이다,

라고 설명할 수 있을 정도라면 구현해도 된다고 생각한다.

...
막상 쓰고 보니,
나는 알고리즘 풀때는 대개 풀이 자체가 떠올리기 힘들어서
어쩔 수 없이 비효율적인 방법이라도 채택해서
이거라도 가능한지 확인하는 걸 자주 하는데,

그런 점에 있어서 얘초에 풀이를 떠올리지 못한다면
최대한 그 자체 코드를 보지 않는 한에 있어서
이미 알고 있는 동료에게 힌트를! 많이! 받는게 최선일거같다.
(그리고 동료가 없다면...
뭐 어쩌겠는가 슬쩍 훑어봐라)

꼭 독자적으로 생각해내야한다는 생각에 매일 필요는 없을거같다.
지금 이 일이 아니더라도 독자적으로 생각할 일은 많고 많으며,
생각할 수 있다면 이미 생각 났을 것이다^^

아무튼...

---

이번 프로젝트에서는 먼저
Introduction에서
이런거 저런거 구현해봐야할것이당
고려해봐랑 이러는데

깃북을 전부 읽는건 당연하지만
지금부터 전체 플로우를 다 잡는다는건 외롭고 고난하고
기억도 안 나는 일이므로

Memory management - Anonymous page 를
연계해서 다 하는 걸 처음으로 잡아라.

일단 Project3은 Virtual memory,
기존에 페이지 맵에 적재하기만 하면 바로 물리 주소를 찾을 수 있던 시스템에서 벗어나
실제 va를 적용해서, 처음부터 다 적재하지 않고 '페이지' 만 기록해놓고
그때그때 접근했을 때나 적재하는 방식을 직접 한다!

와우!

듣기만해도 막막하다.

실제 va를 적용 : va가 어디서 오는데?
처음부터 다 적재하지 않고 페이지만 기록 : 페이지가 뭐고(페이지의 개념이야 알겠지만, 페이지가 코드에서 실제로 어떤 식으로 존재하는가?) 어디에 페이지를 어떻게 기록하는데?
그때그때 접근했을 때 : 접근하는 시점이 뭐고 접근시 어디로 접근이 되는데?
적재하는 방식을 직접 : 어떻게 적재를 어디에 하는데?

....

아무튼, 참고해야할 파일은 vm.c. uninit.c , anon.c, file.c, disk.c이다.
hash를 쓴다면 hash.c와 bitmap.c도 자료구조적으로 쓸수 있다.

Memory Management

깃북을 잘 읽도록 하자.
함수 포인터라는 개념을 새로이 쓰며,
page라는 구조체도 설명해준다.

처음으로 구현해야할 것은 여섯 가지 함수다.
(이쯤 되면 자기가 구현할 함수의 갯수도 세게 되지 않게 된다.)

• void supplemental_page_table_init (struct supplemental_page_table *spt);

• struct page *spt_find_page (struct supplemental_page_table *spt, void *va);

• bool spt_insert_page (struct supplemental_page_table spt, struct page page);

• static struct frame *vm_get_frame (void);

• bool vm_do_claim_page (struct page *page);

• bool vm_claim_page (void *va);

뭔소리야.

Implement Supplemental Page Table

supplemental page table을 줄여서 spt라고 하겠다.

구현해야할 것은 세가지다.
spt init, spt find page, spt insert page.

spt를 초기화, spt에서 page 찾기, spt에 page 삽입하기.

아 그럼 구현하면 되지
맞다.

근데 왜 구현하는가?
spt는 무슨 용도고 page는 무슨 용도 인가?

애초에 spt 자체는 그냥 page를 관리하는 리스트다.
말이 리스트지, 어떤 구조체를 하든 상관이 없다는 점이다.

그럼 page의 용도를 알아야겠지?

page는 요런 모양이다.

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

  union {
    struct uninit_page uninit;
    struct anon_page anon;
    struct file_page file;
#ifdef EFILESYS
    struct page_cache page_cache;
#endif
  };
};

나는 이게 진짜 va를 품고 페이지 맵에 사는 어쩌고인줄 알았는데
자세히보면 va 자체를 가진게 아니라 va의 포인터와, frame에 대한 포인터다.

또 union이라는건 여러가지를 정의할 수 있지만 결정하면 한놈만 품는 놈으로
다양한 페이지로 진화할 수 있다는 걸 알수있다.(이브이..)

즉,
실제 주소를 담은 페이지 단위가 아니라,
해당하는 페이지에 대한 정보를 담은 구조체라는 것이다.

spt 자체가
내가 어떠한 page fault를 마주하게 되었을때,
어떠한 page를, 즉 메모리나 정보들을 적재해와야하는지 알기 위해,
참고해야하는 데이터들을 담은, 페이지에 관한 보충 데이터를 담은 구조체를 관리하는 리스트인데,

아니!
그렇다. spt에 들어갈 entry를 따로 만들 필요가 없다.
그냥 이 친구를 쓰면 되는 것이다. 얘가 가진 정보가 이렇지 않은가.

• va : 이 va에 대한 정보를 갖고 있어용
• frame : 이 va에는 요런 frame을 가져용
• union 관련 page : 이 va는 이러한 page에용
• page_operations : 이 va에 관련된 page는 이러한 operation한 요소들을 갖고 있어용(해당하는 페이지에 대한 함수, 부가 데이터 등등.)

와! 다 있다.
그러면 생각해보자....

....
load 시점을 생각해보자.
원래는 load 자체에서 load segement라고
file에 있는걸 open 해서 read byte, zero byte를 계산해서
file read해서 install page니 뭐니로 pml4에 set하고 있을것이다.

근데 우리는 page fault가 일어났을 때나 적재하기로 했으니?
load 시점에는 일단 나중에 적재할겡.... 이라고는 하지만
적재시에 필요한 정보는 page 구조체에 넣어놔야하지 않겠는가?

!! 알았다 그럼 page 구조체에 그것들을 다 넣어놓는거군용!!!!

비슷하게 맞는데 또 약간 다르다
page 구조체에 덕지덕지 read byte 등을 달고 살기도 좀 그렇기도하고
모든 page가 그런게 필요한건 또 아니지 않는가?
얘는 정말 Load 시점.. 태초의.. 짝지어진 file이 있는... 운명이라서 그런거 아닌가?

일단 주요하게 봐야하는건 그거다.
실제 pml4에 set하진 않아도, 관련 정보는 page 구조체에 담아
spt에 쫘라락 리스트업 해놔야한다는 사실.

spt에 넣는것? 간단하다.
당신이 구현할 spt insert 함수가 해줄것이다.
spt에서 찾는것? 간단하다.
당신이 구현할 spt find page 함수가 해줄 것이다.

하지만 page에 적절한 데이터를 넣는것?
그게 중요한 당신의 몫이다.(앞도 당신 몫이긴한데.)

Anonymous page 맛보기

vm_alloc_page_with_initializer

그렇다.
간단하게 생각하면, page는 그냥 구조체다.

구조체를 선언한다면 무조건 init, 초기화를 거쳐야하지 않는가?

그러므로 이 page도 init해준다.
단, 어떻게 진화할 건지 진화의 돌을 포함해서.

• 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. *

todo 를 보라.
page를 create 하시오.
vm type에 따라 initialier를 fetch하고,
uninit_new로 unitinit page를 create하시오.
너는 uninit_new를 부른후 filed를 modify해야할 것이오.

....
page를 만들라는데
page를 만든 후에 uninit으로 또 page를 만들래
얘는 지금 나보고 page를 두번 만들라고하는 거임
말이 됨?
뭐? 아니 연계되는건가 했는데 'and'이면 그리고...잖아.
그걸 한 뒤에 만들라는거잖아

진실은 이렇습니다
만들라 : initialzer를 type에 따라 가져와서, uninit_new를 호출해서 uninit page를 만들라.

영어 실력은 개발 실력에 중요하지않다지만
그럼 이런 document는 어케 읽으라는것인지
(근데 다시 읽고보니 걍 국어도 저런 말인거같기도하고)

뒤에 filed를 고치라는 것도
uninit_new로 갱신되지 않는 원하는 필드가 있다면 고치라는 것이다.

설명을 좀더 길게 써줬다면 초보자는 행복했을텐데
상대가 카이스트라니 이해한다...

그럼 이걸 하기 위해서 알아야하는것

• vm type에 따라 initialzer를 어떻게 다르게 해야하는지 알아내기
• uninit_new가 모에용

...

그리고 단순히 말해서 이렇지,
또 이러한 궁금증도 들것이다.

맨처음에 load segment 함수 자체에 이미 포함되어있는 코드를 보라.

	if (!vm_alloc_page_with_initializer (VM_ANON, upage,
					writable, lazy_load_segment, aux))
                    ...

...
맨처음 init을 VM_ANON으로 한다.
그치만 load 당시에 file 자체를 여니까 이건 VM_FILE은 아닌가?
애초에 VM_FILE과 VM_ANON으로 들어오는 것의 기준은 무엇인가?

...
내 생각엔...
VM_FILE로 지정할 경우와, VM_ANON으로 지정할 경우
동작 방식이 어떻게 달라지는지를 고려해야할 거같다.

VM_FILE로 시작되면 file backed initalizer를,
VM_ANON으로 시작되면 anon_initializer를 타게 된다.

각 initialzer를 타면
각 swap in, out, destroy를 anon, file 방식을 타게된다.

file 방식은 기존에 이미 file이 존재하기때문에
swap out, in 시점시점마다 file을 수정한다.

anon 방식은 file이 따로 존재하지 않기때문에
swap disk에 적어놨다가 불러오는 식으로 한다.

그런데 내가 지금 실행중인 file을
file 방식처럼 swap out 좀 했다고 수정해버리면?
기존 로직과 어떻게 꼬일지 모르는 것이다.
(뇌피셜이다.)

아무튼, 단순히 말하자면,
그래서 내가 진짜 현재 실행중인 main file을 제외하면
file 기반은 file로 구분하고, 아닌건 anon으로 하는게 맞을 것이다...

....
아무튼 이 단계는 딱히 swap in, out도 고려하지 않았으므로
딱히 구별해서 안 가져와도 큰일은 안 난다.

uninit_new는 초기화시키는 매크로에 가깝다.

bool
vm_alloc_page_with_initializer (enum vm_type type, void *upage, bool writable,
		vm_initializer *init, void *aux) {
	struct page *page;

	ASSERT (VM_TYPE(type) != VM_UNINIT)
	struct thread *cur = thread_current();

	struct hash *spt = &cur->spt;
	/* Check wheter the upage is already occupied or not. */
	if (spt_find_page (spt, upage) == NULL) {
		page = (struct page *)malloc(sizeof(struct page));
		if(page == NULL){
			return false;
		}
		switch (VM_TYPE(type))
		{
		case VM_ANON:
			uninit_new(page, upage, init, type,aux,anon_initializer); 
			break;
		case VM_FILE:
			uninit_new(page, upage, init, type,aux,file_backed_initializer);
		default:
			break;
		}
		page->writable = writable;
		page->swap = false;
		/* TODO: Insert the page into the spt. */
		if (!spt_insert_page(spt, page)) {
			return false;
		}
	}
err:
	return false;
}

쫌 특이한것은
init 시키는 함수이기떄문에
이미 spt안에 있는건 init시킬 필요가 없으므로
조건문으로 한번 확인해야하고,

page도 한낱 구조체이기때문에
malloc 시켜줘야하고,

type을 그대로 넣으면
vm_type은 여러가지 type이 섞여있을수 있기때문에
VM_TYPE이라는 매크로를 써야하며,

...이걸 하려면
spt find, insert, init은 당연히 구현되어있어야한다는 것이다!

고로, 이 시점에서
spt init, find, insert로 돌아가자.

spt init

일단 spt를 무슨 구조체로 만들지가 관건이다.
arr로 만든다? 그냥 선언만 하면 끝나겠지.
list로 만든다? init만 하면 되겠지.

여기서 추천하는건 hash다.
hash가 find 자체가 편하기때문.

단, hash는 내가 가진 key에 따라 hash화를 거쳐서
같은 key라면 같은 bucket에 담기때문에
find 자체도 기존에 있는 hash find 등을 써야하며

hash init 자체도
key를 hash화 하는 함수를 넣어야하고,
요소 안에 key끼리 비교하는 함수도 넣어야한다.

헉 내가 hash 화 하는 함수까지?!!?
깃북 appendix hash table 안에 다 적어주셨다.
감사합니다 교수님...

코드 안에는 기존에 supplimental page table이라고 있어서
그 안에 hash를 만든다든가 하는 방법도 있는데
포인터를 어떻게 쓰느냐에 따라 주소 연산자가 꼬이며
hash도 포인터만 넣어준다면 따로 malloc 해주는 등
차이가 갈리므로 헷갈리지 않게 조심하자.

이부분의 hash init, hash func, hash less가 제대로 구현되지 않으면
페이지 폴트가 일어나기 쉽다.

나는 원래 spt 안에 hash 구조체를 넣었다가
그 방법으로는 주소가 살짝씩? 바뀌는게 추정하기 힘들어
그냥 thread 구조체 안에 spt가 있을 자리에
hash spt 식으로 hash형식으로 애초에 넣어주었다.

spt는 전역적이든, process 별이든 상관이 없으나
전역적으로 하는 것에 장점은 다른 것들도 접근이 가능하다는 거지만
다른 process의 page에 접근할 일은 거의 없을테니
아마 지엽적으로 해도 후일 개발에 문제..?는 없...?
을지 모르겠다. 난 참고로 extra인 copy on write는 읽지도 않았으니.

void
spt_hash_init (struct hash *spt UNUSED) {
	hash_init(spt, page_hash, page_less, NULL);
}

uint64_t
page_hash (const struct hash_elem *p_, void *aux UNUSED){

	const struct page *p = hash_entry (p_, struct page, hash_elem);
	return hash_bytes (&p->va, sizeof p->va);
}

bool 
page_less (const struct hash_elem *a_, const struct hash_elem *b_, void *aux UNUSED){
 	const struct page *a = hash_entry (a_, struct page, hash_elem);
  const struct page *b = hash_entry (b_, struct page, hash_elem);

  	return a->va < b->va;
}

struct thread {
...
#ifdef VM
	/* Table for whole virtual memory owned by thread. */
	struct hash spt;
	uintptr_t cur_rsp;
#endif
...

struct page {
	struct hash_elem hash_elem;
    ...
    }

spt find

spt find는 아주 단순해보이지만
그냥 hash find가 해결해줄거같지만
(사실 그 함수를 생각해내는 것마저 나는.....
iterator로 돌면 되는줄알았다^^ 당신은 내장함수 읽으세용)

고려해야할 개념이 있다.

• va는 어느 주소로든 존재할 수 있지만, spt에서는 va를 페이지 단위로 관리한다.
  즉, 'abcde'가 페이지 단위의 정보고, 접근가능 주소가 abcde일때, a자리, b자리, c자리에 접근하자마자 데이터가 있는 게 아니라,
  a 자리에만 abcde 내에 접근할 수 있게 주솟값을 적어놨기때문에,
  내가 b를 가져와 b에 대한 정보를 찾고 싶다면,
  b -> page size 단위로 정렬 -> a로 들어가서
  a위치에서 page size 단위로 복원하며 자연스레 b도 찾을 수 있게 되는 메커니즘이다.
• 따라서, b에 대한 page를 찾으려면 page size 단위로 정렬한 지점, a로 찾아야해서 pg_round_down을 지정해준다.(안해주면 spt find page == NULL로 뜰것이다.)

struct page *
spt_find_page (struct hash *spt, void *va) {
	struct page *page = NULL;
	page = (struct page*)malloc(sizeof(struct page));
	struct hash_elem *e;

	page->va = pg_round_down(va);

	e = hash_find(spt,&page->hash_elem);
    free(page);
	if(e != NULL){
		struct page *found_page =hash_entry(e, struct page, hash_elem);
		return found_page;
	}
	return NULL;

또 그냥 key로 찾는거라
page 구조체 찾기용 find는 malloc 자체를 거칠 필요도 없다고
조교님의 답변이 있었다... 근데아무튼 malloc을 했다면 free해주자 우리
메모리는 소중하니까...

spt insert

hash insert에게 insert해달라고 조른다
끝!

bool
spt_insert_page (struct hash *spt,
		struct page *page) {
	int succ = false;

	if(!hash_insert(spt, &page->hash_elem)){
		succ = true;
	}

	return succ;
}

(참고로 insert 함수에서 제대로 hash를 넣어주었는지
연산자는 잘 맞는지 확인하자.)
(컴파일러는 다른거 넣어줘도 엥.이거맞낭. 하고 넘어가는 경우가 있다.)

Anonymous page

그리하여...
으쌰으쌰 vm alloc initialzer도 했고 거기에 쓰는
spt init, spt insert, spt find도 했다.

이제 테스트?!!?
케이스 안된다.

왜냐하면 page fault시 참조할 추가 데이터만 만들었지
그 추가 테이터를 참조해서 데이터를 실제로 적재하는 과정은
아직이지 않는가?

frame 관련 함수를 만들어야하지 않느냐고?
이게 다 그거랑 관련이 있다. 한번 보자.

...

load -> load segment -> setup stack
루틴을 타면서 initd가 마무리된다.
원래는

load -> load segment -> (install page) -> setup stack인데

이 흐름이 뭐냐면

• load 함수에서 내가 연 file에 대한 byte를 받아서(load)
• 실제로 쓸수 있도록 segment를 load한뒤(load segment)
• load가 끝났으므로 pml4에 업데이트하고(install page)
• thread가 쓸 user stack을 세팅하는 건데(setup stack)

va를 쓴다면 이렇게 된다

• load 함수에서 내가 연 file에 대한 byte를 받아서(load)
• 나중에 쓰도록 업로드할 segment에 관한 정보를 담아 spt에 page 구조체를 저장한뒤(load segment)
• user stack은 일단 바로 쓸수 있게 바로 page 구조체도 가져오고, page 자체도 바로 할당하여(setup stack)

...

• 정말 후일 접근 시점에 페이지 폴트가 뜨면 (page_fault)
• vm관련 pf로 빠졌을때 spt에는 page가 있지만 frame은 없는 경우 등으로 정말 말도 안되는 주소인지 아닌지 구분하여(vm_try_handle_fault)
• 만약 spt에 미리 적재되어있는 거였다면 page를 참조하여 실제 page를 요청한다(vm claim page, vm do claim page)(va로 찾는다면 전자, page로 찾는다면 후자.)

...

요청과정 :

• 1. 그래서 내가 진짜 할당받을 물리메모리에 관한 frame을 가져와서(vm_get_frame)
• 2. page와 frame을 매핑, 즉 pml4를 set한다.(pml4_set_page)
• 3. 최종으로 swap in함수를 호출하는데 대개 이때 내가 init으로 설정해뒀던 함수로 빠진다. (lazy load, 위의 load segment와 비슷한 과정을 거침.)

...

즉 새로운 Load segment, setup stack,
vm try handle fault, vm claim page, vm do claim page,
vm get frame, pml4 set page, lazy load를
(추가로 구현 방식에 따라 page fault도 수정.)

손봐야하는 것이다...

이전에 봤던 frame management 친구인
get frame, do claim, claim이 전부 있다.

anonymous 에선 load segment, lazy load가 다있다.
...^^ 짱!

나는 vm try handle fault 하자마자
init 해야하는줄 알아서 init을 두번 한 별종이 되었으며
개념은 잘 알았으나 함수가 돌아가는 순서를 파악하지 못하였나니
훌쩍훌쩍이로다...(이쯤되면 개념을 잘 알았는지도 의뭉스러움)

뭣보다 page 구조체와
page로 데이터를 직접 claim 한다는 개념 자체가
어려웠더랬지... palloc과 malloc의 차이 호되게 맞고갑니다

이쯤 되면 동적할당과 제법 피와눈물로 친해진거같아요

사담은 이정도로 하고 함수들을 차례대로 살펴보자.

load segment

load segment...
이거 들어오는 인자를 보자.

나중에 쓰도록 업로드할,
segment에 관한 정보를 담아 page 구조체를 init 시키고
그걸 spt에 저장한다.

근데 vm alloc page initializer에
이미 uninit한 뒤 spt insert를 진행하지 않는가?

그러므로 우리가 할건
segment에 관한 정보를 담아
init 하도록 돕는 것이다.

그러려면 load시에 어떤 과정 이루어지는지,
그래서 어떤게 필요한지 확인해야한다!

기존의 load segment를 보자.

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

크게 골자는 이렇다.

• file seek로 ofs 위치로 file 시작 시점 이동.

• read byte, zero byte가 다 소모될때까지, page단위로 file read 할수 있도록 page read byte, page zero byte 계산.

• load할 자리를 확보하기 위해 palloc.

• palloc한 자리에 file read를 page read byte 만큼 진행.

• 남은 자리에 page zero byte 만큼 memset

• install page 함수로 pml4에 set.

  ...

  load 시에 이러한 정보가 필요하다면,
  우리가 넣을 정보도! 뻔하다.

  애초에 page 구조체 자체가 page 단위에 대한 데이터 정보이기 떄문에
  page read byte, page zero byte 만큼 넘겨주되,
  내가 필요한 page 단위 갯수 만큼 page 구조체를 생성하면 되는 것이다!

  그러므로, 필요한 것은 아마 이것일 거다.

• file 관련 함수에 쓰일 file.

• file seek에 쓰일 ofs.

• file read에 쓰일 read byte, memset에 쓰일 zero byte.

  ...그러므로, 이 세가지를 한꺼번에 전달할 구조체를 따로 만들어,
  해당 정보들로 Init 시킨 뒤에,
  vm alloc page with initializer에 aux로 전달해준다!

  물론, 내용이 손상될수 있으니 그 구조체도 malloc 해줘야한다.

  또 고려해야할건, page 단위로 전달하기 때문에,
  upage, offset 등도 계속 갱신해줘야한다는 점이다.

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) {
		size_t page_read_bytes = read_bytes < PGSIZE ? read_bytes : PGSIZE;
		size_t page_zero_bytes = PGSIZE - page_read_bytes;
	
		struct page_load_data *aux = malloc(sizeof(struct page_load_data));
		aux->file = file;
		aux->read_bytes = page_read_bytes;
		aux->zero_bytes = page_zero_bytes;
		aux->ofs = 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;
}

malloc을 안해주면 데이터 손상으로 페이지 폴트나 커널 패닉이 뜰거고(이상한 주소로 갈테니깐...이상한 값으로 하려고하거나. ofs가 주로 손상되는 듯.)

offset을 pg 단위 이동마다 갱신해주면 한줄만 출력되거나..할 것이다.

그럼 계산이야 여기서 해서 load 데이터를 넘겨준다 치고
기존 단계의 palloc과 pml4 set은 어디서 이루어질 것인가?
va를 쓰면 pml4는 안 쓰는 것인가?
정말 궁금할 것이다(아님 말고)

setup stack

기본적으로 process 마다 개별 유저 스택이 있기떄문에 이 과정을 거쳐야한다.

기존 함수를 보면 요런 모양인데..

static bool
setup_stack (struct intr_frame *if_) {
	uint8_t *kpage;
	bool success = false;

	kpage = palloc_get_page (PAL_USER | PAL_ZERO);
	if (kpage != NULL) {
		success = install_page (((uint8_t *) USER_STACK) - PGSIZE, kpage, true);
		if (success)
			if_->rsp = USER_STACK;
		else
			palloc_free_page (kpage);
	}
	return success;
}

palloc 해서 USER 풀에 ZERO화 시켜 받아와가지고
잘 받아왔다면 pml4에 set하는 install page를 진행 후
rsp를 USER_STACK 에 달아놓는다..

그리고 자세히 보면 install page라는게
내가 palloc으로 받아온 자리에 USERSTACK에서 PGSIZE 차이나는 지점에 pml4를 set한다.

대체 pml4 set이 뭔가? 의문이 들것이다...
page와 frame이 진짜 이어졌다고 혼인계약서를 올리는 작업으로
Pml4에 혼인 신고서를 등재하는 과정..
단순히 말하자면 매핑 확정 신고다.

즉 그냥 palloc으로 frame을 받아와서
내가 넣으려는 va, USER STACK에서 PGSIZE만큼 차이 나는 지점의 va를
매핑해주는 것뿐인 것이다.

그러면 우리가 va 식으로 한다면?

간단하다.
(사실 떠올리는건 전혀 안 간단하다.)

spt에 page를 꼭 넣는게 우리의 룰이니
원래의 도식대로
page 구조체를 init한 다음
그 page 구조체에 따라 claim하는 것이다!

그리고, 분명 claim이 잘 끝났다면 PGSIZE만큼 alloc 되었을 테니
rsp를 원하는 목표지점으로 옮겨주자.

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

	if(vm_alloc_page(VM_ANON |VM_MARKER_0, stack_bottom, true)){
		if(vm_claim_page(stack_bottom)){
			if_->rsp = USER_STACK;
			success = true;
		}
	}

	return success;
}

VM_MARKER_0은 stack임을 알리기 위해 넣는 부분이다.
반대로 저걸 찾아낼 수 있다면 stack 지점인 것을 알수 있겠지...

하지만!

우리는 claim page를 구현하지 않았다.
(vm_alloc_page는 달라보이지만 그냥 vm_alloc_page with initializer를 매크로화 식으로 실행시키는 거라 같다.)

claim page를 보자...

vm claim page

왜 claim과 do claim이 나뉘어있는지 궁금할 것이다.
나도 궁금했는데 차이점은 page를 받느냐, va를 받느냐, 라는 점에서

claim page는 va로 받으니,
애초에 va에 해당하는 page가 있는지만 확인하고
같은 기능을 하는 do claim으로 넘기면 되겠지?

그래서 spt find만 수행한다.
(va만 있어도 claim이 가능하도록 일종의 편의..에 가까울듯 하다.)

vm_claim_page (void *va) {
	struct page *page = NULL;
	struct thread *cur = thread_current();
	page = spt_find_page(&cur->spt, va);
	if(page == NULL){
		return false;
	}
	return vm_do_claim_page (page);
}

vm do claim page

대망의 do claim!
위에 내용이 기억나는가?

내가 만든 page 구조체에 따라
해당하는 frame을 가져와서 매핑 시켜주는 놈이다.

그렇다! 감이 오는가?
여기서 pml4 set을 해준다.

pml4가 뭐길래 vm에서도 set해주는가? 궁금할수 있는데
pml4는 vm 시스템이든 뭐든 아무튼 페이지 맵으로서
실제 매핑된 테이블이기때문에 최종적으로 확정되었다면 여기에 등재해줘야한다.

앞서 page는 찾아주었으니,
적합한 frame을 가져와서 둘을 이어줘야겠지...

...
근데 frame이라는게 그렇게 page의 타입따라 달라지는 놈이 아니다.
그냥 일종의 palloc처럼 자리만 있는 아무 놈을 가져오면 되기때문에
vm get frame으로 frame을 가져와 서로의 포인터를 갱신해주고
set을 진행해준다.

중간의 lock이나 list push back은 무시하자.
지금 관련있는 부분은 아니다.

vm_do_claim_page (struct page *page) {
	struct frame *frame = vm_get_frame ();
	frame->page = page;
	page->frame = frame;
	
	struct thread *cur = thread_current();
	lock_acquire(&swap_lock);
	list_push_back(&swap, &(frame->frame_elem));
	lock_release(&swap_lock);

	if(!pml4_set_page(cur->pml4, page->va, frame->kva, page->writable)){
		return false;
	}
    
	return swap_in (page, frame->kva);
}

swap in 매크로도 분명 page의 operaion내에 swap in 함수를 호출하는거같은데 init으로 설정해줬던 lazy load로 빠진다. 모른다. 알게되면 나중에라도 궁금하니 덧글을 달아달라.
(진작 조교님에게 질문할걸.)

vm_get_frame

아무튼 그렇다면 frame은 어떻게 가져오는가?
이거 다른 사람 코드로 완전히 변모한건 이해해달라.(출처가 기억이 안난다.)
나도 절박했다.

(근데 되지도않았다 난 ....운다
이 코드라서 안된건 아니고, swap 관련 함수를
늘 다른 사람 코드로 다 탈바꿈했지만 늘 같은 에러가 걸려
그냥 아무 코드로 고정한 모습이다.)

static struct frame *
vm_get_frame (void) {
	struct frame *frame = NULL;
    
	void *pg_ptr = palloc_get_page(PAL_USER);
	if (pg_ptr == NULL)
	{
		return vm_evict_frame();
	}

	frame = (struct frame *)malloc(sizeof(struct frame));
	frame->kva = pg_ptr;
	frame->page = NULL;

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

이 단계에서 evict frame은 구현도 안 되어 할필요가 없고
PANIC("todo!")로 넣어두면 나중에 구현할 부분으로 panic이 빠지니 냅두자.

간단히 말하자면,
palloc을 해온뒤 그에 1대1 대응할 frame 구조체도 malloc 해주어
서로 딴다딴 이어준뒤 frame을 반환한다.

(사실, 결과적으로 아까 palloc과정이
frame을 추가로 끼고 있을 뿐 여기에 있는 것이다!)

그렇구나! pml4 set은 do claim에,
palloc은 get frame에 있었다...!

아무튼, 여기까지하면
initd에서 실패는 안 뜨지만

page fault가 실제로 발생하여
직접 적재하는 과정은 아직 덜 구현했다. 계속 하자!

page_fault

page fault 시점에서,
아마 VM 용으로 이렇게 ifdef로 빠질 것이다.

exit(-1)을 project2 케이스에서
어디에 옮겨놨는지는 모르지만,

여기서 진행한다면 아무튼 vm try handle fault 아래로는 이동해두자.
(만약 뭘 하기도 전에 exit(-1)로 죽는다면 높은 확률로 이 문제다.)

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)){
		//printf("vm try handl fault fail!\n");
		return;}

#endif
	exit(-1);
    ...
    }

vm_try_handle_fault

vm try handle fault를 보자.

여기에 들어오는 인자를 유심히 봐놓도록 하자.
intr frame, addr, user, write, not present...
나중에 하나도 안 쓰는게 없다!

아무튼, 여기서 해주는 건
정말 말도 안되는 addr 등은 죽이지만,

그 외는 spt find page에서 해당하는 addr에
대응하는 page 구조체를 찾아서(spt find page)
do claim page를 진행한다.

(만약 va에 맞는 page가 없다면 애초에 내정된 애가 아니니까
당연히 죽이고 말이다!)(page == NULL!)

writable은 initializer 때 잘 계승했다면
(물론 page 구조체에 추가해놔야되었겠지만..)
고려하는 것은 어렵지 않을 것이다.

여기서 not present 를 쓰는게 좀 생경할 건데
연결된 frame이 없다는걸 알아서 인지하는 인자...
애초에 인지해서 넘어오는 인자인데

어디서 오는지 모른다
나는 그냥 썼다 사실 쓰는 법도 몰랐다
다른 사람 코드가 세련되게 쓰길래 가져왔다
(나는 이전에는 frame은 null이라든지로 체크하려고 노력했다..)

bool
vm_try_handle_fault (struct intr_frame *f, void *addr,
		bool user, bool write, bool not_present) {
	struct hash *spt = &thread_current ()->spt;

	struct page *page = NULL;
    
	if(addr == NULL){
		return false;
	}
	if(is_kernel_vaddr(addr)){
		return false;
	}


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

나는 이 진상을 알았을 때 굉장히 허탈했다
여기서 헉...
page fault에서 빠졌다고..??
그럼 page에 데이터 가져오려면
해당하는 va로 page 만들어서
데이터 가져..와야겠네?? 하고
addr로 page init하려고 했으니까..

큰 개념과 플로우는 알지만
슬프도록 착각한 모습이다...

나는 load 당시에 page fault가 나는줄 알았으니
아무튼 알았지만 전혀 몰랐다는 것에 가깝다..

어! 우리는 근데 do claim page는 했다.
그러면!
최종의 최종.

실제 do claim page 후 swap in으로 안 빠지고
init 함수로 빠지며 시작되는
lazy load segment를 확인해보자.

lazy load segment

근데 말이 lazy라
그냥 그때그때 할당,
즉 도착한 시점에 load 하기때문에 lazy일뿐

실제 본인 함수는 부지런하게 page에
page와 연결된 frame kva에 열심히 적재한다.

우리가 앞서 load segment에 넘겨줬던 파일 정보와,
실제 적재했던 과정이 기억이 나는가?

그거다!

그 aux에 넣어놨던 파일 정보를 꺼내서
file seek, file read, memset을 진행해준다.

bool
lazy_load_segment (struct page *page, void *aux) {

	struct page_load_data *aux_d = (struct page_load_data *)aux;
	file_seek(aux_d->file, aux_d->ofs);

	if(file_read(aux_d->file, page->frame->kva, aux_d->read_bytes) != (int)aux_d->read_bytes){
		palloc_free_page(page->frame->kva);
		return false;
	}

	memset((page->frame->kva)+(aux_d->read_bytes), 0, aux_d->zero_bytes);

	return true;

...
휴!
initd가 방금 끝났다.
(아마도.)

그렇지만 fork 전반이 안될것이다.
(물론 그 외에도 숱한게 안될수 있다. 파이팅.)

그러기 위해서는
fork 과정에서 pte를 열심히 복사했던 눈물 겨운 그 과정을
물론 spt에 있는 page도 복사해줘야한다.
page가 적재되었느냐에 따라 적재도 진행을 해야한다...

그러므로,

spt copy,
spt kill을 구현해야하는데,
kill 당시 쓰일 page에 따른 destroy,
즉 uninit destoy도, anon destroy도 필요하다면 수정해야한다.

갈..
길이 멀다...

spt hash copy

...
나는 spt에서 page를 맨처음 가져올때
그렇다고 생각했어

hash iterator로
끝까지 도는데...

page를 그래서 hash entry로 꺼내오면
그거 어차피 type 다 있을거 아냐?

그걸로 Uninit_new로 싹! 해주면
(type에 따라 initializer는 따로해주고)

끝나는 거 아냐?
라고 생각했다....

근데 생각이 짧았던게

아.. 나 잠깐 모르겠어

아... 이제 알겠어
initializer에서 uninit_new만 선언한 시점에서
아직 type은 uninit_new만 거쳐서 VM_UNINIT 되어있고
claim은 안 된 애랑

page fault를 맞이해서
claim page까지 도달한 애랑 따로 있을테니

VM_TYPE으로 분류를 해서
전자는 vm alloc initilaizer만 진행하고,
후자는 그것도 하되 claim page도 하고,

claim page는 단순히 frame만 가져와서 set 하는 애니까
(물론 그게 끝난후에 init 함수로 빠져서 적재되어야 맞지만)
첫번째 page fault에서만 Init이 빠지니 이미 page fault가
일어난 거나 다름 없는 그 page는 내가 순수 적재해줘야하기때문에

일일이 하지 않고 부모 page frame kva에 있는걸
memcpy로 인터셉트를 한다...

bool
spt_hash_copy (struct hash *dst UNUSED,
		struct hash *src UNUSED) {
	struct hash_iterator i;
	hash_first(&i, src);
	while(hash_next(&i)){
		struct page *p = hash_entry(hash_cur(&i), struct page, hash_elem);
		switch (VM_TYPE(p->operations->type))
		{
		case VM_UNINIT:
			if(!vm_alloc_page_with_initializer(p->uninit.type, p->va, p->writable, p->uninit.init,p->uninit.aux)){
				return false;
			}
			break;
		default:
			if(vm_alloc_page(p->operations->type, p->va, p->writable)){
				if(!vm_claim_page(p->va)){
					return false;
				}
			}
			break;
		}
		if(p->operations->type != VM_UNINIT){
			struct page *k;
			k = spt_find_page(dst, p->va);
			memcpy(k->frame->kva, p->frame->kva, PGSIZE);

		}
	}
	return true;

}

.. 그렇다.

spt hash kill

...
나는 spt를 일일이 돌면서
(hash니까 iterator로..)
page를 찾아
destroy를 돌리면 되지 않을까 했었다...

솔직히 안 될 이유는 없다고 생각되지만
hash_clear 함수를 써서해준다...
(그러니 내장 함수를 잘 읽어야한다.)

(hash clear 함수 내에서는,
맨 위에 있는 bucket list를 꺼내서,
hash를 하나씩 꺼내서,
그걸 일일이 지워주는데....

만약 이걸 해야한다면
spt copy 에서는 왜 iterator만으로 가능하단 말인가?
궁금하다...)

뭐 그걸 제외하고서라도, clear 함수를 쓰는게 코드는 훨씬 간단하다.

void
spt_hash_kill (struct hash *spt UNUSED) {
	hash_clear(spt, page_entry_destroy);
}

void
page_entry_destroy(struct hash_elem *e, void *aux){
	struct page *p = hash_entry(e, struct page, hash_elem);
	destroy(p);
	free(p);
}

여기까지 하면 project2 부분 까지는 다 된다고 한다!