[PintOS] Project 3. VIRTUAL MEMORY

supsssonยท2022๋…„ 6์›” 21์ผ
0

pintos

๋ชฉ๋ก ๋ณด๊ธฐ
2/2
post-thumbnail

๋“ค์–ด๊ฐ€๊ธฐ ์ „

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 ํ•จ์ˆ˜๋„ ํ•จ๊ป˜ ํ˜ธ์ถœ๋œ๋‹ค.

0๊ฐœ์˜ ๋Œ“๊ธ€