Pintos - Virtual Memory

Memory Management

현재 pintos에는 lazy loading이 구현되지 않은 상황이다. lazy loading을 구현하기 위해서는 특정 virtual address에 대응되는 page에 대한 정보가 추가적으로 필요하다. 각 page에 관한 정보를 담는 page 구조체를 생성하자. 또한, 이 page들을 supplemental page table이라는 hash table을 통해 관리했다. 추가적으로, user_pool이 가득 차서 page를 더이상 할당해줄 수 없는 경우 page의 정보들을 swap out&swap in 하는 코드까지 구현해 보았다.

page는 세가지의 type중 한 가지 종류로 정해지며, 최초에 할당되는 page는 lazy loading을 위한 uninit_page로 설정된다. 이 상태는 아직 memory에 실제로 load되지 않은 상태이다.(PTE에도 va와 pa가 연결되어있지 않다.) Program이 해당 page의 주소를 참조할 때 PTE에 아직 등록되어 있지 않음으로 (vogue)page fault가 발생하고, 이때 supplemental page table에서 해당 virtual address에 해당하는 page structure가 존재하는지 확인한다. page structure가 존재한다면, 그제서야 실제로 물리 메모리에 data를 load하는 과정이 일어나게 된다. type에 따라(VM_FILE or VM_ANON) 과정을 거친 후 program이 해당 주소를 다시 참조하게 되고, 이때는 물리 메모리에 load되어 있고, PTE에도 등록이 되어있는 상태임으로 page fault가 발생하지 않고 참조할 수 있게 된다!

 

Page Initialization with Lazy Loading

Lazy loading은 메모리가 실제로 필요한 시점 전까지 메모리 로드를 미룬다. page fault가 발생했는데, 해당 virtual address가 할당되어있는 경우 그제서야 contents들이 load되게 된다.

uninit상태를 제외하고 page의 type은 3가지가 존재한다. page_cache, anon_page 그리고 file_page이다. page_cache는 pintos project 4에서 구현할 예정이기 때문에, 여기서는 나머지 두가지 type에 대해서만 설명할 것이다.

 

file_page

file_page는 mmap함수를 통해 생성된 page들이다. load될때, page에 연결되어 있는 file의 일부분을 읽어오며, swap_out 혹은 destroy될 때, 해당 page의 dirty_bit가 켜져있다면,(수정 사항이 존재한다면) 해당 file에 수정사항을 반영한다.

mmap - file을 read, write하는 과정에서 계속 systemcall이 호출되는데, 이때 매번 context switching이 일어난다. mmap을 사용하면, 메모리에 직접 기록해놓고 수정하며, swap out, destroy혹은 munmap과정에서 수정 사항이 file에 반영됨으로 context switching에 드는 비용을 줄일 수 있다. 프로세스간에 mmap을 이용해서 데이터를 공유할 수도 있다.

anon_page

setup_stack 혹은 load과정에서 생성된다. file_page와 달리 특정 file과 matching되지 않는 page들이다. file로부터 읽어들인 정보가 저장될 수는 있지만, mmap을 통해 생성된 file_page와 달리 특정 file과 직접적으로 관련되어있지 않다. anon_page 는 file관련 정보를 별도로 지니고 있지 않다. 따라서, swap_out될때, disk에 page의 정보를 복사해 놓게된다. file에 수정사항이 반영되지도 않는다.

 

File_page의 lazy_loading 과정

[lazy_load를 위한 준비(실제 load X)]mmap systemcall이 호출되고, 해당 file의 정보를 별도의 구조체 내에 저장한 후 vm_alloc_page_with_initializer를 호출한다. 이 함수는 page구조체를 생성하고, lazy_load시에 호출할 함수(lazy_load_segment, file_initializer) & file의 정보를 담고 있는 구조체를 page 구조체 내에 저장한다. 이후, 이 page를 supplemental page table에 추가한다.

[page_fault발생 이후 실제 메모리에 load]File_page에 해당하는 주소에 접근하려는 시도가 발생하면 vouge page fault가 일어난다. exception handler에서 vm_handle_fault함수를 호출하고, supplemental page table에서 주소에 해당하는 page를 찾은 kernel은 handle 가능한 page fault임을 인지하고 vm_do_claim함수를 호출한다. 이 함수에서 물리 메모리와 1:1로 매핑되어있는 kva를 user_pool에서 할당해주고, frame에 kva를 담아 page와 연결해준다. 추가로, PTE(page table entry)에도 가상 주소와 물리 주소의 매핑을 생성한다. 이후, file_initializer와 lazy_load_segment가 실행되며 물리 메모리에 file의 정보가 load되게 된다.

program이 해당 addr에 다시 한 번 접근을 시도한다. 이때는 PTE에 addr가 등록되어있는 상태 이고, 물리 메모리에도 file의 내용들을 load해 놓았음으로, page fault가 발생하지 않고 원하는 정보에 접근할 수 있게 된다.

 

Anon_page의 lazy_loading 과정

File_page와 흐름은 거의 동일하다. 차이점은, vogue page fault가 발생한 이후 file_initializer함수 대신 anon_initializer함수가 호출된다는 점과, (stack 제외)file의 내용을 메모리에 load한 이후 file에 대한 정보를 더이상 지니고 있지 않는다는 점이다. 이 차이점 때문에 swap_out시에 작동하는 방식이 달라지게 된다.

차이점에 대해 얘기한 김에 조금 더 얘기해보자.

fork 시에 이 둘의 차이점이 더욱 극명하게 나타난다. (copy on write 구현 X)

File_page의 경우 자신과 연결된 file에 대한 정보를 모두 지니고 있음으로, fork시에 page를 복사해 갈때도 page구조체 내에 file에 대한 정보를 정확하게 담아놓고 spt에 추가해 놓으면 된다. 이후 page_fault가 발생하면 lazy_loading과정이 반복되며 메모리에 file의 내용이 load될 수 있다.

하지만, Anon_page의 경우 file과 연결되어있지 않고, 당연히 file에 대한 정보도 존재하지 않는다. uninit 시절의 file에 대한 정보를 굳이 제거하지 않았다면 남아있을 수는 있겠지만, 부모가 해당 page의 내용을 수정했을 경우 file의 내용을 다시 읽어오게 된다면, 부모의 내용과 달라지게 될 것이다.

실제 test-case중 한 가지인 args-none 실행 파일에 대한 program header를 살펴보자. 0x604d20에서 시작되는 bss segment도 VM_ANON으로 lazy_load되는 부분이다. 0번 segment의 text와 rodata(read only data)와는 달리 bss는 정적으로 할당되는 전역 변수가 할당되는 부분으로, 처음에는 0으로 초기화 되어있다가 프로그램이 실행되며 값이 변한다.

부모 프로세스가 이 부분의 변수에 특정 값을 입력해 주었는데, 자식이 args-none의 파일을 다시 읽어서 프로그램을 실행한다면, bss segment에 저장된 변수들의 정보가 제대로 전달되지 않을 것이다. 때문에, file과 직접적으로 연결되지 않는 ANON type page들의 경우 supplemental_page_table_copy함수에서 메모리의 정보들을 모두 복사해주는 방식으로 구현하였다. (copy_on_write는 아직 구현하지 않았다.)

ubuntu@ip-172-31-10-84:~/pintos_os_project/vm/build/tests/userprog$ readelf -Wl args-none

Elf file type is EXEC (Executable file)
Entry point 0x400c7f
There are 3 program headers, starting at offset 64

Program Headers:
  Type           Offset   VirtAddr           PhysAddr           FileSiz  MemSiz   Flg Align
  LOAD           0x000000 0x0000000000400000 0x0000000000400000 0x004d1a 0x004d1a R E 0x200000
  LOAD           0x004d20 0x0000000000604d20 0x0000000000604d20 0x000000 0x000530 RW  0x200000
  GNU_STACK      0x000000 0x0000000000000000 0x0000000000000000 0x000000 0x000000 RW  0x10

 Section to Segment mapping:
  Segment Sections...
   00     .text .rodata
   01     .bss                    <<---bss segment 0x604d20~
   02

 

 

lazy loading을 위한 구조체 & 함수

struct page

page를 할당할 때, page에 대한 정보를 관리하기 위한 structure를 만든다. supplemental page table(이하 spt)에 page structure를 넣어놓고 관리할 예정이다. spt는 hash_table로 구성된다. virtual address로부터 얻은 hash value에 해당하는 bucket은 list로 이루어져 있다.(같은 hash value를 가지는 page 구조체는 같은 bucket에 담긴다.) 따라서, page structure에도 hash_table의 bucket(linked_list)에 추가하기 위한 hash_elem을 추가해 주었다.

swap을 구현할 때, 어떤 page를 victim으로 삼아 swap out시킬 것인지 선택해야 한다. 이를 위한 victim_list를 사용할 예정인데, 이 list에 추가하기 위해 victim_elem도 구조체에 추가해 주었다.

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
    };
    bool writable;
    struct hash_elem hash_elem; 
    struct list_elem victim_elem; 
    enum vm_type vm_type;
};

struct frame

위에서 살펴본 struct page가 virtual memory의 page에 대한 정보를 관리하는 구조체였다면, struct frame은 physical memory의 page에 대한 정보를 관리하는 구조체이다. frame과 page는 서로가 서로의 주소를 저장하는 방식으로 연결되어 있다.

uninit type의 경우 물리메모리에 할당되어있지 않고, 당연히 자신의 va와 연결된 kva도 존재하지 않는다. 따라서 frame이 존재하지 않고, vogue page fault가 발생해 실제로 물리 메모리에 load되는 시점에 frame을 할당받는다.

va : virtual address (user영역에 존재하는 virtual address)

kva : kernel virtual address (kernnel 영역에 존재하는 virtual address)

struct frame {
  void *kva;
  struct page *page;
};

struct uninit_page

Lazy loading을 위한 page type이다. 물리 메모리에 load되어있지 않은 상태이며, bogue page fault가 발생할 때 비로소 특정 type으로 initialize&load된다.(이 과정은 page type별로 상이하다.)

void supplemental_page_table_init

supplemental_page_table을 사용하기 위해 먼저 hash_table을 초기화하는 함수를 만들어준다.

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

struct page *spt_find_page

va정보를 이용해 page structure의 시작 주소를 구해야 한다. 이때, page_lookup이라는 함수를 사용했는데, 이 함수가 굉장히 신기하다. 아래에서 살펴보자. 추가로, 함수에 입력되는 va값이 페이지단위로 align되어있는 상태이겠지만, 혹시 모를 상황을 대비해 ASSERT로 확인하는 코드를 추가해주었다.

struct page *
spt_find_page (struct supplemental_page_table *spt UNUSED, void *va UNUSED) {
    ASSERT(pg_round_down(va) == va);
    return page_lookup(va);
}

struct page *page_lookup

입력으로 받은 va와 동일한 주소값을 가지는 page구조체를 찾아주는 함수이다.

함수 내에서 page 구조체인 p를 추가한다. p.va에 함수의 인자로 받은 주소값을 넣어준 후에 hash_find함수의 인자로 p.hash_elem의 주소를 넘겨준다. p내부의 값들을 별도로 초기화하지 않고 va값만 넣어준 후에 p를 사용하고 있다. hash_find함수 내에서는 p.hash_elem의 주소를 사용해 page 구조체의 주소를 얻은 후에 이를 활용해 va의 값을 얻고, 이를 사용한다. page구조체의 다른 값에 접근하려 했다면, 문제가 생겼을 수도 있겟지만, va에 값을 입력하고 va값만 사용하기 때문에 이런 일들이 가능하다.

struct page *
page_lookup (const void *address) {
  struct page p;
  struct hash_elem *e;

  p.va = address;
  e = hash_find (&thread_current()->spt.hash_table, &p.hash_elem);
  return e != NULL ? hash_entry (e, struct page, hash_elem) : NULL;
}

bool spt_insert_page

supplemental page table에 page를 삽입하는 함수를 구현해보자. hash_insert함수에 &spt->hash_table,와 page->hash_elem을 입력해 spt의 hash_table에 page의 hash_elem을 삽입하자. hash_insert함수는 내부적으로 hash_table에 동일한 주소를 가지는 page의 hash_elem이 이미 추가되어 있는지 확인한다. 기존에 동일한 값을 가지는 page의 hash_elem이 존재하지 않으면 NULL을 반환하고, 존재한다면 기존에 삽입되어 있던 page의 주소를 반환한다. hash_insert의 반환값이 NULL이라면, 삽입이 잘 되었음을 의미함으로 true를 return해주자.

bool
spt_insert_page (struct supplemental_page_table *spt UNUSED,
        struct page *page UNUSED) {
    //?This function should checks that the virtual address does not exist in the given supplemental page table.
    if(hash_insert(&spt->hash_table, &page->hash_elem) == NULL)
        return true;
    return false;
}

static struct frame *vm_get_frame

user pool에서 page를 할당받은 후 frame struct에 해당 page의 시작 주소(kernel virtual address)를 할당한다. PAL_USER flag를 활용해 user pool에서 페이지를 할당 받을 수 있다.

user pool에서 더이상 할당해줄 수 있는 페이지가 없을 경우 vm_evict_frame함수를 호출해 하나의 page를 swap_out 시키고, 해당 page의 (kva가 담겨있는)frame을 반환한다.

static struct frame *
vm_get_frame (void) {
    void* p = palloc_get_page(PAL_USER);
    if(p == NULL)
        return vm_evict_frame();

    struct frame *frame = (struct frame*)malloc(sizeof(struct frame));
    if (frame == NULL) 
        PANIC("failed to allocate frame");

    frame->kva = p;
    frame->page = NULL;
    ASSERT (frame != NULL);
    ASSERT (frame->page == NULL);

    return frame;
}

static bool vm_do_claim_pag

메모리를 할당받아 frame을 page에 연결하고 page내에 저장되어있는 va와 frame내에 저장되어있는 kva를 페이지 테이블을 활용해 연결한다. 이후 page type별로 서로 다른 swap_in을 실행한다.

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

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

    bool writable = page->writable;
    int check = pml4_set_page(thread_current()->pml4, page->va, frame->kva, writable);

    list_push_back (&victim_table, &page->victim_elem);
    return swap_in (page, frame->kva);
}

bool vm_claim_page

위에서 만든 vm_do_claim_page와 vm_get_frame 함수를 사용해 va에 할당할 page를 얻고, frame과 page구조체를 구성한다. mmu와 spt에도 va와 연결되는 kva 그리고 page구조체를 할당해준다.

bool
vm_claim_page (void *va UNUSED) {
    struct page *page = (struct page*)malloc(sizeof(struct page));
    page->va = va;
    ASSERT(!spt_insert_page(&thread_current ()->spt, page));

    return vm_do_claim_page (page);
}

vm_alloc_page_with_initializer

load_segment에서 불리는 함수로, page 구조체를 생성하고, input으로 들어온 type에 맞게 initializer를 지정한다. 해당 page를 supplemental page table에 추가해 놓음으로써 lazy_loading을 위한 준비를 마친다. 추후에, vogue page fault가 났을 때 spt에서 해당 page를 찾고, page 구조체 내에 저장해 놓았던 initializer와 lazy_load_segment함수를 호출하게 된다.

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;

    /* Check wheter the upage is already occupied or not. */
    if (spt_find_page (spt, upage) == NULL) {
        /* TODO: Create the page, fetch the initialier 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* page = (struct page*)malloc(sizeof(struct page));
        ASSERT(page);

        bool (*initializer)(struct page *, enum vm_type, void *);
        switch(VM_TYPE(type)){
            case VM_ANON:
                initializer = anon_initializer;
                break;
            case VM_FILE:
                initializer = file_backed_initializer;            
                break;
            default:
                PANIC("###### vm_alloc_page_with_initializer [unvalid type] ######");
                break;
        }

        uninit_new(page, upage, init, type, aux, initializer);

        page->writable = writable;
        page->vm_type = type;

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