PintOS Project3 - Virtual Memory 1편

1. Memory Management

구현 1번 (complete)

void supplemental_page_table_init (struct supplemental_page_table *spt);

- supplemental_page_table의 데이터 구조는 Hash를 선택

 

void supplemental_page_table_init (struct supplemental_page_table *spt UNUSED) {
    hash_init (&spt->spt_hash, page_hash, page_less, NULL);
}

unsigned page_hash (struct hash_elem *elem, void *aux UNUSED) {
    // hash_entry: 해당 hash_elem을 가지고 있는 page를 리턴하는 함수
    struct page *page = hash_entry(elem, struct page, hash_elem);

    // hash_bytes: 해당 page의 가상 주소를 hashed index로 변환하는 함수
    return hash_bytes(&page->va, sizeof(page->va));
}

bool page_less (struct hash_elem *elema, struct hash_elem *elemb, void *aux UNUSED) {
    // page_less: 두 page의 주소값을 비교하여 왼쪽 값이 작으면 True 리턴하는 함수

    struct page *pagea = hash_entry(elema, struct page, hash_elem);
    struct page *pageb = hash_entry(elemb, struct page, hash_elem);

    return pagea->va < pageb->va;
}

hash_init	- 해시 테이블을 초기화하는 함수 - 1번째 인자 (struct hash *h) : 초기화할 Hash table - 2번째 인자 (hash_hash_func *) : 해시값을 구해주는 함수의 포인터 - 3번째 인자 (hash_less_func *) : 해시 element들의 크기를 비교해주는 함수의 포인터
hash_entry	- 이전에 사용했던 list_entry와 같은 기능을 함
hash_bytes	- 해당 page의 가상 주소를 hashed index로 변환하는 함수 - 첫번째 인자에 있는 두번째 인자만큼의 Size의 해시를 반환한다.

 

---

구현 2번 (complete)

struct page *spt_find_page (struct supplemental_page_table *spt, void *va);

- spt에서 va에 해당하는 페이지를 찾는다. 실패하면 NULL을 반환한다.

 

struct page *spt_find_page (struct supplemental_page_table *spt UNUSED, void *va UNUSED) {
    // spt_find_page: spt에서 va가 있는지를 찾는 함수, hash_find() 사용


    struct page *page = (struct page *)malloc(sizeof(struct page));
    // pg_round_down: 해당 va가 속해 있는 page의 시작 주소를 얻는 함수
    page->va = pg_round_down(va);

    // hash_find: Dummy page의 빈 hash_elem을 넣어주면, va에 맞는 hash_elem을 리턴해주는 함수 (hash_elem 갱신)
    struct hash_elem *e = hash_find(&spt->spt_hash, &page->hash_elem);

    free(page);

    return e == NULL ? NULL : hash_entry(e, struct page, hash_elem);
}

pg_round_down	- 주석 설명 : 가장 가까운 페이지 경계로 내림을 한다. - 페이지 크기(보통 4096바이트, 4KB)로 정렬된 주소를 의미합니다. - 예를 들어, 주소 0x12345가 주어지면, 이는 페이지 크기인 0x1000(4096)으로 나눴을 때 가장 가까운 하위 경계인 0x12000으로 내림됩니다. * 그냥 va를 넣어주면 왜 안될까? 경계에 맞춰서 va가 안들어오는 경우도 있을까???     · 페이지의 크기(hash의 크기)는 4KB로 고정이다.     · 4KB 공간 중에 쓰기도 중간부터 쓰기가 될 수도 있기에 hash의 시작점을 확인해야 한다.
hash_find	- 해시 테이블에서 element를 검색 - 첫번째 인자 (structy hash *) - 두번째 인자 (struct hash_elem *)

---

구현 3번 (complete)

bool spt_insert_page (struct supplemental_page_table *spt, struct page *page);

- spt에 page를 삽입한다.

- 이 함수는 가상 주소가 주어진 spt에 존재하지 않는지 확인해야 한다.

 

bool spt_insert_page (struct supplemental_page_table *spt UNUSED, struct page *page UNUSED) {
    return hash_insert(&spt->spt_hash, &page->hash_elem) == NULL ? true : false; // 존재하지 않을 경우에만 삽입
}

hash_insert

- NEW를 해시 테이블에 삽입하고 동일한 요소가 이미 테이블에 없으면 null 포인터를 반환합니다. - 동일한 요소가 이미 테이블에 있으면 NEW를 삽입하지 않고 그 요소를 반환합니다.

---

구현 4번 (complete)

static struct frame *vm_get_frame (void);

- 'palloc_get_page'를 호출하여 사용자 풀에서 새로운 물리 페이지를 가져온다.

- 사용자 풀에서 페이지를 성공적으로 가져오면, 프레임을 할당하고, 그 멤버들을 초기화한 후 반환합니다. 

    · 사용할 수 있는 페이지가 없으면 페이지를 evict하여 반환한다.

    · 이 함수는 항상 유효한 주소를 반환해야하기 때문이다.

- 'vm_get_frame'을 구현한 후에는 모든 사용자 공간 페이지 할당(PALLOC_USER)을 이 함수를 통해 수행한다.

- 현재는 페이지 할당 실패 시 스왑 아웃을 처리할 필요는 없습니다. 그런 경우에는 "todo"와 함께 PANIC으로 표시만 하면 됩니다.

 

static struct frame *vm_get_frame (void) {
    struct frame *frame = (struct frame*)malloc(sizeof(struct frame));
    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;
}

PAL_USER	- 커널 풀 대신 유저 풀에서 메모리를 할당 받기 위함
vm_evict_frame	- 한 페이지를 축출하고 해당하는 프레임을 반환한다. 오류가 발생하면 NULL을 반환한다.

---

구현 5번 (complete)

bool vm_do_claim_page (struct page *page);

- 페이지를 할당한다는 것은 물리적 프레임을 할당한다는 의미이다.

- 먼저 'vm_get_frame'을 호출하여 프레임을 가져온다.

- 그런 다음 MMU를 설정해야 한다.

- 즉, 페이지 테이블의 가상 주소와 물리 주소 간의 매핑을 추가하고, 반환 값은 작업 성공 여부를 반환한다.

 

static bool vm_do_claim_page (struct page *page) {
    struct frame *frame = vm_get_frame ();
    if (frame == NULL) return false;

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

    /* Insert page table entry to map page's VA to frame's PA. */
    struct thread *curr = thread_current();
    bool success = (pml4_get_page (curr->pml4, page->va) == NULL && pml4_set_page (curr->pml4, page->va, frame->kva, page->writable));

    return success ? swap_in(page, frame->kva) : false;
}

pml4_get_page	- 인자 : (uint64_t *pml4, const void *uaddr) - pml4에서 사용자 가상 주소 uaddr에 해당하는 물리 주소를 찾는다. - 해당 물리 주소에 대응하는 커널 주소를 반환하거나, uaddr이 매핑되지 않았을 경우 Null Pointer를 반환한다.
pml4_set_page	- 인자 : (uint64_t *pml4, void *upage, void *kpage, bool rw) - 사용자 가상 페이지 upage에서 커널 가상 주소 kpage로 식별된 물리 프레임까지의 매핑을 pml4에 추가한다. - upage는 이미 매핑되어 있으면 안된다. - kpage는 일반적으로 palloc_get_page()를 사용하여 사용자 풀에서 얻은 페이지이여야 한다. - rw가 true인 경우 새로운 페이지는 읽기/쓰기가 가능하고, false면 읽기 전용이다. - 메모리 할당에 성공하면 true, 실패하면 false를 반환한다.
swap_in	- 물리적 메모리(RAM)에 없는 페이지를 디스크의 스왑영역에서 가져오는 역할

---

구현 6번 (complete)

bool vm_claim_page (void *va);

- 할당할 가상 주소(va)를 지정하여 페이지를 요청한다.

- 먼저 페이지를 가져온 다음 해당 페이지를 가지고 'vm_do_claim_page'를 호출한다.

 

bool vm_claim_page (void *va UNUSED) {
    // 프레임을 페이지에 할당하는 함수

    struct page *page = spt_find_page(&thread_current()->spt, va);
    if (page == NULL) false;

    return vm_do_claim_page (page);
}

 

---

2. Anonymous Page

* 페이지 수명 주기 : 초기화 → (page_fault → lazy_load → swap_in →swap_out → ...)  → destroy

 

구현 1번 (complete)

bool vm_alloc_page_with_initializer (enum vm_type type, void *va,
        bool writable, vm_initializer *init, void *aux);

- 커널이 새 페이지 요청을 받을 때 호출된다.

- 초기화되지 않은 페이지의 swap_in 핸들러는 페이지를 타입에 따라 자동으로 초기화하고, 주어진 AUX를 사용하여 INIT을 호출한다.

- 페이지 구조체를 생성한 후, 해당 페이지를 프로세스의 supplement_page_table에 삽입한다.

- 'vm.h' 에 정의된 'VM_TYPE' 매크로를 사용을 추천한다.

 

bool vm_alloc_page_with_initializer (enum vm_type type, void *upage, bool writable, vm_initializer *init, void *aux) {
    // 타입에 따라 적절한 이니셜라이져를 가져와 uninit_new를 호출하는 함수

	ASSERT (VM_TYPE(type) != VM_UNINIT)

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

	/* Check wheter the upage is already occupied or not. */
	if (spt_find_page (spt, upage) == NULL) {
		/* Create the page, fetch the initialier according to the VM type,
		 * and then create "uninit" page struct by calling uninit_new. You
		 * should modify the field after calling the uninit_new. */
            struct page* page = (struct page*)malloc(sizeof(struct page));

            // uninit_new를 호출해 "uninit" 페이지 구조체를 생성
            switch(VM_TYPE(type)) {
                case VM_ANON:
                    uninit_new(page, upage, init, type, aux, anon_initializer);
                    break;
                case VM_FILE:
                    uninit_new(page, upage, init, type, aux, file_backed_initializer);
                    break;
             }
             page->writable = writable;

             /* Insert the page into the spt. */
             return spt_insert_page(spt, page);
	}
err:
	return false;
}

 

uninit_new

- 첫번째 인자로 넘겨준 page에 나머지 인자들의 값들을 다 세팅해주는 함수

---

구현 2번 (No touch)

static bool uninit_initialize (struct page *page, void *kva);

- 페이지 폴트 핸들러는 호출 체인을 따라 진행되며, 결국 swap_in을 호출할 때 unint_initialize에 도달한다.

- PintOS에서는 이를 위한 완전한 구현을 제공하지만, 설계에 따라 unint_initialize를 수정해야 할 수도 있다.

 

- 첫 번째 페이지 폴트가 발생했을 때 페이지를 초기화한다.

- 템플릿 코드는 먼저 'vm_initializer'와 'aux'를 가져와 함수 포인터를 통해 해당하는 'page_initializer'를 호출한다

 

---

구현 3번 (No touch) - 2편에서 구현

void vm_anon_init (void);

- 익명 페이지 서브 시스템을 초기화한다.

- 이 함수에서는 익명 페이지와 관련된 모든 설정을 할 수 있다.

 

---

구현 4번 (No touch) - 2편에서 구현

bool anon_initializer (struct page *page,enum vm_type type, void *kva);

- 이 함수는 먼저 'page->operations'에서 익명 페이지의 핸들러를 설정한다.

- 현재 비어 있는 구조체인 'anon_page'에 일부 정보를 업데이트해야 할 수도 있다.

- 이 함수는 익명 페이지(VM_ANON)의 초기화 프로그램으로 사용된다.

 

---

구현 5번 (complete)

static bool load_segment (struct file *file, off_t ofs, uint8_t *upage,
        uint32_t read_bytes, uint32_t zero_bytes, bool writable);

- 현재 코드는 파일에서 읽을 바이트 수와 메인 루프 내에서 0으로 채울 바이트 수를 계산한다.

- 그런 다음 'vm_alloc_page_with_initializer'를 호출하여 대기 중인 객체를 생성한다.

    · 'aux' 인수로서 보조 값을 설정해야 한다.

    · 바이너리를 로드하는 데 필요한 정보를 포함하는 구조체를 생성하는 것이 좋습니다.

 

- 즉, lazy_load_segment에서 사용해야 하는 인자들을 aux 값으로 전달해야 한다.

/* process.h */
// Project 3: Lazy Load
struct container {
    struct file *file;
    off_t offset;
    size_t read_bytes;
};


/* process.c */
static bool load_segment (struct file *file, off_t ofs, uint8_t *upage, uint32_t read_bytes, uint32_t zero_bytes, bool writable) {
    ...
    /* Set up aux to pass information to the lazy_load_segment. */
    struct container *container = (struct container *)malloc(sizeof(struct container));
    container->file = file;
    container->offset = ofs;
    container->read_bytes = page_read_bytes;
    ...
}

---

구현 6번 (complete)

static bool lazy_load_segment (struct page *page, void *aux);

- 'load_segment'에서 'lazy_load_segment'가 'vm_alloc_page_with_initializer'의 네 번째 인수로 제공된다는 것을 볼 수 있다.

- 이 함수는 실행 파일의 페이지를 초기화하는 역할하며, 페이지 폴트가 발생할 때 호출된다.

- 이 함수는 페이지 구조체와 'aux'를 인수로 받는다. 'aux'는 'load_sement'에서 설정한 정보이다.

- 이 정보를 사용하여 세그먼트를 읽어올 파일을 찾아 결국 세그먼트를  메모리를 읽어와야 한다.

 

static bool lazy_load_segment (struct page *page, void *aux) {
	/* Load the segment from the file */
	/* This called when the first page fault occurs on address VA. */
	/* VA is available when calling this function. */

    struct container *container = (struct container *)aux;

    struct file *file = container->file;
    off_t offsetof = container->offset;
    size_t read_bytes = container->read_bytes;
    size_t zero_bytes = PGSIZE - read_bytes;
    
    // Page load
    file_seek(file, offsetof); // file의 위치를 offsetof으로 변경
    if (file_read(file, page->frame->kva, read_bytes) != (int)read_bytes) {
        palloc_free_page(page->frame->kva);
        return false;
    }
    memset(page->frame->kva + read_bytes, 0, zero_bytes);

    return true;
}

file_seek	- file의 Current Position 을 offsetof 위치로 변경
file_read	- file을 read_bytes 만큼 읽어서 page->frame->kva에 저장한다.
memset	- 첫 번째 인자 void * ptr은 세팅하고자 하는 메모리의 시작주소 - 두 번째 인자 value는 메모리에 세팅하고자 하는 값 - 세 번째 인자 size_t num은 길이를 뜻한다. - returns 성공시 첫 번째 인자로 들어간 ptr, 실패시 NULL - page->frame->kva + read_bytes 부터 0으로 zero_bytes 만큼 세팅한다.

---

구현 7번 (complete)

bool setup_stack (struct intr_frame *if_);

- 새로운 메모리 관리 시스템에 맞게 스택 할당을 맞춰야 한다.

-  vm/vm.h의 vm_type에 있는 보조 마커(예: VM_MARKER_0)를 사용하여 페이지를 표시할 수 있습니다.

 

- 스택바닥에 스택을 매핑하고 페이지를 즉시할당한다.

- 성공하면 rsp를 그에 맞게 설정해야 한다.

- 페이지가 스택임을 표시해야 한다.

 

bool setup_stack (struct intr_frame *if_) {
    bool success = false;
    void *stack_bottom = (void *) (((uint8_t *) USER_STACK) - PGSIZE);

    struct thread *thread = thread_current();

    // vm_alloc_page: type, upage, writable
    if (vm_alloc_page(VM_ANON | VM_MARKER_0, stack_bottom, 1)) {
        success = vm_claim_page(stack_bottom);

        if (success) {
            if_->rsp = USER_STACK;
        }
    }
    return success;
}

vm_alloc_page	- vm_alloc_page_with_initializer 함수를 호출하여 페이지를 할당하는 기능을 단순화한다. - 페이지타입, 사용자 공간 주소, 쓰기 가능여부를 인자로 받고 나머지 인자는 NULL 설정하여 호출한다.
VM_MARKER_0	- 정보 저장을 위한 보조 비트 플래그 마커를 의미 - 스택이 저장된 메모리 페이지임을 식별하기 위해 추가
vm_claim_page	- 프레임을 페이지에 할당하는 함수 - stack_bottom이 spt에 할당되어 있다면 해당 페이지와 프레임을 페이지 테이블에 매핑시킨다.

---

구현 8번 (complete)

bool vm_try_handle_fault (struct intr_frame *f UNUSED, void *addr UNUSED, bool user UNUSED, bool write UNUSED, bool not_present UNUSED);

- 페이지 폴트 발생하면 (page_fault in userproog/exception.c)는 제어권을 해당 함수로 넘긴다.

- 가짜 오류인 경우 일부 내용을 페이지에 로드하고 제어권을 사용자 프로그램으로 반환한다

    · 1. 지연로드

    · 2. 스왑 아웃 페이지

    · 3. 쓰기 금지 페이지

- 지연 로딩에 대한 페이지 오류인 경우 커널은 vm_alloc_page_with_initializer 세그먼트를 지연 로딩하기 위해 이전에 설정한 초기화 프로그램 중 하나를 호출한다.

 

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;

	/* Validate the fault */
    if (addr == NULL || is_kernel_vaddr(addr)) return false;

    if (not_present) {
        page = spt_find_page(spt, addr);
        if (page == NULL) return false;
        if (write == 1 && page->writable == 0) return false;
        return vm_do_claim_page(page);
    }
    return false;
}

is_kernel_vaddr(addr)	- 가상 메모리 주소는 유저 영역에 있어야 하기 때문이다.
not_present	- 이 함수에서 할당된 물리 프레임이 존재하지 않아서 발생한 예외일 경우 true를 전달받는다. - SPT에서 페이지 확인 후 해당 페이지에 물리 프레임 할당(vm_do_claim_page) - false인 상황은 물리 프레임이 할당되어 있지만 page fault가 일어난 것     · 그 경우는 read-only page에 write한 경우이기에 false를 반환     · true인 경우에도 read-only page에 write 요청할 경우가 있을수도 있어서 valid check

---

구현 9번 (complete)

bool supplemental_page_table_copy (struct supplemental_page_table *dst,
    struct supplemental_page_table *src);

- 부모의 실행 컨텍스트를 자식이 상속해야 할 때(즉, fork()를 사용할 때) src에서 dst로 보충 페이지 테이블을 복사한다.

- src의 보충 페이지 테이블의 각 페이지를 순회하며 dst의 보충 페이지 테이블에 해당 항목의 정확한 복사본을 만든다.

- 초기화되지 않은 페이지를 할당하고 즉시 요청해야 할 것이다.

 

bool supplemental_page_table_copy (struct supplemental_page_table *dst UNUSED, struct supplemental_page_table *src UNUSED) {
    // scr에서 dst로 SPT을 복사하는 함수

    struct hash_iterator iterator;
    hash_first(&iterator, &src->spt_hash);

    while (hash_next(&iterator)) {
        // hash_cur: 현재 elem을 리턴하거나, table의 끝인 null 포인터를 반환하거나
        struct page *parent_page = hash_entry(hash_cur(&iterator), struct page, hash_elem);

        enum vm_type type = parent_page->operations->type;
        void *upage = parent_page->va;
        bool writable = parent_page->writable;

        // 1) type이 uninit이면
        if (type == VM_UNINIT) {
            vm_initializer *init = parent_page->uninit.init;
            void *aux = parent_page->uninit.aux;
            vm_alloc_page_with_initializer(VM_ANON, upage, writable, init, aux);
            continue;
        }

        // 2) type이 uninit이 아니면
        if (!vm_alloc_page(type, upage, writable)) {
            // init이랑 aux는 Lazy Loading에 필요함
            // 지금 만드는 페이지는 기다리지 않고 바로 내용을 넣어줄 것이므로 필요 없음
            return false;
        }

        // vm_claim_page으로 요청해서 매핑 & 페이지 타입에 맞게 초기화
        if (!vm_claim_page(upage)) {
            return false;
        }

        // 매핑된 프레임에 내용 로딩
        struct page *dst_page = spt_find_page(dst, upage);
        memcpy(dst_page->frame->kva, src_page->frame->kva, PGSIZE);
    }
    return true;
}

hash_iterator	- a hash table iterator.
hash_first	- void hash_first (struct hash_iterator *, struct hash *);
hash_next	- struct hash_elem *hash_next (struct hash_iterator *);
memcpy	- src_page->frame->kva를 dst_page->frame->kva에 PGSIZE 만큼 복사한다.

 

---

구현 10번 (complete)

void supplemental_page_table_kill (struct supplemental_page_table *spt);

- 보조 페이지 테이블에 의해 유지되던 모든 자원을 해제한다.

- 이 함수는 프로세스가 종료될 때 호출된다. (userprog/process.c 내의 process_exit())

- 테이블 내의 페이지 항목을 순회하며, 테이블에 있는 페이지에 대해 destroy(page)를 호출해야 한다.

    · 이 함수에서는 실제 페이지 테이블(pml4)과 물리 메모리(palloc으로 할당된 메모리)에 대해 걱정할 필요가 없다.

    · 호출자가 보조 페이지 테이블이 정된 후에 이들을 청소한다.

 

void supplemental_page_table_kill (struct supplemental_page_table *spt UNUSED) {
    hash_clear(&spt->spt_hash, hash_page_destroy);
}

void hash_page_destroy(struct hash_elem *e, void *aux) {
    struct page *page = hash_entry(e, struct page, hash_elem);
    destroy(page);
    free(page);
}

---

구현 11번 (No touch)

static void uninit_destroy (struct page *page);

- page 구조체에 의해 유지되는 자원을 해제한다.

- 페이지의 vm 타입을 확인하고 그에 따라 적절하게 처리할 필요가 있다.

 

static void uninit_destroy (struct page *page) {
    // uninit page가 보유한 리소스를 해제하는 함수

    struct uninit_page *uninit UNUSED = &page->uninit;

    struct container *container = (struct container *)(uninit->aux);
    file_close(&container->file);
}

---

구현 12번 (No touch)

static void anon_destroy (struct page *page);

- 익명 페이지에 의해 유지되던 자원을 해제한다.

- 페이지 구조체를 명시적으로 해제할 필요는 없으면 호출자가 이를 처리해야 한다.

 

---

* 다음 내용들을 전부 구현한다면 project 2의 테스트들은 pass 한다.

* No touch 관련 구현은 구현하지 않아도 project 2 관련 테스트들은 동작한다.

    · vm_anon_init : 2편에서 구현

    · anon_initializer : 2편에서 구현

    · uninit_destroy

    · anon_destroy

 

* 테스트를 돌려보면 project2의 일부분 테스트가 fail이 뜬다. 해결 방법으로 밑의 코드를 주석 처리해준다.

    · 페이지 테이블에 유저 영역의 주소도 매핑되기 때문에 주석처리 해준다.

void check_address(void *addr) {
    ...
    // 해당 페이지맵은 커널 가상 주소에 대한 매핑을 가지고 있지만, 사용 주소에 대한 매핑은 없다.
    // if (pml4_get_page(thread_current()->pml4, addr) == NULL)
    //     exit(-1);
}