Goals
- Annoymous Page 구현
- Lazy Loading 구현
What is a Annoymous Page
-
annoymous page란 non-disk 기반 이미지이다.
-> 어떤 파일과도 연결되지 않은 페이지를 의미 -
파일로부터 매핑되지 않은, 커널로부터 할당된 페이지를 뜻한다.
파일에 매핑되어있지 않기 때문에 0으로 초기화된 값을 담고 있다. -
anonymous mapping은 백업 파일이나 장치가 없다.
file-backed 페이지와 달리 명명된 파일 소스가 없기 때문에 익명이다.
익명 페이지는 스택 및 힙과 같은 실행 파일에 사용된다.
What is a Lazy loading(Demand paging)
Lazy load란 프로세스가 실행을 시작할 때, 필요한 메모리 부분만 메인 메모리에 로드시켜놓고,
나머지 메모리에 대해서는 필요할 때 요청을 보내면, 물리메모리에 로드 시키는 방식이다.
여기서의 요청은 Page Fault이다.
조금 더 설명을 덧 붙이면, 프로세스가 mmap()으로 커널에게 annonymous page를 할당 요청할 경우
커널은 프로세스에게 가상 메모리 주소 공간을 부여해준다.
하지만 이 가상 메모리 주소와 연결된 실제 물리 메모리 공간은 할당이 되지 않은 상태이다.
실제 물리 메모리 공간이 할당되는 시점은 유저 프로세스가 해당 메모리에 접근을 시도 할 때,
이루어지는데 해당 실제 물리 메모리 공간은 할당되지 않은 상태이므로 Page Fault가 발생하면서,
물리 메모리에서 빈 frame을 찾아 할당해서 가상 메모리 주소 공간과 물리 메모리 주소 공간을 연결해준다.
현재 Pintos의 가상 주소 공간 초기화 과정은 위의 그림과 같이, 디스크로 부터 ELF 이미지 세그먼트를
물리 메모리로 읽어들이는 방식이다.
하지만, 모든 내용을 물리 메모리에 올리는 방식은 물리 메모리의 낭비를 초래하기 때문에 Lazy load 방식을 적용해야 한다.
- Page table에서 해당 가상주소에 해당하는 물리 프레임의 주소를 찾는다.
- 해당 물리 프레임 주소에 필요한 정보가 로드되어 있는지 체크한다.
- 없다면 Page Fault 발생.
- Page Fault Handler에 의해 Page fault가 발생한 주소로 spt에서 페이지를 검색한다.
- spt에는 해당 페이지가 어떤 파일 유형을 저장하고 있는지 기억하고 있는데,(anon or file-backed)
해당 파일 유형에 맞추어 프레임을 할당해준다. - 물리 프레임을 할당해준 뒤, 작업을 다 마쳤다고 signal을 보내고, 해당 프로세스는 ready_que의 제일 뒤로 들어간다.
- 이후 해당 프로세스가 CPU를 잡았을 때, 요청했던 정보가 메인 메모리에 load된 상태이므로 해당 물리 메모리 주소에 접근할 수 있다.
Page initialization process in Lazy loading
이제는 spt에 필요한 정보들을 넣어서 Page Fault가 발생했을 때(페이지가 요청됐을 때)가 되어서야
메모리에 load하는 lazy load 방식으로 변경할 것이다.
lazy loading에서 페이지 초기화 과정은 어떻게 진행될까?
-
커널이 새 페이지를 만들어달라는 요청을 받으면
vm_alloc_page_with_initializer()가 호출된다.
새 페이지 구조체를 할당받고 초기화한 다음, 페이지 타입에 맞는초기화 함수를 설정한다.
그 후 다시 유저 프로그램에게 제어권을 넘긴다. -
유저 프로그램이 실행되면 접근하려는 페이지 안에 아직 내용물이 없기 때문에 Page Fault가 일어난다.
따라서 Page Fault가 호출되고, uninit_initialize가 호출되어 앞에서 설정한초기화 함수가 호출된다.
Anon page의 경우anon_initializer를,
File-backed page의 경우file_backed_initializer를 부른다.
하나의 페이지의 사이클은 다음과 같다.
초기화 → Lazy Loading(Page Fault → Lazy load → Swap-in → Swap-out) → Destroy
struct page {
...
union {
struct uninit_page uninit; // uninit page
struct anon_page anon; // annoymous page
struct file_page file; // file-backed page
...
};맨 처음 페이지가 만들어지면 모두 VM_UNINIT 타입으로 만들고, 그 후 ANON 타입이나 FILE-BACKED 타입으로 변환한다.
그 전에 해당 페이지에 프로그램이 접근하려 하면 page fault가 발생하고 초기화를 진행해주어야 한다.
Implement
STEP1 : Uninitialized Page 구현
vm_alloc_page_with_initializer
인자로 주어진 TYPE에 맞추어 Unintialized Page를 하나 만든다.
추후 이 페이지에 대해 Page Fault가 발생하여 초기화되기 전까지는 UNINIT 타입으로 존재한다.
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;
upage = pg_round_down(upage);
/* Check wheter the upage is already occupied or not. */
if (spt_find_page(spt, upage) == NULL)
{
/* 새 페이지를 만들어서 page 구조체의 멤버를 채운다. */
struct page *page = (struct page *)calloc(1, sizeof(struct page));
/* 함수 포인터를 사용하여 TYPE에 맞는 페이지 초기화 함수를 저장한다. */
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:
goto err;
}
uninit_new(page, upage, init, type, aux, initializer);
page->writable = writable;
/*새로 만든 UNINIT 페이지를 프로세스의 spt에 넣는다. */
return spt_insert_page(spt, page);
}
err:
return false;
}맨 처음 페이지를 만들면 해당 페이지는 UNINIT 페이지이다.
ANON 타입으로 만들어졌지만 아직 UNINIT일수도 있고, FILE-BACKED로 만들어졌지만 아직 UNINIT일 수도 있다.
그 후 uninit_new()를 통해 인자로 받은 설정들로 페이지 구조체의 멤버들을 채워준다.
그리고 프로세스의 spt에 해당 페이지를 넣어준다.
하지만, 이 페이지는 아직 해당 타입으로 초기화가 된 상태가 아니다.
나중에 Page Fault가 발생했을 때, 각 타입에 맞는 초기화 함수를 호출하게 될 것이다.
static bool uninit_initialize (struct page page, void kva)
첫번째 fault에서 페이지를 초기화하는 함수이다.
모든 페이지들은 맨 처음 만들어질 때 UNINIT으로 만들어진다.
그리고 프로세스가 해당 페이지에 첫 접근시 Page Fault가 발생하고, Page fault handler는
해당 페이지를 swap_in하는데, UNINIT 타입일 때의 swap_in 함수가 바로 이 함수이다.
static bool
uninit_initialize (struct page *page, void *kva) {
struct uninit_page *uninit = &page->uninit;
/* Fetch first, page_initialize may overwrite the values */
vm_initializer *init = uninit->init;
void *aux = uninit->aux;
/* 해당 페이지의 타입에 맞도록 페이지를 초기화한다. */
/* 만약 해당 페이지의 segment가 load되지 않은 상태면 lazy load 해준다.
init이 lazy_load_segment일 때! */
return uninit->page_initializer (page, uninit->type, kva) && (init ? init (page, aux) : true);
}static bool load_segment ()
기존의 load_segment에서 물리 페이지를 할당하고 맵핑하는 부분 삭제하고,
vm_alloc_page_with_initializer에 인자로 넣어줄 aux를 동적 할당하고,해당 구조체에 멤버를 설정해준다.
가상 페이지가 요구될 때, 읽어야할 파일의 오프셋과 크기, 마지막에 패딩할 제로 바이트 등을 넣어준다.
이 정보들은 실제 Page Fault가 발생했을 때, 해당 파일의 정보들로 lazy_load를 수행한다.
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) {
/* Do calculate how to fill this page.
* We will read PAGE_READ_BYTES bytes from FILE
* and zero the final PAGE_ZERO_BYTES bytes. */
size_t page_read_bytes = read_bytes < PGSIZE ? read_bytes : PGSIZE;
size_t page_zero_bytes = PGSIZE - page_read_bytes;
/* TODO: Set up aux to pass information to the lazy_load_segment. */
struct segment *seg = calloc(1, sizeof(struct segment));
seg->file = file;
seg->offset = ofs;
seg->page_read_bytes = page_read_bytes;
seg->page_zero_bytes = page_zero_bytes;
void *aux = seg;
if (!vm_alloc_page_with_initializer (VM_ANON, upage, writable, lazy_load_segment, aux)){
free(seg);
return false;
}
/* Advance. */
read_bytes -= page_read_bytes;
zero_bytes -= page_zero_bytes;
ofs += page_read_bytes;
upage += PGSIZE;
}
return true;
}
struct segment {
struct file *file;
off_t offset;
size_t page_read_bytes;
size_t page_zero_bytes;
};static bool lazy_load_segment (struct page page, void aux)
실제 lazy_load를 수행하는 함수이다.
위의 load_segment에서 넣어줬던 aux가 인자로 들어오는데, 이를 가져와 실제로 디스크에서 file을 읽고
메모리에 적재해준다.
static bool
lazy_load_segment (struct page *page, void *aux) {
/* TODO: Load the segment from the file */
/* TODO: This called when the first page fault occurs on address VA. */
/* TODO: VA is available when calling this function. */
// struct file* file = thread_current()->running;
struct segment *load_src = aux;
off_t offset = load_src->offset;
size_t page_read_bytes = load_src->page_read_bytes;
size_t page_zero_bytes = load_src->page_zero_bytes;
struct file* file = load_src->file;
file_seek(file, offset);
if (file_read(file, page->frame->kva, page_read_bytes) != (int)page_read_bytes) {
// palloc_free_page(page);
return false;
}
memset(page->frame->kva + page_read_bytes, 0, page_zero_bytes);
free(load_src);
return true;
}
static bool setupstack(struct intr_frame *if) 수정
새로운 메모리 관리 시스템에 맞는 스택 할당을 위해 setup_stack을 조정해야 한다.
첫 번째 스택 페이지는 lazy loading이 필요 없기 때문에, Page Fault를 기다릴 필요 없이, 커맨드라인 인자를 사용하여 할당하고 초기화할 수 있다.
따라서 스택을 구분하는 방법이 필요하다. VM_MARKER를 통해 ANON이면서 STACK인 anon_page를 마킹해준다.
static bool
setup_stack (struct intr_frame *if_) {
bool success = false;
void *stack_bottom = (void *) (((uint8_t *) USER_STACK) - PGSIZE); // 시작점
// struct thread* t = thread_current();
/* TODO: Map the stack on stack_bottom and claim the page immediately.
* TODO: If success, set the rsp accordingly.
* TODO: You should mark the page is stack. */ // do_claim_frame -> initial
/* TODO: Your code goes here */
/* 추가 */
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;
}STEP2 : Supplemental Page Table - Revisit 구현
supplemental page table 인터페이스에 다시 방문하여, copy 및 clean up 기능을 구현해야한다.
프로세스를 생성(구체적으로 자녀 프로세스 생성)하거나 파괴할 때 필요하기 때문이다.
bool supplemental_page_table_copy
src에서 dst로 supplemental page table을 복사한다.
이 함수는 fork에서 자식들이 부모의 실행 컨텍스트를 상속받아야 할 때 사용된다.
hash iterator를 사용하여 src의 테이블에 있는 각 페이지를 돌면서 각 파일 유형에 맞추어 dst에 복사해준다.
bool supplemental_page_table_copy(struct supplemental_page_table *dst UNUSED,
struct supplemental_page_table *src UNUSED)
{
struct hash_iterator i;
hash_first(&i, &src->pages);
while (hash_next(&i))
{
struct page *p = hash_entry(hash_cur(&i), struct page, hash_elem);
enum vm_type type = p->operations->type;
void *va = p->va;
bool writable = p->writable;
struct aux_data *aux_dt = calloc(1, sizeof(struct aux_data));
switch (VM_TYPE(type))
{
case VM_UNINIT:
memcpy(aux_dt, p->uninit.aux, sizeof(struct aux_data));
if (!vm_alloc_page_with_initializer(p->uninit.type, va, writable, p->uninit.init, aux_dt))
{
free(aux_dt);
return false;
}
break;
case VM_ANON:
case VM_FILE:
free(aux_dt);
if (!(vm_alloc_page(type, va, writable) && vm_claim_page(va)))
{
return false;
}
struct page *page = spt_find_page(dst, va);
memcpy(page->frame->kva, p->frame->kva, PGSIZE);
break;
default:
PANIC("SPT COPY PANIC!\n");
break;
}
}
return true;
}void supplemental_page_table_kill
supplemental page table이 보유한 모든 리소스를 해제한다.
이 함수는 프로세스가 종료될 때(process_exit()) 호출된다.
void supplemental_page_table_kill(struct supplemental_page_table *spt UNUSED)
{
hash_destroy(&spt->pages, page_destructor);
}