📖01: Memory Management

VM 시스템을 지원하기위해 Virtual Page와 (page) Physical frame을 (frame) 효율적으로 관리해야한다. 이 뜻은 특정 (v든 p든) 메모리가 사용되고 있는지, 그렇다면 무슨 목적으로, 누구에게, 그리고 등등의 정보를 계속해서 추적할 수 있어야한다는 뜻이다.

---

📑Page Structure and Operations

---

📟struct page

VM의 VA들은 page 단위로 관리된다는 것을 이론을 통해 알고 있다. pintOS에선 page의 구조체가 include/vm/vm.h에 정의되어 있다.

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

위의 page 구조체 정의에서 알 수 있듯이, page는 세 가지 종류가 있다.

• VM_UNINIT
• VM_ANON
• VM_FILE

---

📟Page Operations

각 페이지가 수행해야 할 수 있는 작업(operations)들이 page_operations 구조체에 function pointer 형태로 저장되어있다. 이는 일종의 interface를 c에서 구현하는 방법 중 하나로, 해당 operation들은 page 구조체를 통해 언제든 요청될 수 있게 되어있다.

page operations 구조체는 아래와 같이 정의되어있다.

struct page_operations {
  bool (*swap_in) (struct page *, void *);
  bool (*swap_out) (struct page *);
  void (*destroy) (struct page *);
  enum vm_type type;
};

📑Implement Supplemental Page Table

---

Supplemental page table 이란 간단히 말해서 page table보다 많은 정보를 가진 page table이다. 이는 page fault, resource management 등의 이유로 필요하다.
(page fault가 발생하는 이유를 생각하면, 이런 상황을 해결하기 위해 page table보다 더 많은 정보를 담은 page table 인 spt의 필요성을 짐작 할 수 있다.)

우리는 pintOS에서 제공하는 hash table 자료구조를 이용해 spt를 구현할 것이다.

📟supplemental_page_table_init ()

---

이 함수는 is called when a new process starts (in initd of userprog/process.c) and when a process is being forked (in do_fork of userprog/process.c).

	#include "lib/kernel/hash.h"
    
/* Initialize new supplemental page table */
void
supplemental_page_table_init (struct supplemental_page_table *spt UNUSED) {
	struct hash* page_table = malloc(sizeof (struct hash));
	hash_init (page_table, page_hash, page_less, NULL);
	spt->page_table = page_table;
}

page_table에 메모리를 할당하고,
hash_table을 초기화 시키고,
spt에 해당 page_table을 연결시켜 spt초기화를 마친다.

🛑note: hash table 자료구조에 대한 자세한 설명은 다른 글에서 하겠다.
🛑hash table을 이용하기 위해 page 구조체에 hash_elem이라는 맴버를, supplemental_page_table 구조체에 struct hash* page_table이란 맴버를 추가했다.

🧮hash table functions

---

🧮hash_entry(HASH_ELEM, STRUCT, MEMBER)

hash elem 를 받아 해당 elem가 들어있는 구조체의 pointer를 return한다.

🧮hashbytes (const void *buf, size_t size)

Returns a hash of the SIZE bytes in BUF. 주어진 값을 주어진 size크기로 적당히 변환시키는 함수.ㅋㅋ

🧮page_hash

---

hash 테이블 자료구조에서 key 값을 받아 bucket 안의 index로 변형시키는 function이다.

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

🧮page_less

---

hash 자료구조에서 elem들의 값을 비교해 a, b중 a가 더 작은지 아닌지를 return하는 함수다.

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

---

📟spt_find_page ()

---

VA가 주어졌을 때, spt에 속한 적절한 page를 찾는 함수.
Find struct page that corresponds to va from the given supplemental page table. If fail, return NULL.

/* Find VA from spt and return page. On error, return NULL. */
struct page *
spt_find_page (struct supplemental_page_table *spt UNUSED, void *va UNUSED) {
	struct page page;
	page.va = pg_round_down (va);
	struct hash_elem *e = hash_find (spt -> page_table, &page.hash_elem);

	if (e == NULL) 
		return NULL;

	struct page* result = hash_entry (e, struct page, hash_elem);
	
    // VA가 결과로 받은 page의 va 범위에 들어가는지 검증. 0~4kb
	ASSERT((va < result->va + PGSIZE) && va >= result->va);
	
	return result;
}

VA를 round_down으로 page 주소 형태로 변형시키고,
해당 page 주소를 가진 hash elem을 찾은 뒤에,
해당 hash elem을 가진 page 구조체를 찾아서 result에 담고 return

📟spt_insert_page ()

---

인자로 주어진 page를 spt에 넣는 함수. 이미 spt에 있는 page인지 검증을 해줘야한다.

/* Insert PAGE into spt with validation. */
bool
spt_insert_page (struct supplemental_page_table *spt UNUSED,
		struct page *page UNUSED) {
	struct hash_elem *result = hash_insert (spt->page_table, &page->hash_elem);
	return (result == NULL) ? true : false ;
}

📑Frame Management

---

물리 메모리를 형상화하는 struct frame은 include/vm/vm.h에 아래와 같이 정의되어있다.

/* The representation of "frame" */
struct frame {
  void *kva;
  struct page *page;
};

📟vm_get_frame();

---

user pool에서 새로운 physical page를 palloc_get_page()를 통해 얻어온다. 그리고 이를 물리 메모리의 frame과 연결시킨다.

/* palloc() and get frame. If there is no available page, evict the page
 * and return it. This always return valid address. That is, if the user pool
 * memory is full, this function evicts the frame to get the available memory
 * space.*/
static struct frame *
vm_get_frame (void) {
	struct frame * frame = malloc (sizeof (struct frame));
	frame->kva = palloc_get_page (PAL_USER);
	frame->page = NULL;

	// Add swap case handling
	if (frame->kva == NULL) {
	  free (frame);
	  frame = vm_evict_frame ();
	}

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

🛑📟vm_do_claim_page ();

---

클레임은 물리적 프레임을 페이지에 할당하는 것을 의미합니다. 먼저 vm_get_frame(템플릿에서 이미 수행 된) 호출하여 프레임을 얻습니다 . 그런 다음 MMU를 설정해야 합니다. 즉, 가상 주소에서 페이지 테이블의 물리적 주소로의 매핑을 추가합니다. 반환 값은 작업의 성공 여부를 나타내야 합니다.
Claim the PAGE and set up the mmu. Claims, meaning allocate a physical frame, a page.

/* Claim the PAGE and set up the mmu. */
static bool
vm_do_claim_page (struct page *page) {
	struct thread *curr = thread_current ();
	struct frame *frame = vm_get_frame ();

	/* Set links */
	ASSERT (frame != NULL);
	ASSERT (page != NULL);
	frame->page = page;
	page->frame = frame;

	// Add to frame_list for eviction clock algorithm
	if (clock_elem != NULL)
		// Just before current clock
		list_insert (clock_elem, &frame->elem);
	else
		list_push_back (&frame_list, &frame->elem);

	/* Insert page table entry to map page's VA to frame's PA. */
	if (!pml4_set_page (curr->pml4, page->va, frame->kva, page->writable))
		return false;
	
	return swap_in (page, frame->kva);
}

The swap_in handler of uninit page automatically initializes the page according to the type, and calls INIT with given AUX.

🛑📟vm_claim_page ();

---

Claims the page to allocate va. You will first need to get a page and then calls vm_do_claim_page with the page.
할당할 페이지를 요청합니다 va. 먼저 페이지를 가져온 다음 해당 페이지와 함께 vm_do_claim_page를 호출해야 합니다.

/* Claim the page that allocate on VA. */
bool
vm_claim_page (void *va UNUSED) {
	struct page *page = spt_find_page (&thread_current ()->spt, va);

	if (page == NULL) 
		return false;

	return vm_do_claim_page (page);
}

---

📖02: Anonymous Page

---

https://yongshikmoon.github.io/2021/04/18/anon_pages.html

Non disk based image = anonymous page
먼저 ‘익명’ 이라는 뜻은 파일에 기반하고 있지 않은(파일로부터 매핑되지 않은) 페이지라는 뜻이다.
익명 페이지는 커널로부터 프로세스에게 할당된 일반적인 메모리 페이지이다.

파일-기반 페이지는 파일으로부터 매핑된 페이지를 뜻한다.
익명 페이지는 파일으로부터 매핑되지 않은, 커널로부터 할당된 페이지를 뜻한다.

프로세스가 mmap()으로 커널에게 익명 페이지를 할당 요청하게 되면, 커널은 프로세스에게 가상 메모리 주소 공간을 부여하게 된다.

부여된 가상 메모리 공간은 아직까지는 실제 물리 메모리 페이지로 할당되지 않은 공간이다.
부여된 가상 메모리는 메모리 읽기 쓰기시, 다음과 같은 커널 도움을 받아 zero 페이지로 에뮬레이션 되거나, 실제 물리 페이지로 매핑된다.

프로세스가 그 메모리 공간에 읽기 작업 시, 커널은 zero로 초기화된 메모리 페이지 (file-backed page with /dev/zero)을 제공한다.
프로세스가 그 메모리 공간에 쓰기 작업 시, 커널은 실제 물리 페이지를 할당하고 write된 데이터를 보관한다.

익명 페이지는 private 또는 shared로 할당받을 수 있다.
프로세스의 힙과 스택이 private로 할당된 anonymous page이다.
shared는 프로세스간 통신을 위해 사용되는 anonymous page이다.

📑Page Initialization with Lazy Loading

---

Lazy loading이란
disk에 그대로 냅뒀다가 특정 point를 요청하는 경우, 그 영역을 물리 메모리에 load하는 말그대로 게으르게 loaging하는 기법.

page가 allocated 되어 해당 데이터를 가르키는 page 구조체가 존재할 지라도, 연결된 frame이 없는(물리 메모리에 loading되지않은) 상태가 lazy loading에서 볼 수 있는 흔한 상황이다.

해당 page가 정말로 요청이 된다면, page fault가 발생하며 그제서야 disk에서 물리 메모리로 할당된다.

page initialization
3가지 종류의 page가 있는 만큼 각각의 page 종휴에 따라 다른 초기화가 필요하다.

vm_alloc_page_with_initializer()은 kernel이 새로운 page request를 받았을 때 호출된다.

The initializer will initialize a new page by allocating a page structure and setting appropriate initializer depending on its page type, and return the control back to the user program.

page fault는 user program이 진행되면서 program이 물리 메모리에 있을거라고 생각하면서 접근 하는데 실제로는 원하는 데이터가 물리 메모리에 load 혹은 저장되어있지 않을 경우 발생한다.

page fault handler가 실행되면, uninit_initialize()가 호출되고, 이는 위에서 이야기한 vm_alloc_page_with_initializer()가 호출되면서 초기화를 진행한다. 이때 anonymous page라면 anon_initializer()를, file-backed page라면 file_back_initializer()를 호출한다.

각각의 page는 아래와 같은 수명을 가진다고 볼 수 있다.
initialize->(page_fault->lazy-load->swap-in>swap-out->...)->destroy

page가 살아있는 동안 요구되는 변화들은 page type에 따라 다르다. 앞서 말한 초기화처럼 말이다.

pintOS에서는 이를 구현할 것이다.

📑Lazy Loading for Executable

---

process가 실행되고 주어진 작업(프로그램)을 실행시킬 때, 당장 필요한 데이터들만 물리 메모리에 할당되어있다.

lazy loading의 경우 eager loading과 비교했을때 overhead 현상이 훨씬 덜 발생한다는 것을 알 수 있다.

overhead 현상이란?
오버헤드란 프로그램의 실행흐름에서 나타나는 현상중 하나입니다. 예를 들어 , 프로그램의 실행흐름 도중에 동떨어진 위치의 코드를 실행시켜야 할 때 , 추가적으로 시간,메모리,자원이 사용되는 현상입니다.
출처: https://gamestory2.tistory.com/15 [베베의 개발일지]

📲VM_UNINIT

uninit type의 page는 lazy loading을 지원하기 위해 있다.

모든 페이지는 우선 uninit type으로 생성된다!

pintOS
All pages are initially created as VM_INIT pages. We also provide a page structure for uninitialized pages - struct uninit_page in include/vm/uninit.h. 
The functions for creating, initializing, and destroying uninitialized pages can be found in include/vm/uninit.c. 
You will have to complete these functions later.

🛑page fault in pintOS

📟vm_try_handle_fault()

---

page fault는 user program이 진행되면서 program이 물리 메모리에 있을거라고 생각하면서 접근 하는데 실제로는 원하는 데이터가 물리 메모리에 load 혹은 저장되어있지 않을 경우 발생한다.

page fault handler는 (page_fault in userprog/exception.c)
이 함수는 제어를 넘긴다 to vm_try_handle_fault in vm/vm.c

우선 유효한 page fault인지를 검증한다.
1. valid fault
2. bogus fault

bogus fault 일 경우 총 세가지 경우가 있는데 lazy-loaded, swaped-out page, and write-protected page.

지금은 첫번째 경우인 lazy-loaded인 경우만 고려한다.

page fault가 lazy-loagding 때문에 발생한 경우, the kernel calls one of the initializers you previously set in vm_alloc_page_with_initializer to lazy load the segment.
You will have to implement lazy_load_segment in userprog/process.c.

/* 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 thread *curr = thread_current ();
	struct supplemental_page_table *spt = &curr->spt;

	/* TODO: Validate the fault */
	/* TODO: Your code goes here */

	//Returns true if VADDR is a kernel virtual address.
	if (is_kernel_vaddr (addr) && user) 
		return false;

	// user stack이 작아서 생긴 문제일 경우?
	// void *stack_bottom = pg_round_down(curr->saved_sp);
	// if (write && (stack_bottom - PGSIZE <= addr && (uintptr_t) addr < USER_STACK)) {
	// /* Allow stack growth writing below single PGSIZE range
	//  * of current stack bottom inferred from stack pointer. */
	//     vm_stack_growth (addr);
	//     return true;
	// }

	struct page* page = spt_find_page (spt, addr);

	if (page == NULL) 
		return false;

	//case : write-protected page 
	// if (write && !not_present) 
	// 	return vm_handle_wp (page);

	return vm_do_claim_page (page);
}

📟vm_alloc_page_with_initializer()

---

주어진 type의 초기화 되지않은 page를 생성한다. 생성 후 에는 swap_in handler를 통해 uninit page를 자동적으로 초기화 시켜주고 (주어진 type에 맞게). 그리고는 spt에 집어 넣는다.
page 생성은 이 함수 혹은 vm_alloc_page()를 통해 진행되어야한다.

The page fault handler follows its call chain, and finally reaches uninit_intialize when it calls swap_in. We gives the complete implementation for it. Although, you may need to modify the uninit_initialize according to your design.

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

	struct supplemental_page_table *spt = &thread_current ()->spt;
	bool writable_aux = writable;

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

		// ASSERT(type != VM_UNINIT);
		/* create new page */
		struct page* page = malloc (sizeof (struct page));

		/* do different initialization depends on page the type */
		if (VM_TYPE(type) == VM_ANON){
			uninit_new (page, upage, init, type, aux, anon_initializer);
		}
		else if (VM_TYPE(type) == VM_FILE){
			uninit_new (page, upage, init, type, aux, file_backed_initializer);
		}

		page->writable = writable_aux;
		
		/* Insert the page into the spt. */
		spt_insert_page (spt, page);
		return true;
	}
err:
	return false;
}

함수 진행사항

spt_find_page
vm_anon_init
vm_file_init
anon_initializer
file_backed_initializer