개요

실제 운영체제에서 가상 메모리와 물리 메모리의 매핑 정보는 페이지 테이블에 있다. 페이지 테이블 엔트리에 있는 정보는 PPN 뿐만 아니라 여러 정보들을 담고 있다.

하지만 핀토스에서는 64비트 주소공간에 추가 비트를 할당하지 않고 별도의 페이지 테이블을 운용한다. 그리고 접근 속도를 빠르게 하기 위해 해시 테이블 방식을 사용한다. 본 블로그에서는 해시 테이블 동작에 대한 자세한 설명은 생략하고자 한다. 물론 해시 테이블은 매우 중요한 자료구조이다. 핀토스에서는 별도의 페이지 테이블을 Supplemental Page Table(spt)라 부르며 별도의 구조체를 가지고 있다.

핀토스에는 페이지는 uninit, anonymous,file-backed 로 3 종류가 있다. 페이지 종류에 따라 페이지 동작 함수가 다르다. 이는 함수 포인터를 통해 구현한다.

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

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

#define swap_in(page, v) (page)->operations->swap_in ((page), v)
#define swap_out(page) (page)->operations->swap_out (page)
#define destroy(page) \\
	if ((page)->operations->destroy) (page)->operations->destroy (page)

// vm/file.c/static const struct page_operations file_ops
/* DO NOT MODIFY this struct */
static const struct page_operations file_ops = {
	.swap_in = file_backed_swap_in,
	.swap_out = file_backed_swap_out,
	.destroy = file_backed_destroy,
	.type = VM_FILE,
};

file-backed 페이지를 destroy하는 상황을 생각해 보자. 그렇다면 우선 destroy(page) 함수가 호출 된다. 위 코드 블럭에 있는 destroy 매크로에 따라 페이지 구조체 내의 page_operations를 호출한다. 마지막으로 page_operations 내의 .destroy 멤버인 file_backed_destroy가 호출 되어 페이지 종류에 맞는 동작을 진행한다.

SPT 구현

위에서 언급 했듯이 SPT는 해시 테이블 방식으로 구현된다. 따라서 페이지 구조체 내에 해시 테이블 운용에 사용될 hash_elem 구조체를 선언해 준다. 이는 list_elem과 유사하다고 생각하면 편하다.

/* vm.h */

struct page {
	const struct page_operations *operations;
	void *va;              /* Address in terms of user space */
	struct frame *frame;   /* Back reference for frame */
	...
	/* 해시 테이블 운용 */
	struct hash_elem hash_elem;
	... 
}

우선 SPT를 사용하기 위해 SPT를 초기화 시켜준다. SPT는 해시 테이블 이기 때문에 SPT 초기화 함수 내부에서 해시 테이블을 초기화 하는 함수를 호출한다. SPT를 초기화 하는 경우는 프로세스가 처음 생성될 때(initd)와 자식 프로세스(__do_fork)를 생성할 때이다.

/* vm.c */
void supplemental_page_table_init (struct supplemental_page_table *spt UNUSED) {
	hash_init(&spt->pages, page_hash, page_less, NULL);
}

해시 테이블을 초기화 할 때 키 값을 생성하는 page_hash과 키 값을 확인하는 page_less이 필요하다.

/* vm.c */
unsigned 
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);
}

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를 초기화 했다면 SPT에 페이지를 삽입 할 수 있어야 한다. 이는 insert_page를 통해 이루어 진다. 이는 결국 해시 테이블에 추가 하는 것이므로 insert_page는 hash_insert 를 호출 한다.

/* vm.c */
bool 
insert_page(struct hash *pages, struct page *p) {
    if (!hash_insert(pages, &p->hash_elem))
        return true;
    else
        return false;
}

SPT를 초기화 하고 SPT에 요소를 삽입 하였다면 SPT를 통해 요소를 찾는 함수를 구현해야한다. 이는 hash_find를 통해 이루어진다.

/* vm.c */

struct page *
spt_find_page (struct supplemental_page_table *spt UNUSED, void *va UNUSED) {
	
	/* 해시 테이블 순회에 사용될 페이지 구조체를 선언 */
	struct page *page = (struct page*)malloc(sizeof(struct page));
	/* TODO: Fill this function. */
	struct hash_elem *e;
		
		/* 요청받은 va를 페이지 시작주소로 변환하여 순회용 구조체에 기입 */
    page->va = pg_round_down(va);
		
		/* 해시 검색 함수를 이용하여 탐색*/  
    e = hash_find(&spt->pages, &page->hash_elem);
		
		/* 순회용 구조체 메모리 할당 해제 */
    free(page);
		
		/* 검색 결과 맞는 페이지가 있다면 hash_entry를 통해 해당 페이지 반환 없다면 NULL */
    return e != NULL ? hash_entry (e, struct page, hash_elem) : NULL;
}

Physical Frame 구현

물리 메모리에 있는 각 프레임(페이지 단위)의 정보를 담고 있는 frame table을 구현해야한다. frame 테이블을 통해 swap in과 out을 위한 eviction 정책을 수행한다. frame 테이블은 리스트 형식으로 관리한다. 이를 위해 프레임 구조체에 리스트 요소를 추가해 준다. 그리고 프레임 테이블을 사용하기 위해 전역 변수로 프레임 테이블 리스트를 선언해 준다. 그리고 vm_init에서 리스트를 초기화 시켜준다.

/* vm.h */

struct frame {
	/* 프레임 구조체에 대응되는 커널 가상 주소 */
	void *kva;

	/* 프레임 구조체에 대응되는 커널 가상 영역에 있는 페이지 */  
	struct page *page;

	/*  */
	struct list_elem frame_elem;
};

/* vm.c */
...
struct list frame_table;
struct list_elem *start;
...

void
vm_init (void) {
	vm_anon_init ();
	vm_file_init ();
#ifdef EFILESYS  /* For project 4 */
	pagecache_init ();
#endif
	register_inspect_intr ();
	/* DO NOT MODIFY UPPER LINES. */
	/* TODO: Your code goes here. */
	list_init(&frame_table);
	start = list_begin(&frame_table);
}

프로세스를 수행하기 위해서는 가상메모리와 물리 메모리를 할당 받아야 한다. 물리 프레임을 얻기 위한 함수는 vm_get_frame 이다. 할당 받은 프레임을 초기화 하여 반환하는 함수이다.

static struct frame *
vm_get_frame (void) {
	struct frame *frame = (struct frame*)malloc(sizeof(struct frame));
	/* palloc_get_page를 통해 페이지를 할당 받는다. 할당 받은 페이지를 kva와 연결 */
	frame->kva = palloc_get_page(PAL_USER);
	
	/* 물리 메모리에 자리가 없어 할당 못받은 경우 물리 메모리에서 페이지를 내려야함 */  
	if(frame->kva == NULL){
	      frame = vm_evict_frame();
	      frame->page = NULL;
	      return frame;
	  }
	
	/* 프레임 테이블에 추가하고 프레임을 초기화 하여 반환 */
	list_push_back (&frame_table, &frame->frame_elem);
  frame->page = NULL;
	
	ASSERT (frame != NULL);
	ASSERT (frame->page == NULL);
	
	return frame;
}

vm_evict_frame을 통해 swap 디스크로 내려보낼 프레임을 swap out 시킨다. 내려 보낼 프레임은 vm_get_victim을 통해 선정한다.

/* vm.c */

static struct frame *
vm_evict_frame (void) {
	struct frame *victim UNUSED = vm_get_victim ();
	swap_out(victim->page);
	return victim;
}

static struct frame *
vm_get_victim (void) {
	struct frame *victim = NULL;
	 /* TODO: The policy for eviction is up to you. */
	struct thread *curr = thread_current();
  struct list_elem *e = start;

  for (start = e; start != list_end(&frame_table); start = list_next(start)) {
        victim = list_entry(start, struct frame, frame_elem);
        if (pml4_is_accessed(curr->pml4, victim->page->va))
            pml4_set_accessed (curr->pml4, victim->page->va, 0);
        else
            return victim;
    }

  for (start = list_begin(&frame_table); start != e; start = list_next(start)) {
        victim = list_entry(start, struct frame, frame_elem);
        if (pml4_is_accessed(curr->pml4, victim->page->va))
            pml4_set_accessed (curr->pml4, victim->page->va, 0);
        else
            return victim;
    }

	return victim;
}

이렇게 할당 받은 프레임은 vm_do_claim_page에서 사용된다. 할당 받은 프레임을 요청 받은 페이지와 연결 하는 함수이다. 가상 주소와 물리 주소간 연결은 pml4_set_page 함수를 통해 이루어지며 구조체 간의 연결은 vm_do_claim_page 내에서 이루어진다.

static bool
vm_do_claim_page (struct page *page) {
	struct frame *frame = vm_get_frame ();

	/* Set links */
	frame->page = page;
	page->frame = frame;

	/* TODO: Insert page table entry to map page's VA to frame's PA. */
	if(install_page(page->va,frame->kva,page->writable))
		return swap_in (page, frame->kva);

	return false;
}

이러한 페이지간 연결은 언제 발생할까? 페이지 폴트가 발생 하였을때 페이지를 요청하면서 발생한다. 이는 vm_claim_page를 통해 이루어진다. vm_claim_page에서 va를 이용하여 SPT 내의 페이지를 탐색한다. 이 페이지에 대한 프레임을 요청하게 되는 것이다.

bool
vm_claim_page (void *va UNUSED) {
	/* TODO: Fill this function */
	struct page *page = spt_find_page(&thread_current()->spt,va);
	if(page==NULL)
		return false;

	return vm_do_claim_page (page);
}

그렇다면 페이지 폴트가 발생하였을때 가상메모리가 이를 해결하는 과정을 알아야한다. exception.c의 페이지 폴트 함수를 살펴보면 페이지 폴트 발생 시 vm_try_handle_fault를 호출 한다. not_present → 물리 메모리에 존재 하지 않을 경우에 vm_claim_page를 통해 프레임을 할당 받게 된다. 나머지 stack_growth 함수는 뒤에서 다룰 예정이다.

/* 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 supplemental_page_table *spt UNUSED = &thread_current ()->spt;
	struct page *page = NULL;
	/* TODO: Validate the fault */
	/* TODO: Your code goes here */
	if (is_kernel_vaddr(addr)) {
        return false;
	}

	void *rsp_stack = is_kernel_vaddr(f->rsp) ? thread_current()->rsp_stack : f->rsp;
    if (not_present){
        if (!vm_claim_page(addr)) {
            if (rsp_stack - 8 <= addr && USER_STACK - 0x100000 <= addr && addr <= USER_STACK) {
                vm_stack_growth(thread_current()->stack_bottom - PGSIZE);
                return true;
            }
            return false;
        }
        else
            return true;
    }
    return false;

	
}

가장 아래의 함수부터 위의 함수까지 살펴 보았다. 이를 간단하게 정리해보면 다음과 같다. 페이지 폴트가 발생하면 vm_claim_page를 호출 한다. 이 함수는 spt에서 페이지를 탐색하여 물리 페이지와 연결해야 한다. 이는 vm_do_claim_page 함수에서 이루어진다. 만약 물리 프레임을 할당 받는 것은 vm_get_frame 함수에서 이루어지며 물리 프레임이 없을 경우 vm_evit_frame을 통해 프레임 하나를 swap out시킨다. 이와 같은 과정으로 핀토스는 페이지 폴트를 처리한다.