[PintOS] Project 3. VIRTUAL MEMORY

들어가기 전

• 가상 메모리? 메모리 공간?
  https://velog.io/@supssson/동적-메모리-할당
  https://velog.io/@supssson/OS-Memory

1. Memory Management

Implement Supplemental Page Table

• PintOS에는 pml4라는 페이지 테이블이 존재하지만 Page Fault와 자원 관리를 위해 더 많은 정보를 담을 Supplemental Page Table이 필요하고 이를 구현
• 물리 메모리를 관리하기 위한 Frame과 Management에 필요한 함수 구현

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

현재 include/vm/vm.h에 page 구조체는 위와 같이 정의됨

2. Anonymous Page

Page Initialization with Lazy Loading

• Lazy Loading(= Demand Paging)을 위해 uninit 상태의 페이지 생성
• 가상 주소 / 페이지 타입 / initializer 등 파라미터 설정 후 uninit_new() 호출

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. */
		struct dummy *aux = (struct dummy*)malloc(sizeof(struct dummy));
		aux->file = file;
		aux->read_bytes = page_read_bytes; // * 혜진
		aux->zero_bytes = page_zero_bytes;
    aux->ofs = ofs;

		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;
    ofs += page_read_bytes;
		upage += PGSIZE;
	}
	return true;
}

• 프로그램을 실행할 때 첫번째로 load() 함수와 load_segment() 함수를 통해 파일을 읽어들여 세그먼트 단위로 자른다.
• 그 후 Lazy Loading을 위해 각 페이지들을 uninit 상태로 초기 세팅 하기 위해 vm_alloc_page_with_initializer() 함수를 호출하게 된다.

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)

  bool success = false;
  struct supplemental_page_table *spt = &thread_current()->spt;

  /* Check wheter the upage is already occupied or not. */
  if (spt_find_page(spt, upage) == NULL)
  {
    /* TODO: Create the page, fetch the initializer 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 *p = (struct page *)malloc(sizeof(struct page));

    if (type == VM_ANON)
      uninit_new(p, pg_round_down(upage), init, type, aux, anon_initializer);
    else if (type == VM_FILE)
      uninit_new(p, pg_round_down(upage), init, type, aux, file_backed_initializer);

    p->writable = writable;
    /* TODO: Insert the page into the spt. */
    success = spt_insert_page(spt, p);
  }
  return success;
err:
  return success;
}

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

• uninit 페이지 Initialize 후 페이지 폴트가 일어나기 전에는 해당 페이지에 맵핑 되는 데이터가 메모리에 올라오지 않는다.

• 아직 메모리에 올라오지 않은 데이터에 접근하려고 할 때 아래의 page_fault() 함수가 호출 되면서 vm_try_handle_fault() 함수를 호출하게 된다. 해당 함수는 exception.c에 있다.

• vm_try_handle_fault()가 호출되면 들어온 파라미터들을 검사하여 fault에 대한 처리를 한다.
• 초기 fault는 페이지는 할당되어 있지만 물리 메모리에 올라온 데이터들이 없기 때문에 일어난 fault이기 때문에 vm_do_claim_page를 호출하면서 물리 메모리에 해당 데이터들을 적재하는 과정을 거친다.

• vm_do_claim_page() 함수에서는 vm_get_frame()을 호출하여 프레임과 4KB에 해당하는 물리 메모리를 할당 받아온다.
• supplemental page table과 frame table을 통해 조금 더 쉽게 페이징을 구현하기 위해 페이지와 프레임 구조체에 서로를 맵핑 시킨다.
• 위 과정을 거친 후 PintOS에서의 진짜 페이지 테이블인 pml4에 페이지와 프레임을 맵핑 시킨 후 swap_in()을 호출한다.

---

swap_in()을 통해 물리 메모리에 어떤식으로 데이터가 적재 되는지를 알기전에 PintOS에서의 페이지 테이블인 pml4와 vm_get_frame()을 통해 프레임과 4KB의 물리 메모리를 할당받는 과정을 먼저 알아보았다.

---

/* Obtains a single free page and returns its kernel virtual
   address.
   If PAL_USER is set, the page is obtained from the user pool,
   otherwise from the kernel pool.  If PAL_ZERO is set in FLAGS,
   then the page is filled with zeros.  If no pages are
   available, returns a null pointer, unless PAL_ASSERT is set in
   FLAGS, in which case the kernel panics. */
void *
palloc_get_page (enum palloc_flags flags) {
	return palloc_get_multiple (flags, 1);
}

• palloc_get_page() 함수의 주석에 "Obtains a single free page and returns its kernel virtual address"라고 적혀있다.

아래에서 다룰 내용이지만 실제 물리 메모리 공간 즉 frame을 할당받기 위해서는 palloc_get_page() 함수를 호출 해야한다. 하지만 해당 함수 주석을 보면 리턴값이 kernel virtual address라고 적혀있는 것을 볼 수 있는데 이는 아래 내용을 통해 왜 그런지 알 수 있었다. 모든 내용을 정확히 제대로 알아내지는 못했지만 나름대로 혼자 이해한 내용을 적었다.

실제 물리 메모리의 0번 주소부터 mem_end 즉 메모리의 끝 주소까지 va에 맵핑하여 페이지 테이블을 구성하는 것을 볼 수 있다. 이는 커널 영역과 물리 메모리가 1:1 맵핑 된다는 뜻이다. 실제 PintOS 과정 중 질의 응답을 통해 알게된 내용과 일치했다.

커널 영역의 va와 물리 메모리의 pa가 1:1 맵핑되어 있다고 했을때 위 함수의 주석처럼 palloc_get_page() 함수를 통해 비어 있는 물리 메모리의 주소에 해당하는 kva(kernel virtual address)를 return하면 결국엔 물리 메모리의 4KB 공간을 할당해준거나 마찬가지일 것이다.

palloc_get_page() 함수를 호출하면 위 함수가 호출되는데 위 함수를 통해 커널 영역의 빈 공간은 비트맵으로 관리되고 있는 것을 알 수 있었다. bitmap_scan_and_flip() 함수를 통해 비트맵으로 관리되는 kva의 빈 공간을 찾아 해당 index를 반환해주고 해당 공간이 할당되었다고 true로 flip 해준다.

위 내용을 이해하고 아래 코드를 보면 frame을 할당해주는 vm_get_frame() 함수 과정을 쉽게 이해할 수 있을 것이다.

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

frame을 구성하고 있는 멤버들 중 kva는 kernel virtual address를 나타내며 page는 해당 프레임과 맵핑 되어지는 페이지의 정보를, frame_elem은 프레임들을 리스트로 연결시켜주기 위한 구성요소이다.

PintOS에서 frame 구조체는 실제 물리 메모리에서의 4KB 공간이 할당된 프레임을 나타내는 것이 아니라 해당 프레임의 부가적인 정보들을 담기위한 구조체이다.

그렇기 때문에 frame 구조체는 malloc으로 할당해주어야 하며 아래 코드에서도 볼 수 있듯이 frame->kva는 palloc_get_page(PAL_USER) 를 통해 실제 물리 메모리 중 4KB를 할당 받아야 한다.

다시 vm_do_claim_page() 함수로 돌아와 노란색 박스의 내용을 살펴보면 위에서 vm_get_frame()을 통해 할당 받은 frame과 page들을 맵핑 시켜주고, 해당 내용을 pml4 테이블에 넣어주는 과정을 거친다.

pml4_set_page() 함수를 통해 이루어지는 과정을 그림으로 그려보았다.

pml4에는 앞서 보았던 kva와 pa의 맵핑이 이미 되어 있는 상태이며 이후 pml4_set_page() 함수를 통해 파라미터로 전달된 va와 해당 kva를 맵핑 시켜주면 va를 통해 물리 메모리의 데이터를 가져올 수 있을 것이다.

---

여기까지가 PintOS에서의 pml4, frame 할당 과정을 이해한 내용이며 다시 swap_in 과정으로 돌아와서 살펴보면

uninit_new() 함수를 통해 설정 해놓았던 uninit_ops의 swap_in 함수인 uninit_initialize가 호출된다.

이때 return이 적힌 라인에서 타입에 따라 해당하는 initializer가 호출되며, 앞서 넣어둔 init함수인 lazy_load_segment 함수도 함께 호출된다.