[PintOS - VM] Anonymous Page

 

파일 기반이 아닌, 익명 페이지를 구현해야 한다!

 

Page Initialization with Lazy Loading

• 지연 로드 개념
  • 메모리 로드를 필요한 시점까지 미루는 설계 방식입니다.
  • 페이지는 할당되었지만, 실제 물리적 프레임이나 콘텐츠는 아직 로드되지 않은 상태입니다.
  • 페이지 폴트가 발생할 때 콘텐츠가 로드됩니다.
• 페이지 초기화 흐름
  • vm_alloc_page_with_initializer 호출: 커널이 새로운 페이지 요청을 받을 때 호출됩니다.
    • 페이지 구조체를 할당하고 페이지 타입에 따라 적절한 초기화자를 설정합니다.
    • 사용자 프로그램으로 제어를 반환합니다.
  • 페이지 폴트 발생: 프로그램이 콘텐츠가 아직 로드되지 않은 페이지에 접근을 시도할 때 발생합니다.
  • uninit_initialize 호출: 페이지 폴트 처리 과정에서 호출됩니다.
    • 초기화자가 호출됩니다 (anon_initializer 또는 file_backed_initializer).
• 페이지 생명 주기
  • 초기화 -> (페이지 폴트 -> 지연 로드 -> 스왑 인 -> 스왑 아웃 -> ...) -> 소멸
  • 각 전이 단계는 페이지 타입(VM_TYPE)에 따라 필요한 절차가 다릅니다.
• 구현해야 할 주요 전이 과정
  • 초기화: vm_alloc_page_with_initializer와 uninit_initialize를 통해 구현됩니다.
    • 익명 페이지: anon_initializer
    • 파일 기반 페이지: file_backed_initializer
  • 페이지 폴트 처리: 지연 로드 및 스왑 인/아웃 처리입니다.
    • 페이지가 필요할 때 콘텐츠를 로드합니다.
  • 스왑 인/아웃: 페이지를 디스크로 스왑 아웃하고 다시 메모리로 스왑 인합니다.
    • 각 페이지 타입에 따라 스왑 처리가 다릅니다.
  • 페이지 소멸: 페이지가 더 이상 필요하지 않을 때 메모리를 해제합니다.

 

 

Lazy Loading for Executable

 

• 지연 로드 개념
  • 프로세스가 실행을 시작할 때, 즉시 필요한 메모리 부분만 주 메모리에 로드합니다.
  • 이는 모든 바이너리 이미지를 한 번에 메모리에 로드하는 eager loading 방식보다 오버헤드를 줄일 수 있습니다.
• VM_UNINIT 페이지 타입
  • include/vm/vm.h 파일에 VM_UNINIT 페이지 타입을 정의합니다.
  • 모든 페이지는 처음에 VM_UNINIT 페이지로 생성됩니다.
  • include/vm/uninit.h 파일에 미초기화 페이지를 위한 struct uninit_page 구조체를 제공합니다.
  • 미초기화 페이지를 생성, 초기화 및 소멸시키는 함수들은 include/vm/uninit.c 파일에서 찾을 수 있습니다.
  • 이러한 함수들을 나중에 완성해야 합니다.
• 페이지 폴트 처리
  • 페이지 폴트가 발생하면, 페이지 폴트 핸들러(userprog/exception.c의 page_fault)가 제어를 vm/vm.c의 vm_try_handle_fault로 전달합니다.
  • vm_try_handle_fault는 먼저 유효한 페이지 폴트인지 확인합니다. 유효한 페이지 폴트란 잘못된 접근을 의미합니다.
  • 만약 유효하지 않은 폴트(bogus fault)라면, 페이지에 일부 콘텐츠를 로드하고 사용자 프로그램으로 제어를 반환합니다.
• 유효하지 않은 페이지 폴트의 세 가지 경우
  • 지연 로드된 페이지 (lazy-loaded)
  • 스왑 아웃된 페이지 (swapped-out)
  • 쓰기 보호된 페이지 (Copy-on-Write)
  현재는 첫 번째 경우, 즉 지연 로드된 페이지만 고려합니다.
• 지연 로드된 페이지의 페이지 폴트 처리
  • 지연 로드된 페이지의 페이지 폴트가 발생하면, 커널은 vm_alloc_page_with_initializer에서 설정한 초기화자 중 하나를 호출하여 세그먼트를 지연 로드합니다.
  • userprog/process.c 파일에서 lazy_load_segment를 구현해야 합니다.
• vm_alloc_page_with_initializer() 구현
  • 전달된 vm_type에 따라 적절한 초기화자를 선택해야 합니다.
  • 선택한 initializer를 uninit_new 함수와 함께 호출합니다.

 

 

 

1) vm_alloc_page_with_initializer()

bool vm_alloc_page_with_initializer (enum vm_type type, void *va,
        bool writable, vm_initializer *init, void *aux);

 

 

1. 미초기화 페이지 생성
   • 주어진 타입을 사용하여 uninit 페이지를 생성합니다.
   • uninit 페이지의 swap_in 핸들러는 페이지를 타입에 따라 자동으로 초기화하고, 주어진 INIT 함수와 AUX를 호출합니다.
   • 페이지 구조체를 생성한 후, 이를 프로세스의 SPT에 삽입합니다.
   • vm.h에 정의된 VM_TYPE 매크로를 사용하면 유용합니다.
2. 페이지 폴트 처리 흐름
   • 페이지 폴트 핸들러는 호출 체인을 따라가며, swap_in을 호출할 때 최종적으로 uninit_initialize에 도달합니다.
   • uninit_initialize의 완전한 구현을 제공하지만, 설계에 따라 수정이 필요할 수 있습니다.

/* Create the pending page object with initializer. If you want to create a
 * page, do not create it directly and make it through this function or
 * `vm_alloc_page`. */
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)
	// printf("vm_alloc_page_with_initializer 진입 \n");
	struct supplemental_page_table *spt = &thread_current ()->spt;
	bool ret = false;

	/* 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* page = (struct page*) malloc(sizeof(struct page));

        /* Fetch the initializer according to the VM type */
		/* Initializing a function pointer */
        bool (*initializer)(struct page *, enum vm_type, void *);
		// vm_initializer 은 (struct page *, void *aux) 이다. 
		// anon_initializer (struct page *page, enum vm_type type, void *kva)
		// file_backed_initializer (struct page *page, enum vm_type type, void *kva) 
		// 는 뒤에 *kva 포인터가 하나 더 있다.
		//  (*initializer)(struct page *, enum vm_type, void *)
		// uninit_new의 마지막 매개변수 initializer의 타입은 위와 같다.
		if (VM_TYPE(type) == VM_ANON) {
			initializer = anon_initializer;
		}
		else if (VM_TYPE(type) == VM_FILE) {
			initializer = file_backed_initializer;
		} else {
			free(page); // 근데 위에서 ASSERT (VM_TYPE(type) != VM_UNINIT) 해주니 여기 올일은 없겠네
			return false;
		}
		/* TODO: Insert the page into the spt. */
		/* 여기서 넣어주는 init이 lazy_load_segment()임. process.c 에 있음. */
		uninit_new(page,upage,init,type,aux,initializer);
		page->writable = writable;
		ret = spt_insert_page(spt,page);
		return ret;
	}
err:
	printf("vm_alloc_page_with_initializer");
	return false;
}

 

 

1. upage가 이미 설정되어 있는지, 아닌지 확인합니다.
2. type에 맞는 initializer를 설정한 후
3. uninit_new() 함수를 통해 page type에 따른 (anon || file-backed) uninit을 수행합니다.
4. 이후 SPT 테이블에 해당 page를 넣어줍니다.

 

load_segment & lazy_load_segment 

구현 가이드

1. load_segment 함수 수정
   • load_segment 함수는 실행 파일의 세그먼트를 로드하는 함수입니다.
   • 루프를 통해 각 세그먼트를 처리하며, vm_alloc_page_with_initializer를 호출하여 대기 중인 페이지 객체를 생성합니다.
2. lazy_load_segment 함수 구현
   • 페이지 폴트가 발생했을 때, 실제로 세그먼트를 파일에서 로드합니다.
   • 이 함수는 주어진 파일에서 오프셋을 기준으로 데이터를 읽어와 페이지에 로드합니다.

 

 

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

 

 

/* You may want to create a structure that contains necessary information for the loading of binary. */

/* TODO: Set up aux to pass information to the lazy_load_segment. */

 

우선, 구현 요구사항에 맞춰 자료구조를 하나 생성합니다!

static bool install_page (void *upage, void *kpage, bool writable);
struct lazy_load_data {
    struct file *file;
    off_t ofs;
    size_t read_bytes;
    size_t zero_bytes;
};

 

 

 

 

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);
	/*  ELF포맷 파일의 세그먼트를 프로세스 가상주소공간에 탑재하는 함수이다.
	    이 함수에 프로세스 가상메모리 관련 자료구조를 초기화하는 기능을 추가한다.
  	    프로세스 가상주소공간에 메모리를 탑재하는 부분을 제거하고, page 구조체
	     의 할당, 필드값 초기화, 해시 테이블 삽입을 추가한다.
		
	*/
	while (read_bytes > 0 || zero_bytes > 0) {

		// Current code calculates the number of bytes to read from a file 
		size_t page_read_bytes = read_bytes < PGSIZE ? read_bytes : PGSIZE; 
		// the number of bytes to fill with zeros within the main loop
		size_t page_zero_bytes = PGSIZE - page_read_bytes; 

		/* You may want to create a structure that contains necessary information for the loading of binary. */
		/* TODO: Set up aux to pass information to the lazy_load_segment. */
		// 매개변수 (struct file *file, off_t ofs, uint8_t *upage, uint32_t read_bytes, uint32_t zero_bytes, bool writable)
		struct lazy_load_data *aux = (struct lazy_load_data*)malloc(sizeof(struct lazy_load_data));
		aux->file = file;
		aux->ofs = ofs;
		aux->read_bytes = page_read_bytes;
		aux->zero_bytes = page_zero_bytes;

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

 

vm_alloc_page_with_initializer 함수를 호출을 할 때 아래와 같은 일이 일어난다.

 

1. 페이지 할당 및 초기화
2. lazy_load_segment 라는 함수의 인자로 aux를 넘겨줌

 

여기서 넘겨준 aux의 자료구조를 자세히 보면 엄청난 힌트를 얻을 수 있다.

struct lazy_load_data {  // 'lazy_load_segment' 에서
    struct file *file;   // '해당 파일'을
    off_t ofs;		// 'ofs 위치' 에서부터
    size_t read_bytes;   // 'read_bytes' 만큼 읽어들이고
    size_t zero_bytes;   // 'zero_bytes' 만큼 0 으로 채우세요!
};

1. 'lazy_load_segment' 에서
2. struct file *file  '해당 파일'을
3. off_t ofs  에서부터
4. size_t read_bytes  만큼 읽어들이고
5. size_t zero_bytes 만큼 0 으로 채우세요!

 

우리가 프로그래밍을 배울 때 처럼, 처음부터 모든 문서를 읽는 것이 아니라, 필요 할 때 읽어야 할 부분을 정리해놓은 문서와 같다고 비유하면 될 것 같습니다!! 

 

 

lazy_load_segment

static bool
lazy_load_segment (struct page *page, void *aux) {
	/* you have to find the file to read the segment from 
	and eventually read the segment into memory. */
		
	struct lazy_load_data *data = (struct lazy_load_data*) aux;
	struct file *file = data->file;
	off_t ofs = data->ofs;
	size_t read_bytes = data->read_bytes;
	size_t zero_bytes = data->zero_bytes;

	// file_read_at (struct file *file, void *buffer, off_t size, off_t file_ofs) 
	file_seek(file,ofs);
	if(file_read(file,page->frame->kva, read_bytes) != (int)(read_bytes)) {
		palloc_free_page(page->frame->kva);
		return false;
	}

	memset(page->frame->kva + read_bytes, 0 , zero_bytes);
	return true;
	/* 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. */
}

 

 

file_read 함수가 보이나요? 

 

lazy_load_segment가 호출되면, 해당 file을 ofs의 위치에서부터 read_bytes 만큼 읽어들이는 것을 볼 수 있습니다!

 

 

Setup_stack 수정

1. setup_stack 함수 수정: setup_stack 함수를 수정하여 새로운 메모리 관리 시스템에 맞게 스택 할당을 조정합니다. 첫 번째 스택 페이지는 Lazy하게 할당될 필요가 없습니다. 명령행 인수와 함께 초기화되어야 하며, 이를 위해 추가적인 식별 방법을 제공해야 할 것입니다. vm.h의 vm_type에 있는 VM_MARKER_0 를 사용하여 페이지를 표시할 수 있습니다.

/* Create a PAGE of stack at the USER_STACK. Return true on success. */
static bool
setup_stack (struct intr_frame *if_) {
	bool success = false;
	void *stack_bottom = (void *) (((uint8_t *) USER_STACK) - PGSIZE);
	/* You might need to provide the way to identify the stack. */

	/* TODO: Map the stack on (1).stack_bottom and
	                          (2).claim the page immediately.

	/* TODO: You should mark the page is stack. vm_type of vm/vm.h (e.g. VM_MARKER_0) to mark the page. */
	/* (1) stack_bottomVM_ANON | VM_MARKER_0 을 사용하여 익명 페이지 + Stack임을 Marking 하자. */
	if (vm_alloc_page(VM_ANON | VM_MARKER_0, stack_bottom, 1)) {
		success = vm_claim_page(stack_bottom); // (2).claim the page immediately.
		if(success) {
			/* TODO: If success, set the rsp accordingly.*/
			if_->rsp = USER_STACK; 
			thread_current()->stack_bottom = stack_bottom; 
		}
	}
	return success;
}

 

 

vm_try_handle_fault 수정

1. vm_try_handle_fault 함수 수정: vm_try_handle_fault 함수를 수정하여 페이지 폴트가 발생한 주소에 해당하는 페이지 구조체를 해결합니다. 이를 위해 보충 페이지 테이블을 조회하여 spt_find_page를 사용합니다.

 

/* 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;
    
	/* TODO: Validate the fault */
	/* TODO: Your code goes here */
	if (addr == NULL || is_kernel_vaddr(addr)) {
		return false;
	}
    
	/*
	Step 1.
	1. 페이지폴트가 일어난 페이지를 찾는다. 
	
	Step 2.
	1. 페이지(가상)를 저장하기 위한 프레임(물리)을 얻는다.

	Step 3.
	1. 데이터를 (file system, 스왑슬롯, 혹은 zero page) 갖고온다.

	Step 4.
	1. page fault가 일어난 VA를 Physical Page를 가르키게 한다. threads/mmu.c 함수를 참조해라. */

	/* not_present 가 true인 경우, 물리페이지가 없는 것이다. */
	if (not_present) {

		page = spt_find_page(spt,addr);
		if (page == NULL) {
			return false;
		}
		if (write) {
			if (vm_handle_wp(page)) {
				return false;
			}
		}
		return vm_do_claim_page(page); 
 	}
	return false;
}

 

 

 

테스트 실행

 

모든 요구 사항을 구현한 후, 프로젝트 2의 모든 테스트가 통과되어야 합니다. fork를 제외한 모든 테스트를 통과해야 합니다.

 

 

Supplemental Page Table - Revisit

 

• supplemental_page_table_copy 함수 구현: supplemental_page_table_copy 함수를 구현하여 프로세스를 생성할 때 (특히 자식 프로세스 생성) 필요한 복사 작업을 지원합니다. 이 함수는 부모 프로세스의 보충 페이지 테이블을 복사하여 자식 프로세스에 새로운 보충 페이지 테이블을 생성합니다.
• supplemental_page_table_kill 함수 구현: supplemental_page_table_kill 함수를 구현하여 프로세스를 종료할 때 필요한 정리 작업을 수행합니다. 이 함수는 프로세스가 종료될 때 해당 프로세스와 관련된 모든 페이지를 제거하고 메모리를 해제합니다.

 

supplemental_page_table_copy

 

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

 

 

src의 보충 페이지 테이블에서 dst로 보충 페이지 테이블을 복사합니다. 이것은 자식이 부모의 실행 컨텍스트를 상속해야 할 때 사용됩니다(즉, fork()). src의 보충 페이지 테이블에서 각 페이지를 반복하고 해당 페이지 엔트리를 dst의 보충 페이지 테이블에 정확히 복사합니다. 새로운 초기화되지 않은 페이지를 할당하고 즉시 확보해야 합니다.

 

bool
supplemental_page_table_copy (struct supplemental_page_table *dst UNUSED,
		struct supplemental_page_table *src UNUSED) {
	/* hash.h  의 Iteration 파트를 참조하자. */
	/* A hash table iterator. */
	struct hash_iterator i;
	hash_first(&i,&src->hash_brown);
	/* Advances I to the next element in the hash table and returns
   	   it.  Returns a null pointer if no elements are left.  Elements
   	   are returned in arbitrary order.  */
	while(hash_next(&i))  {
		struct page *src_page = hash_entry(hash_cur(&i), struct page, hash_elem);

		//enum vm_type type = page_get_type(src_page);
		// 🐁 아래 식 대신, 위 함수를 썼다고 fork가 실패했다면 여러분들은 믿으시겠습니까??? 🐁
		enum vm_type type = src_page->operations->type;
		void *upage = src_page->va;
		bool writable = src_page->writable;
		vm_initializer *init = src_page->uninit.init;
		void *aux = src_page->uninit.aux;

		if (type == VM_UNINIT) {
			vm_alloc_page_with_initializer(VM_ANON,upage,writable,init,aux);
			continue;
		}

		if (type == VM_FILE) {
        	// file-backed는 나중에 고려.
			return false;
		}

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

		if (!vm_claim_page(upage)) {
			return false;
		}

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

 

 

 

supplemental_page_table_kill

 

void supplemental_page_table_kill (struct supplemental_page_table *spt);

SPT가 보유한 모든 리소스를 해제합니다. 이 함수는 프로세스가 종료될 때 호출됩니다 (userprog/process.c의 process_exit()). 페이지 항목을 반복하고 테이블의 페이지에 대해 destroy(page)를 호출해야 합니다. 이 함수에서는 실제 페이지 테이블(pml4)과 물리적 메모리(palloc으로 할당된 메모리)를 걱정할 필요가 없습니다. 호출자가 SPT가 정리된 후에 이를 정리합니다.

 

/* Free the resource hold by the supplemental page table */
void
supplemental_page_table_kill (struct supplemental_page_table *spt UNUSED) {
	/* TODO: Destroy all the supplemental_page_table hold by thread and
	 * TODO: writeback all the modified contents to the storage. */
	// hash_action_func -> 뒤에 함수 넘겨줘야함..
	// typedef void hash_action_func (struct hash_elem *e, void *aux);
	hash_clear(&spt->hash_brown, hash_destroy_func);
}

void
hash_destroy_func (struct hash_elem *e, void *aux) {
	struct page *page = hash_entry(e, struct page, hash_elem);
	destroy(page); // anon_destroy 및 uninit_destroy가 호출된다.
	free(page);
}

 

Now all of the tests in project 2 should be passed.