PintOS Project 3 - Virtual Memory (3) Stack Growth (정글사관학교 80일차 TIL)
하..현재 (2)에서 올 fail이 뜨는 상황이다..(혹시나 말하건대 제 글을 참조하며 코드를 짜는 분이 있다면 그러지 말라고 말씀을...그냥 개념 공부만 참조하세요..코드 다 터집니다..) 뒷 내용을 미리 땡겨 쓰다보니 터지지 않았을까 하는 작은 희망으로 무소의 뿔처럼 우직하게 일단 가본다.
Gitbook 정리는 여기 링크에 해뒀다.
1. Stack Growth 정리
이번 과제는 stack growth. 이전 글(개노답글)에서도 잠깐 써놨지만, 프로젝트 2까지는 유저 스택이 고정된 크기를 지녔다. 이는 코드를 보면 알 수 있는데
#ifndef VM
...
/* Create a minimal stack by mapping a zeroed page at the USER_STACK */
bool
setup_stack (struct intr_frame *if_) {
uint8_t *kpage;
bool success = false;
kpage = palloc_get_page (PAL_USER | PAL_ZERO);
if (kpage != NULL) {
success = install_page (((uint8_t *) USER_STACK) - PGSIZE, kpage, true);
if (success)
if_->rsp = USER_STACK;
else
palloc_free_page (kpage);
}
return success;
}VM에서 동작하는 케이스가 아닌 경우, setup_stack은 최소 크기의 스택을 생성하는데 이는 0으로 초기화된 한 페이지를 user stack으로 할당해주는 방식이었다. 즉, 이제부터는 page fault에 의해 스택 크기를 동적으로 할당해줄 것이다.
여기서 질문. 왜 stack을 동적으로 할당하는 게 스택 사이즈를 고정하는 것보다 좋을까? 미리 고정 할당해놓고 있으면 추가로 그때그때 얼마나 스택이 필요할지 알 수도 없을 뿐더러 다른 곳에 써야 할 수도 있을 빈 공간을 스택을 위해 공간 할당 해놓게 되면 빈 자리만 차지하니 효율성 측면에서도 나쁘다. 즉, 메모리 낭비라는 뜻.
그렇다면 이 스택은 언제 크기가 증가해야 할까? 앞서 글에서도 설명했던 것처럼 스택 역시 하나의 페이지이다. 정확히는 anonymous page. 유저 스택에는 유저 프로그램에서 함수가 호출되면 그 리턴값이 차곡차곡 쌓이게 될 텐데, 이 쌓이는 과정을 면밀히 들여다보면 결국 스택 페이지에 접근해 해당 내용을 작성하는 것이다. 이 과정은 스택 포인터인 rsp가 내려오면서 해당 위치에 정보를 넣는 것. 그런데 이 페이지에 접근하는 과정에서 스택에 정보가 쌓이다가 우리가 할당해준 영역 밑으로 rsp(스택 포인터)가 접근하면 page fault가 뜰 것이다. 우리가 할당해주지 않은 페이지이니까. 이때가 바로 stack growth가 발생하는 시점이 된다. 정확히는 stack growth에 대한 page fault가 발생하면 스택 사이즈를 증가(= 추가로 페이지를 할당)한다.
유저 가상 주소 공간에서 page fault가 발생하는 케이스 혹은 시스템 콜에서는 해당 프로세스의 인터럽트 프레임 내 rsp 멤버값을 그대로 사용해도 된다. 왜냐면 이 상황은 각각 유저 프로세스 <-> 운영체제 사이로만 왔다갔다 하지 다른 사용자 프로세스로 cpu가 넘어가는 케이스가 아니기 때문이다. 그렇기 때문에 page fault가 발생해 모드가 전환되면 유저 프로그램의 스택 포인터 값(유저 스택 포인터)은 intr_frame->rsp에 저장되어 page fault handler나 system call handler에 인자로 전달된다.
하지만 유효하지 않은 페이지에 접근해 page fault가 나는 케이스도 있다고 Gitbook에서 소개하는데, 이 경우는 커널 주소 공간에서 page fault가 발생했을 때이다. 문제는 이 경우에는 intr_frame으로부터 rsp(유저 스택 포인터)값을 전달받지 못하게 된다. 유저 프로세스가 돌고 있는 상황에서 page fault가 떴을 때는 해당 유저 스택 포인터 값을 intr_frame 내 rsp 멤버에 저장하지만, 커널 프로세스가 돌고 있는 상황에서 page fault가 뜨면 이때는 애초에 커널 영역이니 유저 영역의 스택 포인터를 intr_frame에 옮겨주는 과정이 없다. 그러니 이 케이스에서 page_fault()로 전달받은 intr_frame을 뒤져봤자 유저 스택 포인터를 찾을 수 없고 엉뚱한 값을 전달받게 된다. 이를 위해 GItbook에서 제시하는 방식은 유저 프로세스가 생성되고 커널로 최초의 transition이 일어났을 때 struct thread 구조체에 해당 rsp 주소값(유저 스택 포인터)을 구조체 내 멤버값으로 저장하는 방식을 설명한다. 마치 tss 내 rsp0가 커널 스택 포인터 값을 항상 들고 있는 것과 같은 맥락이라 볼 수 있다.
2. Stack Growth 관련 함수 구현
bool vm_try_handle_fault (struct intr_frame *f, void *addr, bool user, bool write, bool not_present) 수정
이제 page fault handler를 수정해보자. 위에서 설명했듯, 현재 우리가 할당해준 유저 스택의 맨 밑 주소값보다 더 아래에 접근하면 page fault가 발생한다. 이 page fault가 stack growth에 관련된 것인지 먼저 확인하는 과정을 추가한다. 맞다면 vm_stack_growth()를 호출해 스택에 추가 페이지를 할당해 크기를 늘린다.
참고 2: 프로세스가 스택을 위해 새 페이지를 필요로 할지 커널이 어떻게 알 수 있나요?
여기서 우리가 해결해야 할 문제는 다음과 같다.
1) 유저 스택 포인터를 어떻게 가져올 것인가?
인터럽트 프레임의 rsp 멤버가 유저 스택을 가리키고 있다면 이 스택 포인터를 그대로 사용해도 괜찮다. 하지만 인터럽트 프레임의 rsp 멤버가 커널 스택을 가리키고 있다면(커널 프로세스에서 page fault가 뜬 경우가 이에 해당한다) 우리가 원하는 것은 유저 스택을 키우는 것이니 앞서 첫번째로 유저 -> 커널로 transition이 일어날 때 thread 구조체 내 rsp 멤버로 저장하는 방식을 이용해 여기서 rsp 값을 가져온다.
2) fault가 발생한 주소가 유저 스택 내에 있는지
핀토스뿐만 아니라 대부분 OS는 유저 프로세스 당 스택 크기에 절대 상한을 두고 있다. UNIX는 유저에 맞게 limit이 달라지고, GNU/LINUX에서는 8MB로 제한을 두고 있다. 핀토스에서는 스택 사이즈가 반드시 1MB가 되어야 한다.
결국 핀토스에서는 총 스택 크기가 1MB(0x100000)이다. 따라서 page fault가 발생한 주소가 스택 관련 page fault인지 아닌지를 확인하려면 USER_STACK에서 밑으로 1MB 사이에 있는지를 체크해주면 된다. 설령 아직 할당받은 스택 사이즈(아래 이미지에서 빨간 사각형)가 1MB보다 작다 한들, USER_STACK(아래 이미지에서 빨간 사각형의 윗변에 해당)으로부터 아래 1MB까지의 영역은 무조건 스택 영역에 해당할 터이니, 초록색 1번 화살표는 유저 스택 내에 있는 것으로, 연두색 2번 화살표는 유저 스택이 아닌 다른 곳에서의 fault로 간주할 수 있게 된다.
여기서 우리는 한 가지를 더 하는 게 있는데, 스택 포인터가 stack 영역(stack 절대 크기)에 들어와있더라도 문제가 발생하는 케이스가 있다. Gitbook에는 이런 말이 나온다.
유저 프로그램은 이 프로그램이 스택 포인터 아래 영역의 스택에 write을 할 때 버그가 생긴다. 왜냐면 실제 OS는 스택에 데이터를 수정하는 시그널을 전달하기 위해 언제든지 프로세스에 인터럽트를 걸 수 있기 때문이다. 하지만, x86-64에서 PUSH 명령어는 스택 포인터 위치를 조정하기 전에 접근 권한을 체크하는데, 이는 스택 포인터 아래 8바이트 위치에서 page fault를 일으킨다.
스택에는 함수의 매개변수, 지역 변수 혹은 caller에 의해 호출된 callee 함수가 들어간다. 스택에서 push 인스트럭션이 작동하는 방식은 스택 포인터 위치를 8바이트 내리고 원래 스택 포인터 위치와 8바이트 내린 스택 포인터 사이에 주소값을 넣는 형태이다. 아래 그림을 보면 스택 top이 8바이트 아래로 내려가고 그 사이에 0x123이 들어간 것을 확인할 수 있다.
여기서 만약 해당 주소가 0x100보다 아래에 있다면 어떻게 될까? push 인스트럭션은 한 번에 8바이트씩만 내려가며 원래 위치와 8바이트 내려간 위치 사이에 주소값을 삽입하는 방식인데 그 아래에 주소값이 들어가게 되면 이는 정상적인 push 인스트럭션이 아니라고 간주할 수 있다. 이 경우에는 해당 주소값이 stack 절대 크기 영역 내에 있더라도 허용하면 안되는 케이스이므로 이 역시 차단한다.
이 page fault가 stack growth와 관련된 것임을 체크하면 그제야 vm_stack_growth()를 호출해 스택 사이즈를 늘린다.
/* Return true on success */
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;
//struct page *page = NULL;
/* TODO: Validate the fault */
/* TODO: Your code goes here */
/* 유저 가상 메모리 안의 페이지가 아니라면 여기서 끝내기*/
if (is_kernel_vaddr(addr)) {
return false;
}
/* 1. 유저 스택 포인터 가져오는 방법 => 이때 반드시 유저 스택 포인터여야 함!
모종의 이유로 인터럽트 프레임 내 rsp 주소가 커널 영역이라면 얘를 갖고 오는 게 아니라 thread 내에 우리가 이전에 저장해뒀던 rsp_stack(유저 스택 포인터)를 가져온다.
그게 아니라 유저 주소를 가리키고 있다면 f->rsp를 갖고 온다.
*/
void *rsp_stack = is_kernel_vaddr(f->rsp) ? thread_current()->rsp_stack : f->rsp;
/* 페이지의 present bit이 0이면, 즉 메모리 상에 존재하지 않으면
프레임에 메모리를 올리고 프레임과 페이지를 매핑시킨다.
*/
if (not_present) {
if(!vm_claim_page(addr)) {
// 여기서 해당 주소가 유저 스택 내에 존재하는지를 체크한다.
if (rsp_stack-8 <= addr && USER_STACK - 0x100000 <= addr && addr <= USER_STACK) {
vm_stack_growth(thread_current()->stack_bottom - PGSIZE);
return true;
}
return false;
}
else
return true;
}
return false;
}
thread.h/struct thread 구조체 수정
구조체 내에 stack bottom 위치와 스택 포인터(rsp_stack)을 저장할 수 있도록 멤버를 추가한다.
struct thread {
...
#ifdef VM
/* Table for whole virtual memory owned by thread. */
struct supplemental_page_table spt; // 이미 추가되어 있넹!
void *stack_bottom;
void *rsp_stack;
#endif
...
}
vm_stack_growth() 구현
스택의 맨 밑(stack_bottom)보다 1 PAGE 아래에 페이지를 하나 만든다. 이 페이지의 타입은 ANON이어야 한다(스택은 anonymous page!) 맨 처음 UNINIT 페이지를 만들고 SPT에 넣은 뒤, 바로 claim한다.
/* Growing the stack. */
static void
vm_stack_growth (void *addr UNUSED) {
/* stack에 해당하는 ANON 페이지를 UNINIT으로 만들고 SPT에 넣어준다.
이후, 바로 claim해서 물리 메모리와 맵핑해준다. */
if (vm_alloc_page(VM_ANON| VM_MARKER_0, addr, 1)) {
vm_claim_page(addr);
thread_current()->stack_bottom -= PGSIZE;
}
}