[Pintos] Virtual Memory 구현하기 Part1: Lazy Load 방식으로 프로그램 실행하기 (Memory Management, Anonymous Page, Stack Growth)

Virtual Memory 구현하기 Part1: Lazy Load 방식으로 프로그램 실행하기 (Memory Management, Anonymous Page, Stack Growth) 

Pintos Project3 Virtual Memory의 경우, Project1, 2에 비해 난이도가 상당히 높아졌는데요. 그럼에도 불구하고 선배 기수 분들이 정리를 잘 해주셔서 난관에 부딪혔을 때 참고해서 헤쳐나갈 수 있었습니다. 다만 블로그에 잘못된 코드가 올라가 있는 경우가 있어 적절히 수정하면서 적용해 나가야 했던 점이 아쉬웠는데, 이런 점을 없애보자는 취지로 구현 과정만 다이렉트로 정리해 보려고 합니다.

 

※ 주의: 제 컴퓨터 기준에서는, All Pass가 뜨는 것을 확인했으나, 다른 조원들의 컴퓨터에서 page-merge.* 테스트가 간헐적으로 실패하는 것을 확인했습니다. 따라서 그대로 적용하기보다는, 참고만 하시는 것을 추천드립니다.

 

Memory Management

(1) SPT(Supplemental Page Table) 인터페이스 추가하기 (vm.h)

해시 모듈 참조 추가하기

#include <hash.h>	// hash 함수 모듈

기존 spt 구조체에 hash 추가하기

struct supplemental_page_table {
	struct hash spt_hash;	// spt 해시 구조체
};

기존 page 구조체에 hash_elem 추가하기

/* Your implementation 아래에 추가 */
struct hash_elem hash_elem;

 

(2) supplemental_page_table_init 구현하기 (vm.c)

/* 보조 페이지 테이블 spt를 해시 테이블로 초기화 */
void
supplemental_page_table_init (struct supplemental_page_table *spt UNUSED) {
	// page_hash: 해시 함수, page_less: 비교 함수 사용
	hash_init(&spt->spt_hash, page_hash, page_less, NULL);
}

 

(3) 헬퍼 함수: page_hash, page_less 구현하기 (vm.c)

헬퍼 함수 선언 추가하기

/* vm.c 위쪽에 함수 선언 추가 */
uint64_t page_hash(const struct hash_elem *e, void *aux);
bool page_less(const struct hash_elem *a, const struct hash_elem *b, void *aux);

page_hash 구현하기

/* page의 va를 기준으로 해시 값을 계산 */
uint64_t 
page_hash(const struct hash_elem *p_, void *aux UNUSED) {
    // 해시 요소에서 struct page 포인터 추출
    const struct page *p = hash_entry(p_, struct page, hash_elem);

    // va 값을 바이트 단위로 해싱하여 해시값 반환
    return hash_bytes(&p->va, sizeof p->va);
}

page_less 구현하기

/* 두 page의 va를 비교하여 정렬 순서를 결정 (va 기준 오름차순) */
bool
page_less(const struct hash_elem *a_,
           const struct hash_elem *b_, void *aux UNUSED) {
    // 해시 요소에서 struct page 포인터 추출
    const struct page *a = hash_entry(a_, struct page, hash_elem);
    const struct page *b = hash_entry(b_, struct page, hash_elem);

    // va 기준으로 작은 쪽이 먼저 오도록 비교
    return a->va < b->va;
}

 

(4) spt_find_page 구현하기 (vm.c)

/* SPT에서 va에 해당하는 page 구조체를 찾아 반환 */
struct page *
spt_find_page (struct supplemental_page_table *spt UNUSED, void *va UNUSED) {
	// 해시 탐색용 임시 페이지
	struct page page;

	// va를 페이지 기준 주소로 정렬
    page.va = pg_round_down(va);

	// 해당 주소에 대응하는 page를 해시 테이블에서 탐색
    struct hash_elem *e = hash_find(&spt->spt_hash, &page.hash_elem);

	// 찾으면 page 반환, 없으면 NULL
    return e != NULL ? hash_entry(e, struct page, hash_elem) : NULL;
}

 

(5) spt_insert_page 구현하기 (vm.c)

/* spt에 page를 삽입. 이미 존재하면 실패 */
bool
spt_insert_page (struct supplemental_page_table *spt UNUSED,
		struct page *page UNUSED) {
	// 삽입 성공 시 NULL 반환 → true, 실패(중복) 시 false
	return hash_insert(&spt->spt_hash, &page->hash_elem) == NULL;
}

 

(6) spt_remove_page 구현하기 (vm.c)

/* spt에서 page를 제거하고 메모리 해제 */
void
spt_remove_page (struct supplemental_page_table *spt, struct page *page) {
	// 해시 테이블에서 page 제거
	hash_delete(&spt->spt_hash, &page->hash_elem);

	// page 메모리 해제
	vm_dealloc_page(page);
}

 

(7) Frame Table 인터페이스 추가

frame table용 전역 변수 선언하기 (vm.c)

struct list frame_table;	// 현재 할당된 frame 추적, 관리용 리스트
struct lock frame_lock;		// frame table 접근 동기화를 위한 전역 락

frame table용 전역 변수 초기화하기 (vm.c)

// vm_init의 #endif 아래 맨 밑에 추가
list_init(&frame_table);
lock_init(&frame_lock);

기존 frame 구조체에 list_elem 추가하기 (vm.h)

// kva, page 필드 아랫줄에 추가
struct list_elem frame_elem;

 

(8) vm_get_frame 구현하기 (vm.c)

/* 새로운 frame을 할당하거나 필요 시 교체하여 반환 */
static struct frame *
vm_get_frame (void) {
	// frame 구조체 동적 할당
	struct frame *frame = (struct frame *)malloc(sizeof(struct frame));
	ASSERT (frame != NULL);

	// 사용자 영역용 물리 페이지 할당 (0으로 초기화)
	frame->kva = palloc_get_page(PAL_USER | PAL_ZERO);  

	// 할당 실패 시, frame을 하나 선택해 교체
    if (frame->kva == NULL) {
        frame = vm_evict_frame();
	} else {
        // frame 테이블에 추가
        lock_acquire(&frame_lock);
        list_push_back(&frame_table, &frame->frame_elem);
		lock_release(&frame_lock);
	}

	// 초기에는 매핑된 page 없음
    frame->page = NULL;

	ASSERT (frame->page == NULL);
	return frame;
}

 

(9) vm_claim_page 구현하기 (vm.c)

/* 주어진 va에 해당하는 page를 찾아 물리 메모리에 매핑 */
bool
vm_claim_page (void *va UNUSED) {
	// SPT에서 va에 해당하는 page 찾기
	struct page *page = spt_find_page(&thread_current()->spt, va);

	// 없다면 실패
    if (page == NULL)
        return false;

	// page를 실제 물리 메모리에 매핑
	return vm_do_claim_page(page);
}

 

(10) vm_do_claim_page 구현하기 (vm.c)

/* page에 frame을 할당하고 물리 메모리에 매핑 및 데이터 로드 */
static bool
vm_do_claim_page (struct page *page) {
	// 새 frame 할당
	struct frame *frame = vm_get_frame();

	/* 연결 설정 */
	frame->page = page;
	page->frame = frame;

	// 가상 주소(page->va)와 물리 주소(frame->kva) 매핑
    if (!pml4_set_page(thread_current()->pml4, page->va, frame->kva, page->writable))
        return false;

	// 디스크나 swap 영역에서 실제 데이터 로드
	return swap_in(page, frame->kva);
}

mmu 모듈 참조 추가하기 (vm.c)

#include "threads/mmu.h"	// pml4 함수 모듈

기존 page 구조체에 writable 추가하기 (vm.h)

// hash_elem 아랫줄에 추가
bool writable;

 

 

Anonymous Page

(1) vm_alloc_page_with_initializer 구현하기 (vm.c)

/* 초기화 함수와 함께 새로운 가상 페이지를 생성하고 SPT에 삽입 */
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;

	/* 이미 매핑된 페이지가 없는 경우에만 진행 */
	if (spt_find_page(spt, upage) == NULL) {

		// 새 page 구조체 동적 할당
		struct page *page = malloc(sizeof(struct page));
		if (!page)
			return false;

		// 타입별 초기화 함수 선택
		typedef bool (*initializer_by_type)(struct page *, enum vm_type, void *);
		initializer_by_type initializer = NULL;

		switch (VM_TYPE(type)) {
		case VM_ANON:
			initializer = anon_initializer;
			break;
		case VM_FILE:
			initializer = file_backed_initializer;
			break;
		}

		// uninit page 생성 및 초기화 정보 등록
		uninit_new(page, upage, init, type, aux, initializer);
		page->writable = writable;

		// SPT에 삽입 후 성공 여부 반환
		return spt_insert_page(spt, page);
	}
}

 

(2) lazy_load_arg 구조체 추가하기 (vm.h)

struct lazy_load_arg {
	struct file *file;
	off_t ofs;
	uint32_t read_bytes;
	uint32_t zero_bytes;
};

 

(3) load_segment 구현하기 (VM전용, process.c)

/* 파일의 segment를 lazy loading 방식으로 메모리에 매핑 */
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;
		// 나머지는 0으로 채움
		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;

		// lazy loading용 uninit 페이지 할당
		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;
}

 

(4) lazy_load_segment 구현하기 (VM전용, process.c)

/* page fault 시 호출되어 파일 내용을 물리 메모리에 로드 */
bool
lazy_load_segment(struct page *page, void *aux) {
	// 파일 읽기 정보가 담긴 구조체로 변환
	struct lazy_load_arg *lazy_load_arg = (struct lazy_load_arg *)aux;

	// 파일 오프셋 설정
	file_seek(lazy_load_arg->file, lazy_load_arg->ofs);

	// 파일에서 read_bytes만큼 읽어 page의 물리 메모리(kva)에 저장
	if (file_read(lazy_load_arg->file, page->frame->kva, lazy_load_arg->read_bytes) 
		!= (int)(lazy_load_arg->read_bytes))
	{
		// 실패 시 물리 페이지 해제 후 false 반환
		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;
}

 

(5) setup_stack 구현하기 (VM전용, process.c)

/* 사용자 스택 할당 및 초기 rsp 설정 */
static bool
setup_stack(struct intr_frame *if_) {
	bool success = false;

	// 스택의 첫 페이지 주소 (USER_STACK에서 한 페이지 아래)
	void *stack_bottom = (void *)(((uint8_t *)USER_STACK) - PGSIZE);

	// 스택 페이지를 SPT에 등록
	if (vm_alloc_page(VM_ANON | VM_MARKER_0, stack_bottom, 1))
	{
		// 물리 프레임을 실제로 할당
		success = vm_claim_page(stack_bottom);
		if (success)
			// rsp를 스택 최상단(USER_STACK)으로 설정
			if_->rsp = USER_STACK;
	}
	return success;
}

기존 thread 구조체에 stack_pointer 추가하기 (thread.h)

/* thread.h - thread 구조체의 spt 아래에 추가 */
void *stack_pointer;

 

(6) vm_try_handle_fault 구현하기 (vm.c)

/* 페이지 폴트 발생 시, 유효한 접근이면 페이지를 메모리에 매핑 */
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;

	// 유효하지 않은 주소(커널 영역 or NULL) 접근은 처리 불가
	if (addr == NULL || is_kernel_vaddr(addr))
		return false;

	// 접근한 페이지가 존재하지 않아 발생한 폴트인 경우
	if (not_present) {
		// SPT에서 해당 주소에 대한 페이지 정보 탐색
		struct page *page = spt_find_page(spt, addr);
		if (page == NULL)
			return false;

		// 쓰기 권한 없는 페이지에 대한 쓰기 접근은 처리 불가
		if (write && !page->writable)
			return false;

		// 페이지 실제 물리 메모리에 매핑
		return vm_do_claim_page(page);
	}
	return false;
}

 

(7) supplemental_page_table_copy 구현하기 (vm.c)

/* src SPT의 내용을 dst SPT로 복사 */
bool
supplemental_page_table_copy(struct supplemental_page_table *dst UNUSED,
		struct supplemental_page_table *src UNUSED) {
	
	// src SPT 해시 테이블을 순회할 반복자 초기화
	struct hash_iterator i;
	hash_first(&i, &src->spt_hash);

	while (hash_next(&i)) {
		// 현재 항목의 page 정보 가져오기
		struct page *src_page = hash_entry(hash_cur(&i), struct page, hash_elem);
		enum vm_type src_type = src_page->operations->type;

		if (src_type == VM_UNINIT) {
			// lazy load용 uninit 페이지는 메타데이터만 복사
			vm_alloc_page_with_initializer(
				src_page->uninit.type,
				src_page->va,
				src_page->writable,
				src_page->uninit.init,
				src_page->uninit.aux);
		} else {
			// 이미 초기화된 페이지는 새로 할당하고 데이터 복사
			if (vm_alloc_page(src_type, src_page->va, src_page->writable) &&
				vm_claim_page(src_page->va)) {
				struct page *dst_page = spt_find_page(dst, src_page->va);
				memcpy(dst_page->frame->kva, src_page->frame->kva, PGSIZE);
			}
		}
	}
	return true;
}

 

(8) supplemental_page_table_kill 구현하기 (vm.c)

/* SPT의 모든 페이지를 제거하고 메모리 해제 */
void
supplemental_page_table_kill(struct supplemental_page_table *spt UNUSED) {
	// 해시 테이블 전체 삭제, 각 항목은 hash_page_destroy로 정리
	hash_clear(&spt->spt_hash, hash_page_destroy);
}

 

(9) 헬퍼 함수: hash_page_destroy 구현하기 (vm.c)

헬퍼 함수 선언 추가하기

// vm.c 위쪽에 함수 선언 추가
void hash_page_destroy(struct hash_elem *e, void *aux);

hash_page_destroy 구현하기

/* 해시 테이블에서 페이지 제거 시 호출되는 정리 함수 */
void 
hash_page_destroy(struct hash_elem *e, void *aux) {
    // hash_elem에서 page 구조체 포인터 추출
    struct page *page = hash_entry(e, struct page, hash_elem);

    // 페이지 내부 자원 해제 (frame, swap 등)
    destroy(page);

    // page 구조체 자체 메모리 해제
    free(page);
}

 

(10) check_page(사용자 주소 검증 함수) 수정하기 (validate.c)

참고로 validate.c는 기본 Pintos-kaist 디렉터리에는 존재하지 않는데요. 사용자 주소 검증을 위한 함수들을 모아놓기 위해 따로 만든 파일입니다. 다른 레퍼런스를 참고한다면, synch.c의 check_addr 함수 등을 변경해야 합니다.

/* uaddr가 유저 영역 주소이며 매핑된 페이지가 존재하는지 확인 */
static bool
check_page(const void *uaddr) {
	// NULL이거나 커널 영역 주소면 잘못된 접근
    if (uaddr == NULL || !is_user_vaddr(uaddr)) {
        return false;
    }

#ifdef VM
    // VM이 활성화된 경우, SPT에서 페이지 존재 여부 확인
    struct thread *curr = thread_current();
    struct page *page = spt_find_page(&curr->spt, uaddr);

    // 존재하면 true
    if (page != NULL) return true;

    return false;

#else
    // VM 미사용 시, 직접 page table에서 매핑 여부 확인
    return pml4_get_page(thread_current()->pml4, uaddr) != NULL;
#endif
}

 

(11) page fault 조건 수정하기 (exception.c)

#ifdef VM
	// 페이지 폴트 처리 실패 시 → 프로세스 종료
	if (vm_try_handle_fault (f, fault_addr, user, write, not_present)) {
		return;
	} else {
		sys_exit(-1);
	}
#endif

여기까지 구현이 끝나면, Page Fault로 인해 실행부터 막혔던 프로그램들이 정상적으로 실행되면서, 기본적인 테스트 수행이 가능하게 됩니다.

 

 

Stack Growth

(1) vm_try_handle_fault 수정하기 (vm.c)

/* 페이지 폴트 발생 시, SPT 또는 스택 확장을 통해 처리 시도 */
bool
vm_try_handle_fault(struct intr_frame *f, void *fault_addr,
                    bool user, bool write, bool not_present) {
    struct thread *t = thread_current();
    struct supplemental_page_table *spt = &t->spt;

    // NULL이거나 커널 주소면 잘못된 접근 → 처리 실패
    if (fault_addr == NULL || is_kernel_vaddr(fault_addr))
        return false;

    // SPT에서 fault_addr에 해당하는 페이지 검색
    struct page *page = spt_find_page(spt, fault_addr);

    // 접근이 존재하는 페이지에 대한 쓰기일 경우 → 처리 불가
    if (!not_present && write)
        return false;

    // 해당 페이지가 존재하면 처리 시도
    if (page != NULL) {
        // 쓰기 불가능한 페이지에 쓰기 접근 → 실패
        if (write && !page->writable)
            return false;

        // 실제 페이지 할당 및 매핑 시도
        return vm_do_claim_page(page);
    }

    // SPT에 없는 경우: 스택 확장 가능한 상황인지 확인
    void *rsp = user ? f->rsp : t->stack_pointer;
    bool can_grow =
        fault_addr >= STACK_LIMIT &&       // 최소 스택 크기 제한
        fault_addr < USER_STACK &&         // 유저 영역 내
        fault_addr >= rsp - 32;            // rsp 기준 접근 가능 범위

    // 조건 만족 시 스택 확장
    if (can_grow)
        return vm_stack_growth(fault_addr);

    // 그 외의 경우 처리 실패
    return false;
}

vm_try_handle_fault용 매크로 추가하기

/* 스택은 최대 1 MiB, USER_STACK 기준 아래로 확장할 수 있다. */
#define STACK_LIMIT (USER_STACK - (1 << 20))

/* 최대 몇 바이트까지 rsp 아래 접근을 스택 성장으로 허용할지. 
   8 바이트(단일 push) + 여유를 주고 싶다면 32로 늘릴 수 있다. */
#define STACK_GROW_GAP 32

 

(2) vm_stack_growth 구현하기 (vm.c)

기존 void로 반환값이 없었지만, bool 값을 반환하도록 변경해줍니다.

/* fault 주소를 기준으로 스택 영역을 한 페이지 확장 */
static bool
vm_stack_growth(void *addr UNUSED) {
    bool success = false;

	// 페이지 단위로 정렬
	addr = pg_round_down(addr);

    // 새 스택 페이지를 SPT에 등록
    if (vm_alloc_page(VM_ANON | VM_MARKER_0, addr, true)) {
        // 실제 물리 메모리 할당 및 매핑
        success = vm_claim_page(addr);

        if (success) {
			return true;
        }
    }
	return false;
}

 

(3) sys_read 실패 조건 추가하기 (syscall.c)

// sys_read의 validate_ptr 아랫줄에 추가
#ifdef VM
    // buffer가 SPT에 등록되어 있고, 쓰기 불가능한 페이지인 경우 → 비정상 종료
    struct page *page = spt_find_page(&thread_current()->spt, buffer);
    if (page && !page->writable)
        sys_exit(-1);
#endif

 

(4) syscall_handler에서 스레드 rsp 갱신 처리하기 (syscall.c)

// syscall_handler 시작 부분에 추가
#ifdef VM
    // 현재 스레드의 커널 스택 포인터를 유저 컨텍스트의 rsp로 저장
    thread_current()->stack_pointer = f->rsp;
#endif

 

(5) check_page(사용자 주소 검증 함수) 수정하기 (validate.c)

추가로 스택 확장 조건에 해당하는지에 대해 검사합니다.

// if (page != NULL) return true; 와 return false; 사이에 추가
// 그 외에는 스택 확장 조건인지 확인
void *rsp = curr->stack_pointer;
if ((uaddr >= rsp - 8 || uaddr >= rsp) && uaddr <= USER_STACK) {
    return true;
}