[PintOS] Project 3 - Virtual Memory, Anonymous page (1)

흐름 정리

fork, process_create_initd 등으로 프로세스 생성 -> initd 함수에서 supplemental_page_table_init() 호출하여 현재 스레드의 supplemental page table 을 초기화한다.

userprog/process.c - initd()

supplemental_page_table_init()

새로운 spt를 초기화한다.

기존의 pml4라는 페이지 테이블은 주어진 va를 kva로 변환만 해주고 있고, va가 가리키고 있는 페이지 구조체 정보에 대한 어떠한 정보도 가지고 있지 않다. 따라서 spt는 va가 가리키고 있는 페이지에 대한 정보를 추가적으로 보충해 주는 역할을 한다.

 

-> pml4는 그냥 uint64_t로 선언되어 있는데 어떻게 테이블이라고 할 수 있을까?...

 

spt가 필요한 이유는 다음과 같다.

1. 페이지 폴트가 발생했을 경우 페이지 폴트가 발생한 페이지를 찾을 수 있다. 찾은 페이지가 갖고 있는 정보에 접근하기 위함이다.

pml4는 va와 매핑된 kva 말고는 어떤 정보도 갖고 있지 않아서 spt가 필요한 것인 건가?

2. 커널이 스레드를 종료시킬 때 그 스레드가 갖고 있는 spt를 참고하여 어떠한 데이터들이 할당 해제되어야 할지 결정한다.

-> 프로세스(스레드) 별로 spt를 하나씩 갖고 있다.

 

페이지 폴트가 일어난 가상 주소(va)를 포함하는 페이지 구조체가 있는데, 이 구조체에 접근하여 다양한 데이터를 사용하기 위해서 spt를 사용하는 것이다.

 

이 함수는 supplemental_page_table 구조체 타입의 spt 포인터를 인자로 받기 때문에, spt를 어떻게 초기화 할지 생각해 보아야 한다.

 

이 spt를 초기화 한다는 것은 spt가 갖고 있는 멤버들을 초기화 해주면 된다는 말과 같다.

spt를 리스트, 배열, 비트맵 등 여러가지로 구현할 수 있지만 일단 나는 spt를 해시테이블로 구현할 것이다.

spt의 멤버로 일단 hash 구조체 하나만을 갖도록 구현하였다.

 

struct supplemental_page_table {
    struct hash spt_hash;
};

 

따라서 spt를 초기화 한다는 것은 spt의 해시테이블을 초기화 한다는 말과 같으므로 hash_init()을 사용하여 초기화 해주면 된다.

 

hash_init()

hash_init()은 해시테이블을 초기화하는 함수이다.

인자는 struct hash *h, hash_hash_func *hash, hash_less_func *less, void *aux이다.

인자로 받은 hash h 해시테이블의 멤버를 hash_hash_func과 hash_less_func, aux로 초기화 해준다.

각각의 인자가 무엇을 의미하는지 보자.

 

• hash_hash_func은 함수이다. 따라서 hash_init()은 함수를 인자로 받는다!
  해시 테이블에 저장된 각 요소에 해시 값을 생성하는 'hash function'이다.
  해시 값은 해당 요소가 해시 테이블의 어떤 '버킷'에 저장될지 결정하는 데 사용된다.
• hash_less_func 역시 함수이다.
  두 개의 테이블 요소를 비교해서, 한 요소가 다른 요소보다 작은지 여부를 결정한다.
  해시 테이블 내에서 요소들의 정렬 상태를 유지하거나 특정 요소를 탐색할 때 두 요소가 같은지 비교하는 데 사용된다.
  또한 해시 충돌이 발생했을 때 버킷 내에서 요소를 찾는데도 필요하다.

결론적으로 말하자면, hash_hash_func는 요소가 해시 테이블 내의 어디에 위치할지를 결정하고 hash_less_func은 해당 위치에 다른 요소들이 존재할 경우 삽입, 탐색, 삭제 연산에서 정확한 요소를 식별하는데 도움을 준다.

 

그 밖에도 bucket을 동적 할당하는 등의 초기화를 진행한다.

 

다시 supplemental_page_table이 불렸던 위치 initd()로 돌아가면, 다음으로 실행되는 함수는 process_exec()이다.

 

process_exec()

기존에는 load를 통해 파일의 정보를 바로 물리 메모리에 적재했으나, 이제는 페이지만 할당하고 page fault가 발생할 때가 되어서야 메모리를 적재하는 과정을 거친다.

 

-> 페이지만 할당하고 프레임 생성, 프레임과 페이지 연결은 나중에 한다는 말인가?

-> 이것이 lazy loading인가?

 

load 안의 load_segment를 통해 세그먼트를 load하는데, #ifndef의 #else로 선언된 이후의 load_segment를 사용하게 된다.

 

load()

간단하게 load()의 역할을 살펴보자면 다음과 같다.

1. pml4_create()를 호출하여 프로세스의 pml4 페이지 테이블을 생성하고, 프로세스의 가상 메모리 공간을 생성한다.
2. 실행 파일로부터 세그먼트를 로드한다.
   실행 가능 파일의 프로그램 헤더(phdr)를 분석하여 'PT_LOAD' 유형의 세그먼트 즉, 메모리에 로드되어야 하는 세그먼트를 식별한다.
   각 세그먼트에 대해 'load_segment'를 호출해서 세그먼트의 데이터를 파일로부터 가상메모리로 로드한다.
3. 페이지 '할당'을 요청한다.
   'vm_alloc_page_with_initializer'을 통해 수행된다.

결국 pml4_create()를 통해 프로세스의 가상 주소 공간을 만들고, 그곳에 load_segment를 통해 세그먼트들을 로드하는 것이다.

 

load_segment()

이 load_segment함수는 세그먼트를 load하긴 하지만, 이전과는 다르게 파일의 정보에 대해 페이지 할당만 할 수 있도록하는 과정을 거친다.

인자는 struct file *file, off_t ofs, uint8_t *upage, uint32_t read_bytes, uint32_t zero_bytes, bool writable 등이 있다.

인자들을 하나씩 살펴보자면,

• struct file *file
  process_exec()에서 넘겨받은 파일에 대한 포인터이다.
  이 파일을 읽어서 가상 메모리에 로드할 것이다.
• off_t ofs
  파일 내에서 데이터를 읽기 시작할 오프셋 즉, 위치이다.
  정확히 오프셋이 하는 역할을 이해하기 어렵다
• uint8_t *upage
  가상 메모리 주소 공간 내에서 데이터가 로드될 시작 주소이다.
  load_segment 함수에서의 upage는 프로그램의 가상 주소 공간 내에서 데이터를 로드해야 할 시작 주소를 의미한다.
• uint32_t read_bytes
  파일에서 실제로 읽어야 할 데이터의 크기를 바이트 단위로 지정한 것
  file에서 ofs이 지정된 위치부터 읽어서 upage부터 시작하는 가상 메모리 주소 공간에 복사한다.
• uint32_t zero_bytes
  파일을 로드하고, 나머지 페이지 공간을 초기화할 필요가 있을 때 사용된다.
  데이터 구조체의 끝을 명시하거나 메모리 누수 방지를 위한 목적으로 사용된다.
• bool writable
  로드된 페이지가 쓰기 가능일지를 결정한다.
  코드 세그먼트(읽기 전용)일지, 데이터 세그먼트(쓰기 가능)일지를 결정할 수도 있다.
  세그먼트란 프로그램을 논리적 기준 코드, 데이터, BSS, 힙, 스택 등으로 구분한 것을 말한다!

요약하자면, 프로세스가 load에서 pml4_create()를 통해 가상 주소 공간을 만들고 나면, 그 가상 주소 공간 이내에 있는 upage에 file에서 로드된 데이터들을 저장한다.

 

load_segment()는 세그먼트 데이터를 로드할 가상 주소에 해당하는 페이지를 '할당'하기 위해 vm_alloc_page_with_initializer를 다음과 같이 호출한다.

vm_alloc_page_with_initializer (VM_ANON, upage, writable, lazy_load_segment, aux)

 

alloc 시에 VM_ANON으로 하는 이유를 잘 모르겠다.

 

이때 vm_alloc_page_with_initializer의 인자 중 하나인 vm_initializer *init 함수 즉 여기서는 lazy_load_segment가 실행되기 위해서는 다른 인자들을 aux에 담아주어야 가능하다. 따라서 aux에 파일 정보와 load에 필요한 정보들을 담는다.

 

aux에 파일의 정보들을 담고 vm_alloc_page_with_initializer를 통해 upage에 page들이 실제로 allocate되기 시작한다.

 

이 load_segment()는 이후에 다시 살펴보도록 하겠다.

vm_alloc_page_with_initializer()

page 구조체를 '생성'하고 적절한 초기화 함수를 설정하는 것이 함수가 하는 역할이다.

나는 palloc_get_page()를 사용하면 된다고 생각했다.

-> page 구조체를 '생성'하는 것과 '할당'하는 것은 다른 것인가?

 

uninit_new() 함수를 통해 uninit 타입으로 초기화를 시도한다. 인자는 다음과 같다.

• p - 초기화할 page 구조체
  palloc_get_page()로 할당받은 page 구조체를 넣어주면 된다.
  대부분 malloc을 사용하던데, 아마 수정될 것 같다.
• upage - p를 할당할 가상 주소
• init - p의 내용을 초기화하는 함수
• type - ??
• aux - init에 필요한 보조값
• initializer - p를 타입에 맞게 초기화하는 함수

지금까지의 실행 흐름대로라면 init은 lazy_load_segment일 것이고, type은 VM_ANON이다.

 

p 외에 upage, init, aux는 vm_alloc_page_with_initializer()가 전달받은 매개변수를 그대로 전달해주면 된다. initializer는 매개변수로 들어온 type에 따라 분기를 나눠야 한다.

 

이 말은 즉, 어떤 프로세스가 페이지가 필요한데 그 페이지 type이 어떠할 것임을 실제 페이지를 할당하는 순간에 알고 있다.

그 type에 따라서 초기화를 다르게 진행해야하고, 그것이 바로 initializer 함수이다.

 

나는 switch 문을 이용하여 따로 initializer를 선언하지 않고 type에 따라 분기를 나누었다.

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;

	if (spt_find_page (spt, upage) == NULL) {
        
        struct page *p;
        p = palloc_get_page(PAL_USER);
        if (p == NULL)
            return false;
            
        switch (type)
        {
        case VM_ANON:
            uninit_new(p, upage, init, type, aux, anon_initializer);
            break;
        case VM_FILE:
            uninit_new(p, upage, init, type, aux, file_backed_initializer);
            break;
        default:
            return false;
        }
        spt_insert_page(spt, p);
	}
err:
	return false;
}

 

하지만 함수 포인터를 사용해 보기 위해 initializer를 선언하고 바꾸었다.

참고한 블로그에 다음과 같이 나와 있다.

 

C언어에는 '클래스'나 '상속'이 없지만, 객체 지향 프로그래밍의 '클래스 상속' 개념을 도입하기 위해 함수 포인터를 사용한다.

함수 포인터를 전달한다는 것이 생소하게 느껴지는데, uninit_new 함수에 선언되어 있는 함수 포인터의 타입인 bool(*initializer)(struct page *, enum vm_type, void *)의 리턴 타입과 매개변수 타입이 일치하는 함수를 전달하면 된다.

initializer라는 이름은 매개변수의 이름에 불과하므로 이름은 달라져도 상관 없다.

함수 자체가 주소값을 지니기 때문에 & 없이 함수명만 전달하면 된다,

위 타입으로 선언하고 변수처럼 값을 바꾸는 방식으로 구현하면 된다.

 

다음으로 쓰기 가능 여부를 나타내는 writable 매개변수 값을 uninit_new 이후, 즉 초기화 되고 난 이후에 page 구조체의 writable 필드에 할당한다.

 

uninit_new에서 initializer로 페이지가 초기화가 되기 때문에 꼭 uninit_new 호출 이후에 수행해야 한다.

하지만 uninit_new에서 필드를 수정하는 것이 writable에는 해당되지 않는데, 순서가 중요할까? 싶긴 하다.

 

드디어 새로운 페이지가 만들어졌다. 즉, 페이지 유저 주소 공간에 사용 가능한 페이지가 매핑 되었다.

하지만 아직 lazy_load가 어떻게 이뤄지는 것인지 이해하기 어렵다. 따라서 uninit_new를 보아야 한다.

uninit_new

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

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

 

이 함수의 역할은 다음과 같다.

• 매개변수로 받은 page 구조체를 uninit type으로 만든다.
  page 구조체는 uninit, anon, file, page_cache 중 한 가지 타입을 갖는데 여기서는 uninit 타입으로 만들 것이기 때문에 page 구조체에 uninit 필드가 생기게 되는 것이다.
  즉, 공용체union 으로 선언되어 있었던 여러 타입들 중에 하나의 타입으로 드디어 설정시켜주게 되는 것이다.
• page->operations를 uninit_ops로 설정하여 진짜 '초기화'를 할 수 있게 만들어준다.

static const struct page_operations uninit_ops = {
	.swap_in = uninit_initialize,
	.swap_out = NULL,
	.destroy = uninit_destroy,
	.type = VM_UNINIT,
};

 

이 uninit_ops를 보면 swap_in에 uninit_initialize가 담겨 있다.

페이지가 실제로 로딩될 때 즉, page fault가 발생할 떄 이 swap_in에 담겨진 uninit_initialize가 호출되게 되면서 uninit 페이지의 초기화가 이뤄진다.

• page->uninit->init에 매개변수로 받은 init을 담는다.
  여기서 드디어 우리가 load -> load_segment -> vm_alloc_page_with_initializer의 실행 흐름 속에서 vm_alloc_page_with_initializer를 할 때 uninit_new에 넘겼던 lazy_load_segment가 담기는 모습을 볼 수 있다.
• page->uninit->page_initializer에 매개변수로 받은 initilaizer을 담는다.
  load_segment의 vm_alloc_page_with_initializer를 호출하는 흐름에서는 VM_ANON 타입으로 넘겨주었기 때문에 switch문을 통해서 설정해 주었듯, anon_initializer가 담길 것이다.

여기까지가 대기하고 있는 page를 만드는 과정이다.

즉, 대기하고 있는 페이지는 최초에 vm_alloc_page_with_initializer안의 uninit_new를 통해 VM_UNINIT 타입으로 만들어진다. 이 VM_UNINIT 페이지는 이후에 VM_ANON 혹은 VM_FILE로 바뀔 것이고, 최초에 vm_alloc_page_with_initializer에서 VM_ANON 타입으로 설정한다.

 

그리고 이후에 page fault가 발생하면 vm_try_handle_fault를 호출하고 이 함수는 또 vm_do_claim_page를 호출한다.

거기서 swap_in을 호출하여 결론적으로 page가 anon_initializer를 통해 anonymous page로 초기화되고, lazy_load_segment를 호출한다.

 

이제 lazy_load_segment가 무엇을 하는지 살펴보면 된다.

 

lazy_load_segment()

앞서 말했듯, 첫 번째 page fault가 발생할 때 호출된다.

물리 프레임이 매핑되는 과정은 vm_try_handle_fault()에서 vm_do_claim_page()를 통해 이루어지므로, 물리 프레임에 내용을 로드하는 작업을 거치면 된다.

 

이와 같은 과정으로 lazy loading이 이루어진다.

Reference

https://velog.io/@park485201/pintos-project-3-VM

[pintos] project 3 - VM

https://hongchangsub.com/pintos-project3-anonymous-page/

pintos - project3(Anonymous Page) 수도 코드

https://e-juhee.tistory.com/entry/Pintos-KAIST-Project-3-Anonymous-Page-Lazy-Loading%EC%9C%BC%EB%A1%9C-%EB%A9%94%EB%AA%A8%EB%A6%AC-%ED%9A%A8%EC%9C%A8%EC%84%B1-%EB%86%92%EC%9D%B4%EA%B8%B0