[Pintos-KAIST] Project 3 :: Memory Management

Pintos Project 3의 첫번째 과제인 Memory Management에서는
supplemental page table을 먼저 다루고,
Physical Memory와의 매핑하는 함수를 구현한다.

 

Implement Supplemental Page Table

• 현재 상태에서 Pintos는 가상 및 물리적 메모리 매핑을 관리하기 위한 페이지 테이블(pml4)을 가지고 있다.
• pml4 이외에 추가로, page fault 및 리소스 관리를 처리하기 위해 supplementary page table이 필요하다.

💡 Implement supplemental page table management functions in vm/vm.c.

0) supplemental page table

• hash table을 이용해서 supplementary page table을 구현한다.

supplemental_page_table에 hash 구조체를 추가한다.

/* vm.h */

/* Representation of current process's memory space.
 * We don't want to force you to obey any specific design for this struct.
 * All designs up to you for this. */
struct supplemental_page_table {
    struct hash spt_hash;
};

page 구조체에 hash_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 */

    /* Your implementation */
    struct hash_elem hash_elem;

    /* Per-type data are binded into the union.
     * Each function automatically detects the current union */
    union
    {
        struct uninit_page uninit;
        struct anon_page anon;
        struct file_page file;
#ifdef EFILESYS
        struct page_cache page_cache;
#endif
    };
};

1) supplemental_page_table_init()

• supplementary page table을 초기화한다.
• 이 함수는 새로운 프로세스가 시작될 때(initd in userprog/process.c)와 프로세스가 포크될 때(__do_fork in userprog/process.c) 호출된다.

spt를 초기화한다.

/* vm.c */

/* Initialize new supplemental page table */
void supplemental_page_table_init(struct supplemental_page_table *spt UNUSED)
{
    hash_init(spt, page_hash, page_less, NULL);
}

hash_init에 필요한 함수 page_hash를 선언한다.

/* vm.c */

/* Returns a hash value for page p. */
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);
}

hash_init에 필요한 함수 page_less를 선언한다.

/* vm.c */

/* Returns true if page a precedes page b. */
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;
}

2) spt_find_page()

• supplementary page table에서 va에 해당하는 구조체 페이지를 찾아 반환한다.

spt에서 va에 해당하는 page를 찾아서 반환한다.

/* vm.c */

/* Find VA from spt and return page. On error, return NULL. */
struct page *
spt_find_page(struct supplemental_page_table *spt UNUSED, void *va UNUSED)
{
    struct page *page = NULL;
    /* TODO: Fill this function. */
    page = malloc(sizeof(struct page));
    struct hash_elem *e;

    // va에 해당하는 hash_elem 찾기
    page->va = va;
    e = hash_find(&spt, &page->hash_elem);

    // 있으면 e에 해당하는 페이지 반환
    return e != NULL ? hash_entry(e, struct page, hash_elem) : NULL;
}

3) spt_insert_page()

• supplementary page table에 struct page를 삽입한다.
• 이때, 가상 주소가 이미 supplementary page table에 존재하는지 확인한다.
  • 존재한다면 삽입하지 않고, 존재하지 않으면 삽입한다.

spt에 page를 삽입한다.

/* vm.c */

/* Insert PAGE into spt with validation. */
bool spt_insert_page(struct supplemental_page_table *spt UNUSED,
                     struct page *page UNUSED)
{
    /* TODO: Fill this function. */
    return hash_insert(&spt, &page->hash_elem) == NULL ? true : false; // 존재하지 않을 경우에만 삽입
}

 

Frame Management

💡 Implement vm_get_frame, vm_claim_page and vm_do_claim_page in vm/vm.c.

4) vm_get_frame()

• palloc_get_page 함수를 호출하여 사용자 풀에서 새로운 physical page(frame)를 가져온다.
  • 물리 페이지를 할당하고, 해당 페이지의 커널 가상 주소를 반환하는 함수인 palloc_get_page를 사용한다.
• 사용자 풀에서 페이지를 성공적으로 가져오면, 프레임을 할당하고 해당 프레임의 멤버를 초기화한 후 반환한다.
• 페이지 할당을 실패할 경우, PANIC ("todo")로 표시한다. (swap out을 구현한 이후 변경한다.)

user pool에서 새로운 physical page를 가져와서 새로운 frame 구조체에 할당해서 반환한다.

/* vm.c */

/* palloc() and get frame. If there is no available page, evict the page
 * and return it. This always return valid address. That is, if the user pool
 * memory is full, this function evicts the frame to get the available memory
 * space.*/ 
static struct frame *
vm_get_frame(void)
{
    struct frame *frame = NULL;
    /* TODO: Fill this function. */
    void *kva = palloc_get_page(PAL_USER); // user pool에서 새로운 physical page를 가져온다.

    if (kva == NULL)   // page 할당 실패 -> 나중에 swap_out 처리
        PANIC("todo"); // OS를 중지시키고, 소스 파일명, 라인 번호, 함수명 등의 정보와 함께 사용자 지정 메시지를 출력

    frame = malloc(sizeof(struct frame)); // 프레임 할당
    frame->kva = kva;                      // 프레임 멤버 초기화

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

5) vm_do_claim_page()

• 인자로 주어진 page에 physical frame을 할당한다.
• 먼저, vm_get_frame 함수를 호출하여 프레임을 가져온다.
• 그런 다음 MMU를 설정한다.
  • 즉, 가상 주소와 물리 주소 간의 매핑을 페이지 테이블에 추가한다.

새 frame을 가져와서 page와 매핑한다.

/* vm.c */

/* Claim the PAGE and set up the mmu. */
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. */
    // 가상 주소와 물리 주소를 매핑
    struct thread *current = thread_current();
    pml4_set_page(current->pml4, page->va, frame->kva, page->writable);

    return swap_in(page, frame->kva); // uninit_initialize
}

6) vm_claim_page()

• 이 함수는 주소 va에 해당하는 page로 vm_do_claim_page 함수를 호출한다.
• 먼저, va에 해당하는 page(virtual page)를 가져온다.
• 그 다음, 해당 페이지로 vm_do_claim_page를 호출한다.

spt에서 va에 해당하는 페이지를 가져와서 frame과의 매핑을 요청한다.

/* vm.c */

/* Claim the page that allocate on VA. */
// va로 page를 찾아서 vm_do_claim_page를 호출하는 함수
bool vm_claim_page(void *va UNUSED)
{
    struct page *page = NULL;
    /* TODO: Fill this function */
    // spt에서 va에 해당하는 page 찾기
    page = spt_find_page(&thread_current()->spt, va);
    if (page == NULL)
        return false;
    return vm_do_claim_page(page);
}