[TIL] [WEEK11-12] Pintos Project(3) Anonymous Page 1.

📍 두 번째 과제, Anonymous Page

이번 파트에서는 Anonymous Page(non-disk based image)를 구현한다.

Anonymous Page? 🤔
익명 매핑에는 백업 파일이나 장치가 없다. file-backed page와 달리 이름이 있는 파일 소스를 가지고 있지 않기 때문에 익명이라고 하며, 실행 가능한 파일에서 스택과 힙 영역에서 사용된다.
= 어떤 파일과도 매핑되지 않은 메모리 페이지로, 프로세스의 동적 메모리 할당 요청에 응답해 생성된다.

---

🛠️ Page Initialization with Lazy Loading

Lazy Loading이란 메모리 로딩을 지연시켜 필요한 순간에 데이터를 로딩하는 디자인 패턴이다.
즉, 페이지를 할당해 대응하는 페이지 구조체는 있으나 그것과 연결된 물리 프레임과 페이지의 실제 컨텐츠는 아직 로드되지 않은 상태다. 이 상태에서 page fault가 발생하면, 해당 페이지의 내용이 필요하다는 것을 의미한다.
이 때 페이지의 실제 컨텐츠를 로드하는 게 Lazy Loading이다.

Lazy Loading을 하는 이유는? 🤔
: 프로세스가 실제로 사용하지 않는 페이지는 메모리에 로드되지 않는다. lazy loading은 필요한 시점에 데이터를 로드함으로써 시스템의 리소스 낭비를 줄이고, 사용 가능한 메모리를 보다 더 효율적으로 사용할 수 있게 한다.

PintOS에는 3가지의 페이지 타입이 있는데, 각 타입별 초기화 루틴이 다르다.
페이지의 초기화 과정이 어떻게 되는지 알아보자.

1. vm_alloc_page_with_initializer()
   커널이 새로운 페이지 요청을 받으면 vm_alloc_page_with_initializer()를 호출한다.
   해당 함수는 page 구조체를 생성하고 적절한 초기화 함수를 설정한다. 또한 이렇게 생성된 페이지를 spt에 추가한다.
   -> 초기화하지 않고 초기화 함수를 '담아만' 두는데, 이렇게 초기화되지 않은 페이지 타입은 uninit이다.

2. page fault 발생 -> vm_try_handle_fault - ...
   유저 프로그램이 새로운 페이지에 처음 접근하게 되면 page fault가 발생되면서 lazy loading이 일어나며, 이 때 물리 프레임이 할당되면서 uninit page에 담겨있는 초기화 함수가 호출된다.

3. 페이지 초기화 및 lazy_load_segment
   페이지 유형에 맞는 초기화 함수가 호출되고, 동시에 내용이 로드된다.

위 과정을 표로 정리하자면 다음과 같다.
load_segment에서 while문으로 vm_alloc_page_with_initializer를 호출해 프로세스를 페이지 단위로 쪼개면서 spt에 적재한다.
vm_alloc_page_with_initializer에서는 새로운 페이지를 생성해 type에 맞는 초기화 함수를 담은 다음 uninit_new를 호출해 uninit_page로 초기화 한다.

---

1) vm_alloc_page_with_initializer()
page 구조체 생성 및 적절한 초기화 함수를 담아 uninit 페이지로 초기화

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. */
	/* upage가 이미 사용 중인지 확인 */
	if (spt_find_page(spt, upage) == NULL)
	{
		/* 페이지 생성 */
		struct page *p = (struct page *)malloc(sizeof(struct page));

		/* 페이지 타입에 따라 초기화 함수를 가져와 담기 */
		bool (*page_initializer)(struct page *, enum vm_type, void *);

		switch (VM_TYPE(type))
		{
		case VM_ANON:
			page_initializer = anon_initializer;
			break;

		case VM_FILE:
			page_initializer = file_backed_initializer;
			break;
		}

		/* 생성한 페이지를 uninit page로 초기화 */
		uninit_new(p, upage, init, type, aux, page_initializer);

		/* 페이지 구조체의 필드 수정 */
		/* 필드 값을 수정할 땐 uninit 호출 이후에 해야 한다 = uninit_new 함수 안에서 구조체 내용이 모두 새로 할당되기 때문에 */
		p->writable = writable;

		/* 생성한 페이지 spt에 추가 */
		return spt_insert_page(spt, p);
	}
err:
	return false;
}

해당 함수에서 uninit_new()를 호출해 uninit page로 초기화하는데, 어떻게 초기화할까?

void
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 구조체의 멤버변수를 할당하는 것 같은데, page 구조체는 어떻게 될까?

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

여기서 자세히 봐야할 게 두 가지 있다.

• operations: 페이지에 대한 다양한 연산을 정의하는 함수 포인터 구조체
• union: 페이지 유형의 공용체

🤔 함수 포인터란 뭘까?
: 함수 또는 메모리에 있는 실행가능한 코드를 가리키는 포인터인데, 이걸 왜 쓰는 거지?
-> c언어에서는 클래스와 상속의 개념이 없다.
객체지향 프로그래밍의 클래스 상속을 도입하기 위해 함수 포인터를 적용시킨 것이다.

page_operations 구조체를 보면 swap_in, swap_out, destroy가 있는 걸 볼 수 있을 것이다.
페이지 유형마다 각 루틴이 다를테니, 함수 포인터를 활용해 페이지 유형에 맞는 함수를 호출할 것이다.

다음으로 union은 공용체로, 페이지 유형에 따라 다른 멤버 변수를 포함한다.
각 페이지 유형 별 필요한 멤버변수가 다르기 때문에 어떤 공용체를 가지냐에 따라 필드가 추가된다.

이제 페이지의 구조체까지 봤으니 다시 uninit_new로 돌아가보자.

void
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 구조체의 operations를 uninit에 대한 연산을 하는 &uninit_ops로 할당하고,
union 공용체를 uninit_page로 둠으로써 4가지의 추가 멤버변수가 작용하는 걸 알 수 있다.

• init
  : page의 내용을 초기화하는 함수
  = 이는 vm_alloc_page_with_initializer에서 인자로 받은 lazy_load_segment가 들어갈 것이다.
• type
  : 페이지 유형
  = 이는 uninit이 아닌, 페이지를 생성할 때 담은 유형
• aux
  : init에 필요한 보조 인자
• initializer
  : 페이지 유형에 따른 초기화 함수
  = vm_alloc_page_with_initializer에서 담은 초기화 함수

여기서 주의깊게 봐야할 것은 &uninit_ops와 init, 그리고 initializer다.

• init
  : lazy_load_segment가 담기게 되는데, 이 함수가 호출될 때는 page fault가 발생해 데이터가 로드되어야 하는 시점일 것이다. lazy loading을 하기 위해 담는 함수라고 보면 될 것 같다.

• initializer
  : 이는 매개변수로 넘겨주는 type에 따라 다른 초기화 함수를 담게 된다.
  vm_alloc_page_with_initializer에서 인자로 받은 type이 anon type이라면 anon_initializer가, file_backed type이라면 file_baced_initializer 함수 포인터를 넘겨준다.
  함수 자체가 주소값을 지니고 있기 때문에 주소값 형태가 아닌 함수명 자체를 넘겨준다.

• &uninit_ops
  : page 구조체의 operations 멤버변수는 해당 페이지에 대한 다양한 연산을 정의하는 함수 포인터 구조체라고 했었다. uninit page에 대한 연산은 어떻게 이뤄지는지 함수 포인터를 타고 들어가면 다음과 같은 걸 볼 수 있다.

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

uninit page를 swap_in 할 때 uninit_initialize 함수를 호출하는 것을 볼 수 있다.
uninit_initialize 함수를 봐보자.

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;

	return uninit->page_initializer (page, uninit->type, kva) && (init ? init (page, aux) : true);
}

반환하는 걸 잘 보면 uninit page에 담겨있는 page_initializer를 통해 페이지 타입에 맞게 초기화함과 동시에 init을 호출하는 걸 알 수 있다. init은 위에서 말했다싶이 lazy_load_segment인데, 이 함수를 통해 데이터 로드가 진행된다.
데이터를 로드한다는 것은 첫 번째 page_fault가 발생했다는 의미일 것이다.

이제 데이터를 로드하는 함수인 load_segment와 lazy_load_segment 함수를 볼 차례다.

---

🛠️ load_segment() & lazy_load_segment()

1) load_segment()
위에서 load_segment가 잠깐 나왔는데, 프로세스를 페이지 단위로 쪼개 spt에 적재한다고 설명했었다.
자세히 설명하면 파일의 내용을 로드하는 함수인데, 그 내용을 적재할 page가 필요하기 때문에 vm_alloc_page_with_initializer를 호출하는 것이다.

그런데 우리는 바로 데이터를 로드하지 않기로 했다. lazy loading을 하기로 했기 때문에 vm_alloc_page_with_initializer를 호출할 때 인자로 lazy_load_segment와 그를 위한 보조 인자들을 넣어줘야 한다.

보조 인자들은 현재 구현되어 있지 않다. 우리가 lazy_load_segment를 위해 필요한 정보들을 생각해 그 정보들을 포함한 구조체를 만들어 넘겨주어야 한다.

해당 정보들은 어떤게 있을까?

• file: 파일 내용이 담긴 파일 객체
• ofs: 페이지에서 읽기 시작할 위치
• read_bytes: 페이지에서 읽어야 하는 바이트 수
• zero_bytes: 페이지에서 read_bytes만큼 읽고, 남은 공간을 0으로 채워야 하는 바이트 수

/* lazy_load_segment를 위한 보조 인자들 */
struct lazy_load_arg
{
    struct file *file;   /* file 내용이 담긴 파일 객체 */
    off_t ofs;           /* 페이지에서 읽기 시작할 위치 */
    uint32_t read_bytes; /* 페이지에서 읽어야 하는 바이트 수 */
    uint32_t zero_bytes; /* 페이지에서 read_bytes만큼 읽고 남은 공간을 0으로 채워야 하는 바이트 수 */
};

이러한 정보를 담기 위한 구조체인 lazy_load_arg를 선언하고 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);

	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;

		/* lazy_load_segment에 인자로 전달해 줄 보조 인자를 담아주기 */
		struct lazy_load_arg *lazy_load_arg = (struct lazy_load_arg *)malloc(sizeof(struct lazy_load_arg));
		lazy_load_arg->file = file;
		lazy_load_arg->ofs = ofs;
		lazy_load_arg->read_bytes = page_read_bytes;
		lazy_load_arg->zero_bytes = page_zero_bytes;

		if (!vm_alloc_page_with_initializer(VM_ANON, upage,
											writable, lazy_load_segment, lazy_load_arg))
			return false;

		read_bytes -= page_read_bytes;
		zero_bytes -= page_zero_bytes;
		upage += PGSIZE;
		ofs += page_read_bytes;
	}
	return true;
}

이렇게 되면 page fault가 발생할 때 lazy_load_segment를 통해 데이터가 로드될 것이다.
그럼 실제로 데이터를 로드하는 함수인 lazy_load_segment를 구현해보자.

2) lazy_load_segment()
첫 번째 page fault 발생 시, 페이지 초기화와 함께 호출되는 함수로 파일의 내용을 페이지로 로드한다.
해당 함수 이전에 페이지와 물리 프레임의 매핑은 이미 다른 함수에서 이뤄지기 때문에 여기에선 물리 프레임에 파일 내용을 로드하기만 한다.

이전에 lazy_load_segment를 위한 보조 인자들을 받아왔기 때문에 이를 활용해 읽어올 파일에 대해 내용을 로드하도록 구현하면 된다.

bool lazy_load_segment(struct page *page, void *aux)
{
	struct lazy_load_arg *lazy_load_arg = (struct lazy_load_arg *)aux;

	/* file의 offset을 lazy_load_arg의 ofs으로 이동시킴(읽기 시작할 위치) */
	file_seek(lazy_load_arg->file, lazy_load_arg->ofs);

	/* 페이지에 매핑된 물리 메모리의 프레임에 이동시킨 ofs에서부터 파일의 데이터를 읽어옴 */
	/* 제대로 읽어오지 못 했다면 -> 해당 페이지를 Free 시키고 False 반환 */
	if (file_read(lazy_load_arg->file, page->frame->kva, lazy_load_arg->read_bytes) != (int)(lazy_load_arg->read_bytes))
	{
		palloc_free_page(page->frame->kva);
		return false;
	}
	/* 남는 부분은 0으로 초기화 */
	memset(page->frame->kva + lazy_load_arg->read_bytes, 0, lazy_load_arg->zero_bytes);

	return true;
}

이렇게 데이터를 로드하는 부분까지 구현했지만, 사실 아직 전체적인 그림이 그려지지 않았다.
그래서 각 함수들이 어디서 호출되고, 연결되는지 팀원의 도움을 받아 다음과 같이 정리를 해봤다.

그런데 우리가 지금까지 다루지 않은 부분이 보일 것이다. setup_stack()?

---

🛠️ setup_stack()

프로세스를 로딩할 때, 즉 실행할 때 load 함수에서 호출되는 함수로 한 번만 호출된다.
setup_stack()은 stack에 초기 페이지를 생성한다.
이 말은, 첫 번째 스택 페이지를 Lazy Loading으로 로드할 필요가 없다. 어차피 프로세스가 실행될 때 setup_stack()을 호출하고 나서 커맨드 라인의 인자들 스택에 저장하기 위해 해당 주소에 바로 접근하기 때문이다.
그러니까 page fault가 발생하고 lazy loading하길 기다리지 않고 바로 물리 프레임을 할당 받아 페이지와 매핑해준다.

주의할 점: 스택은 아래로 성장하기 때문에 스택의 시작점(USER_STACK)에서 PGSIZE만큼 '아래'로 내린 지점에서 생성한다.

또한 페이지를 할당받을 때 해당 페이지가 스택의 페이지임을 표시해야 하기 때문에 보조 마커를 사용해야 한다. 페이지를 할당 받을 때 페이지의 타입과 함께 VM_MARKER_0을 사용해 표시할 수 있다.
나중에 이 마커를 통해 스택의 페이지인지 알 수 있다.

할당받은 페이지에 물리 프레임을 매핑하는데 성공했다면 스택 포인터(rsp)를 USER_STACK으로 설정한다.
앞으로 이 rsp부터 인자들을 push하게 될 것이다.

/* 프로세스가 실행될 때 load()에서 호출, STACK의 페이지를 생성하는 함수 */
static bool
setup_stack(struct intr_frame *if_)
{
	bool success = false;
	/* 스택은 아래로 커지니까, 스택 시작점 USER_STACK에서 PGSIZE만큼 아래로 내려간 지점에서 페이지 생성 = stack_bottom */
	void *stack_bottom = (void *)(((uint8_t *)USER_STACK) - PGSIZE);

	/* stack_bottm에 스택 매핑 후 페이지 요청 */
	/* 성공 시, rsp를 그에 맞게 설정 */
	/* 또한 페이지가 스택에 있음을 표시해야 함 */

	/* stack_bottom에 페이지 할당 받음 (스택은 아래로 커지니까) */
	/* VM_MARKER_0: 스택이 저장된 메모리 페이지 식별 */
	if (vm_alloc_page(VM_ANON | VM_MARKER_0, stack_bottom, 1))
	{
		/* 할당받은 페이지에 물리 프레임 매핑 */
		success = vm_claim_page(stack_bottom);
		if (success)
		{
			/* rsp 변경 */
			if_->rsp = USER_STACK;
			thread_current()->stack_bottom = stack_bottom;
		}
	}

	return success;
}

여기까지 lazy loading으로 데이터를 로드함으로써 page fault를 처리하는 것을 구현했다.
이제 page fault가 발생했을 때 지금까지 구현한 방식으로 처리할 수 있도록 handler를 수정해야 한다.

해당 부분부터는 다음 글에서 정리해야겠다.