2022.12.01 SW정글 74일차 / Annonymous Page, Stack Growth 연습장

2022. 12. 2. 03:06카테고리 없음

1) supplemental_page_table 구조체 수정

➡️ struct hash spt_hash 추가하기

 

2) supplemental_page_init 완성 ➡️ 해쉬를 init해줌

➡️ hash_init을 넣어줌

 ( spt의 spt_hash, page_hash 함수, page_less 함수, aux는  NULL) 

 

3) spt_find_page 완성 ➡️ spt에서 해당 va를 가지고 있는 elem을 찾아서 그에 맞는 page를 반환하는 함수

➡️ - malloc을 통해서 page를 만들어준다.

    - va를 page에 이어준다.

    - hash_find를 통해서 spt안에 있는 spt_hash 안에서 hash_elem을 찾아준다.

    - page를 만든 것은 dummy이므로, 다 사용했으면 토사구팽 시켜준다 => free

    - 성공하면, e를 반환하는데 return값은 page 이기 때문에 hash_entry를 써서 반환한다.

 

4) spt_insert_page 구현 ➡️ spt_hash에 해당 page를 넣어주는 함수

➡️ - insert_page라는 함수를 사용한다 (새로 만듦)

     - 우리는 hash_insert를 사용하자

 

5) struct frame 만들어주기 ➡️ frame은 물리메모리 안에 있는 단위로, 가상메모리의 page와 allinged되어 있음

➡️ - kva ( 물리 메모리를 직접 참조는 어렵다 그래서 커널영역에 가상주소를 매핑해준다)

    - page 

    - frame_elem

 

6) frame_table 만들어주기 (list)

➡️ 전역으로 미리 설정을 해준다.

 

7) vm_get_frame 구현 - 물리메모리에 있는 frame 하나 (남는 것 혹은 evict 시키고 얻은 것) 을 반환해주는 함수

➡️ - 일단 malloc을 통해서 frame 하나에 해당하는 메모리를 할당해줌

    - palloc_get_page를 통해서 (from user pool) 가상주소를 받은 다음에 frame의 kva로 연결해줌

   - 하지만 kva가 존재하지 않을 수도 있음 (이유는 user_pool에서보면 남는 공간 (page) 가 꽉차서 그렇다! = 줄 곳이 없다)

      👉 이럴 경우에는 쫓아내야 한다 = vm_evict_frame() / frame의 page를 NULL로 만든다.

   - 그다음에는 frame table에 새로운 frame (elem으로) 을 넣어줌

      👉 쓰레기값이 들어있을 수도 있으니까 frame의 page를 NULL로 만든다.

static struct frame *
vm_get_frame (void) {
	struct frame *frame = NULL;
	/* TODO: Fill this function. */

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

8) vm_evict_frame구현 - frame에서 swap_out을 시켜주는 함수 

➡️ - 첫번째로 victim을 선정해줌 => vm_get_victim();

     - 그 후에, 해당 victim의 page를 swap_out 함수를 통해서 쫓아냄

     - 쫓아낸 victim (즉, page)을 리턴해줌

 

9) start라는 list_elem을 전역변수로 설정해주기 

➡️ 이유 : 8번에서 쫓아낸 victim을 어딘가에서 기억하고 있어야 하는데, 그래서 victim을 start로 저장을 하고 있기

              (예를 들어서 시계가 돌다가 3시 방향에서 한놈을 evict했다면, 그 시계바늘은 다음에 돌 때, 3시부터 돌아야되기 때문에

                3시를 기억하고 있는 것이다. )

 

10) vm_get_victim 구현 - (일단 clock-algorithm으로 구현함)

➡️ - start 변수를 loop를 돌려서, pml4_is_accessed 함수를 통해서 최근에 acccess 되었는지(true)? 안 되었는지(false)? 확인을 한 후,

    - true라면, pml4_set_accessed를 통해서, false로 바꿔준다 -> 이렇게 하면 다음 시계바늘이 혹시라도 돌게 되면 false로 반환이 될 것이기 때문이다!

   - 그래서, 만약에 false가 나오면 그 놈이 victim 이다.

   - 먄약에 모든 elem이 다 true였다면, evict를 하지 못했기 때문에, 한바퀴를 더 돌아야 하므로, loop를 하나 더 써줌

     ( 예를 들어서 12시부터 시작해서 한바퀴 다 돌았는데 evict를 못 했다면, 다음 12시 부분의 처음 놈이 무조건 evict 됨)

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

	return victim;
}

 

10) vm_claim_page 구현 - vm_do_claim_page를 하기 위해서 처음 호출 되는 최초 함수일 뿐임 (왜냐면 parameter가 va 이므로, page를 받아줘야 함) 

➡️ - spt_find_page()를 통해서 spt 안에서 va에 해당하는 page를 리턴함

     - 그 page를 기억해놨다가 vm_do_claim_page에 인자로 넣어주면 됨

 

11) vm_do_claim_page 구현 - 인자로 넣어준 page와 물리메모리에서 가져온 frame을 연결해줌

➡️ - vm_get_frame을 통해서 일단 물리메모리에서 frame을 가져와 준다.

     - frame의 page가 인자로 넣어준 page가 되어야 하고

     - page의 frame이 곧 받아온 frame이 되는 것임

     - 여기에서 그치지 않고 page table에서 key와 value를 심어줘야함

     - 그래서 pml4_get_page를 통해서 원래 있던 정보인지 확인 하고 (원래 있으면 할 필요 없음)

      - pml4_set_page를  통해서 심는 작업을 함

      - 그런데 install_page라는 함수에는 두 개가 다 있음 (편하게 하려면 install_page 사용)

       // 여기에서 writable은 page의 writable을 말함 //

 

12) vm_alloc_page_with_initializer() 수정 - 페이지를 alloc 해주고 vm_type에 따라 적절한 initialize를 골라서 uninit_new를 호출해주는 함수 ( page를 init을 해주는 함수 )

: load_segment()에서 호출됨

핀토스 실행  ➡️ 부팅완료(vm 초기화 완료) ➡️ main 프로그램 실행 ➡️ .... ➡️ process_exec() 에서 load() 실행 ➡️ load() 안에서 load_segment() 실행

 

➡️ - malloc으로 페이지크기 만큼 할당 받아 page를 정의해주기

    - switch 문에서 type에 따라서 initializer를 anon / file_backed 로 설정해주기 (이 initialize는 uninit_new에서 쓰이게 됨)

    - uninit_new() 를 통해서 정보를 새로 만든 페이지에 넣어주기

    - page의 writable도 설정해주기

    - 그 페이지를 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)

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

		/* TODO: Insert the page into the spt. */
	}
err:
	return false;
}

 

13) uninit_new() 

(1) load_segment() - vm_alloc_page_with_initializer()에서 실행 (이 때에는 lazy_load_segment) ,

(2) setup_stack() - vm_alloc_page()에서 실행

➡️ - page 구조체를 채워주는 함수

 

14) lazy_load_segment()

- vm_alloc_page_with_initializer에서 보조함수(4번째 인자)로 받아서, page fault 발생 시 실행됨 (initializer 역할)

➡️ - aux로 받는 struct 만들어주기 ( file / offset / page_read_bytes) 

    - 받은 aux를 통해서 변수로 정의해주기 (file 구조체에서 각각 멤버의 값을 받은 인자를 활용해서 넣음)

    - file_seek() 함수를 통해서 file->pos를 업데이트해주기 (이유 : file_read()에서 쓰이게 됨)

    - file_read를 통해서 스택 페이지에 올려주기 - load (먄약에  read_byte 만큼  안 올렸다면 false)

    - memset으로 zero-byte부분 채워주기

static bool
lazy_load_segment (struct page *page, void *aux) {
	/* TODO: Load the segment from the file */
	load_segment(file, offset, upage, read_bytes, zero_bytes, writable)
	/* TODO: This called when the first page fault occurs on address VA. */
	/* TODO: VA is available when calling this function. */
}

 

15) load_segment()

- lazy_load_segment()에 들어갈 세그먼트들을 구조체에 저장해줌

➡️ - struct를 정의해주고 할당해주기 (malloc 사용)

     - struct에 인자들을 저장해주기 (나중에 lazy_load_segment()에 전달해줘야됨)

     - ofs에 page_read_bytes 를 더해주기

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. */
		void *aux = NULL;
		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;
	}
	return true;
}

 

16) setup_stack() - 유저 스택 공간을 할당해줌 (if->rsp를 위치시켜줌)

➡️ anon_page로 변할 uninit page를 stack_bottom 위로 1 page 만큼 만들어줌 (vm_alloc_page)

➡️ 이 때, VM_MARKER_0을 활용하여 이 page가 stack임을 표시함 ( VM_ANON 포함 )

➡️ stack_bottom을 현재 thread에 저장해야되므로, thread 구조체에 추가

stack은 disk와 무관하기 때문에 lazy load할 필요가 없으니까 init에 NULL을 넣어줌

 

<수정 전 코드>

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

	/* TODO: Map the stack on stack_bottom and claim the page immediately.
	 * TODO: If success, set the rsp accordingly.
	 * TODO: You should mark the page is stack. */
	/* TODO: Your code goes here */

	return success;
}

 

17) vm_try_handle_fault() 수정 - page fault 발생 시, faulted address에 해당하는 page struct를 해결

➡️  - addr이 유저영역 가상 메모리 안의 페이지가 아니라면 끝내버리기 (false 리턴)

     - 유저스택의 포인터를 가져오기 

        (1) 인터럽트 프레임 f의 rsp가 유저영역에 없다면 (커널 영역에 있다면) 현재스레드에 있는 rsp_stack 사용

        (2) 아니라면 주어진 f의 rsp를 사용 

     - 페이지의 present bit 값이 false 이면 (메모리 상에 존재하지 않으면) 프레임과 메모리를 매핑함 (vm_claim_page)

     - addr이 rsp_stack - 8 보다 위에 있고, 유저스택 - 1M 보다 위에 있고, 유저스택보다 아래에 있으면 

          vm_stack_growth 실행

 

<수정 전 코드>

vm_try_handle_fault (struct intr_frame *f UNUSED, void *addr UNUSED,
		bool user UNUSED, bool write UNUSED, bool not_present UNUSED) {
	struct supplemental_page_table *spt UNUSED = &thread_current ()->spt;
	struct page *page = NULL;
	/* TODO: Validate the fault */
	/* TODO: Your code goes here */

	return vm_do_claim_page (page);
}

 

18) check_address() 수정 - 기존에는 rsp 값으로 check_address를 진행했었는데, 방식이 바뀌었기 때문에 수정해줌

➡️  - addr이 유저영역에 없다면 exit(-1)

     - 있다면 spt_find_page를 해서 page를 반환해줌

 

19) check_valid_buffer() 새로 만들기 - read, write를 진행할 때, buffer가 유효한지 체크해줘야하기 때문

➡️  - loop문을 돌면서 buffer 한 바이트마다 유효한지 체크 (size 만큼 돌아줌)

     - 만약 page가 NULL이라면 exit (-1)

     - to_write가 true인데 읽기전용페이지라면 exit(-1)

     - syscall_handler로 가서, 해당 함수를 넣어줌

 

20) anon_page struct에 swap_index를 추가해주기 (int)

 

21) anon_initializer 함수 수정해주기

➡️  - 주어진 page에서 uninit을 0으로 memset 해줌 (초기화)

     - 주어진 page의 operations를 anon_ops로 설정해줌

     -주어진 page의 anon의 swap_index를 -1로 설정해줌

 

<수정 전 코드>

bool
anon_initializer (struct page *page, enum vm_type type, void *kva) {
	/* Set up the handler */
	page->operations = &anon_ops;

	struct anon_page *anon_page = &page->anon;
}

 

22) supplemental_page_table_copy 함수 수정해주기

➡️  - hash_iterator i를 하나 설정해주고 src의 pages를 연동하기 (hash_first)

     - 

 

<수정 전 코드>

bool
supplemental_page_table_copy (struct supplemental_page_table *dst UNUSED,
		struct supplemental_page_table *src UNUSED) {
}

 

 

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

커널이 새 페이지의 request를 받으면 

vm_alloc_page_with_initializer가 호출됨

➡️ 인자로 받은 페이지 타입에 맞게 새 페이지를 초기화하여 다시 유저프로그램으로 제어권을 넘김

 

유저프로그램이 실행될 때, page fault가 발생됨 

이유는 페이지와 프레임 간의 연결이 성사되지 않았기 때문임

 

이에 따라 uninit_initialize가 발동할 때, 위의 initializer가 호출됨

➡️ 각 페이지 유형에 맞게 다른 initializer를 호출

 

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

해야할 일 ??

 

1) vm_init() 수정 - 부팅이 시작될 때 호출되는 함수

➡️ 프레임 테이블 list_init 해주기 

(프레임테이블을 여기에서 먼저 만들어준다)

 

<수정 전 코드>

void vm_init(void)
{
	vm_anon_init(); // swapdisk 셋업
	vm_file_init(); // file vm initialize
#ifdef EFILESYS /* For project 4 */
	pagecache_init();
#endif
	register_inspect_intr();
	/* DO NOT MODIFY UPPER LINES. */
	/* TODO: Your code goes here. */
}

 

2) vm_alloc_page_with_initializer() 수정 - 페이지를 alloc 해주고 init까지 해주는 함수

: load_segment()에서 호출됨

핀토스 실행  ➡️ 부팅완료(vm 초기화 완료) ➡️ main 프로그램 실행 ➡️ .... ➡️ process_exec() 에서 load() 실행 ➡️ load() 안에서 load_segment() 실행

 

➡️ 1)malloc으로 페이지크기 만큼 할당 받기

2) switch 문에 따라서 initializer를 anon / file 로 설정해주기

3) uninit_new() 를 통해서 정보를 새로 만든 페이지에 넣어주기

4) 그 페이지를 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)

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

		/* TODO: Insert the page into the spt. */
	}
err:
	return false;
}

 

3) uninit_initialize() - page fault 발생 후에 unint type의 페이지를 swap-in하고 type을 변환시켜주는 함수

➡️ 한번 살펴보기

➡️ page fault handler: page_fault() 

                   

 :  각 타입에 맞는 initializer()와 vm_init() 호출

 

<수정 전 코드>

static bool
uninit_initialize(struct page *page, void *kva)
{
	struct uninit_page *uninit = &page->uninit;

	/* Fetch first, page_initialize may overwrite the values */
	vm_initializer *init = uninit->init;
	void *aux = uninit->aux;

	/* TODO: You may need to fix this function. */
	return uninit->page_initializer(page, uninit->type, kva) &&
		   (init ? init(page, aux) : true);
}

 

4) setup_stack() - 유저 스택 공간을 할당해줌 (if->rsp를 위치시켜줌)

➡️ anon_page로 변할 uninit page를 stack_bottom 위로 1 page 만큼 만들어줌 (vm_alloc_page)

➡️ 이 때, VM_MARKER_0을 활용하여 이 page가 stack임을 표시함

➡️ stack_bottom을 thread에 저장해야되므로, thread 구조체에 추가

stack은 disk와 무관하기 때문에 lazy load할 필요가 없으니까 init에 NULL을 넣어줌

 

<수정 전 코드>

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

5) lazy_load_segment()

- vm_alloc_page_with_initializer에서 보조함수로 받아서, page fault 발생 시 실행됨 (initializer 역할)

➡️ aux로 받는 struct 만들어주기 ( file, offset, page_read_bytes) 

➡️ 받은 aux를 통해서 변수로 정의해주기 ( file_read 통해서 load 진행해주기)

➡️ zero-byte 부분 잊지 말고 실행해주기 (0으로 만들기 = memset)

 

static bool
lazy_load_segment (struct page *page, void *aux) {
	/* TODO: Load the segment from the file */
	load_segment(file, offset, upage, read_bytes, zero_bytes, writable)
	/* TODO: This called when the first page fault occurs on address VA. */
	/* TODO: VA is available when calling this function. */
}

 

6) load_segment()

- lazy_load_segment()에 들어갈 세그먼트들을 구조체에 저장해줌

➡️ struct를 정의해주고 할당해주기

➡️ struct에 인자들을 저장해주기 (나중에 lazy_load_segment()에 전달해줘야됨)

 

 

8) vm_try_handle_fault() 수정 - page fault 발생 시, faulted address에 해당하는 page struct를 해결

➡️ addr이 커널이 아닌지 확인

➡️ 

bool vm_try_handle_fault(struct intr_frame *f UNUSED, void *addr UNUSED,
						 bool user UNUSED, bool write UNUSED, bool not_present UNUSED)
{
	struct supplemental_page_table *spt UNUSED = &thread_current()->spt;
	struct page *page = NULL;
	/* TODO: Validate the fault */
	/* TODO: Your code goes here */

	return vm_do_claim_page(page);
}