Stack Growth
Gitbook👇
프로젝트 2에서 스택은
USER_STACK에서 시작하는 단일 페이지였으며, 프로그램은 이 크기(4KB)로 제한하여 실행했습니다. 이제 스택이 현재 크기를 초과하면 필요에 따라 추가 페이지를 할당합니다.
추가 페이지는 스택에 접근하는 경우에만 할당합니다. 스택에 접근하는 경우와 아닌 경우를 구별하는 휴리스틱을 고안하세요.
당신은 User Program의 스택 포인터의 현재 값을 얻을 수 있어야 합니다. System Call 또는 User Program에 의해 발생한 Page Fault 루틴에서 각각syscall_handler()또는page_fault()에 전달된struct intr_frame의 rsp멤버에서 검색할 수 있습니다. 잘못된 메모리 접근을 감지하기 위해 Page Fault에 의존하는 경우, 커널에서 Page Fault가 발생하는 경우도 처리해야 합니다. 프로세스가 스택 포인터를 저장하는 것은 예외로 인해 유저 모드에서 커널 모드로 전환될 때 뿐이므로page_fault()로 전달된struct intr_frame에서 rsp를 읽으면 유저 스택 포인터가 아닌 정의되지 않은 값을 얻을 수 있습니다. 유저 모드에서 커널 모드로 전환 시 rsp를 struct thread에 저장하는 것과 같은 다른 방법을 준비해야 합니다.
Page Fault가 스택을 증가시켜야하는 경우에 해당하는지 아닌지를 확인해야 합니다. 스택 증가로 Page Fault를 처리할 수 있는지 확인한 경우, Page Fault가 발생한 주소로
vm_stack_growth()를 호출합니다.
유저 스택에는 rsp를 내리고 그 자리에 함수의 리턴값이 쌓이게된다. 이 과정에서 할당해준 영역 밑으로 스택 포인터가 접근하게 되면 page fault가 발생한다. 그 때 스택을 늘려줘야(페이지 추가 할당)한다.
대부분의 운영체제는 유저 프로세스 당 스택 크기에 상한을 두고있다. 예를 들어 GNU/LINUX는 8MB로 제한을 두고 있지만 핀토스에서는 스택 사이즈가 1MB가 되어야 한다. 제일 먼저 Pagefault가 발생한 주소가 스택을 조회하려던 것인지 8 바이트 아래 주소를 확인해준다. 유효한 pagefault면 vm_stack_growth()를 통해 스택을 늘려준다. 그리고 페이지가 매핑되지 않았다면(not_present) 프레임과 페이지를 링크 해준다.
/* 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;
/* -- Project 3 -- */
struct page *page = spt_find_page(spt, addr);
/* Validate the fault */
if(is_kernel_vaddr(addr))
return false;
uint16_t STACK_LIMIT = USER_STACK - (1<<20);
uint64_t limit = f->rsp - 8;
if(page == NULL && limit == addr) {
if(f->rsp > STACK_LIMIT && USER_STACK > f->rsp) {
while(limit <= thread_current()->stack_bottom) {
vm_stack_growth(thread_current()->stack_bottom - 8);
thread_current()->stack_bottom -= PGSIZE;
}
return true;
}
return false;
}
if(page && not_present)
return vm_do_claim_page(page);
return false;
}/* Growing the stack. */
static void
vm_stack_growth (void *addr UNUSED)
{
/* -- Project 3 -- */
vm_alloc_page(VM_ANON | VM_MARKER_0, addr, true);
}Memory Mapped Files
Memory Mapped Files - overview
In this section, you will implement memory-mapped pages. Unlike anonymous pages, memory-mapped pages are file-backed mappings. The contents in the page mirror data in an existing file. If a page fault occurs, a physical frame is immediately allocated and the contents are copied into the memory from the file. When memory-mapped pages are unmapped or swapped out, any change in the content is reflected in the file.
mmap() system call
Gitbook👇
메모리 매핑된 파일에 대한 두 가지 시스템 호출인 mmap 및 munmap을 구현합니다. VM 시스템은 mmap 영역에서 페이지를 lazy load하고 mmap된 파일 자체를 매핑을 위한 백업 저장소로 사용해야 합니다. 이 두 시스템 콜을 구현하려면 vm/file.c에 정의된
do_mmap()과do_munmap()을 구현해서 사용해야 합니다.
#include <sys/mman.h>
void *mmap(void *addr, size_t lengthint " prot ", int " flags ,
int fd, off_t offset);int munmap(void *addr, size_t length);
mmap()creates a new mapping in the virtual address space of the calling process. The starting address for the new mapping is specified in addr. The length argument specifies the length of the mapping.
If addr is NULL, then the kernel chooses the address at which to create the mapping; this is the most portable method of creating a new mapping. If addr is not NULL, then the kernel takes it as a hint about where to place the mapping;
/* -- Project 3 -- */
void*
mmap(void *addr, size_t length, int writable, int fd, off_t offset)
{
if ((signed)length <= 0 || length < offset)
return NULL;
if(!addr || fd < 2 || is_kernel_vaddr(addr) || pg_ofs(addr))
return NULL;
struct file* file = file_reopen(thread_current()->fd_table[fd]);
return do_mmap(addr, length, writable, file, offset);
}/* Opens and returns a new file for the same inode as FILE.
* Returns a null pointer if unsuccessful. */
struct file *
file_reopen (struct file *file)
{
return file_open (inode_reopen (file->inode));
}Gitbook👇
Maps length bytes the file open as fd starting from offset byte into the process's virtual address space at addr. The entire file is mapped into consecutive virtual pages starting at addr.
If the length of the file is not a multiple of PGSIZE, then some bytes in the final mapped page "stick out" beyond the end of the file. Set these bytes to zero when the page is faulted in, and discard them when the page is written back to disk. If successful, this function returns the virtual address where the file is mapped. On failure, it must return NULL which is not a valid address to map a file.
만약 읽어들이는 파일 길이가 PGSIZE로 나눠 떨어지지 않는다면 페이지를 넘어 삐져나오는(stickout) 데이터가 발생할 것이다. 이 남는 데이터를 매핑하면 마지막 페이지에 빈 공간이 남는데, 여기에는 0으로 초기화해줄 필요가 있다. 이전에 이 페이지 영역에서 작업했던 기록이 남아있을 수 있는데, 이를 현재 프로세스에서 접근하면 보안 문제가 될 수 있기 때문.
A call to
mmap()may fail if :
- 파일 디스크립터로 열린 파일의 길이가 0 이하이면
mmap()은 실패해야한다.- 주소가 Page-align 되지 않았어도 실패해야한다.
- 매핑된 페이지가 현재 존재하는 페이지들이나 스택과 겹치는 부분이 생기면 실패해야한다.
/* @syscall.c */
case SYS_MMAP:
f->R.rax = mmap(f->R.rdi, f->R.rsi, f->R.rdx, f->R.r10, f->R.r8);
break;mmap()은 위의 조건들을 확인 후 do_mmap()을 호출해준다.
/* @file.c */
void *
do_mmap (void *addr, size_t length, int writable,
struct file *file, off_t offset)
{
off_t read_size = file_length(file);
void *va = addr;
while(0 < read_size) {
struct aux_struct *temp_aux = (struct aux_struct *)malloc(sizeof(struct aux_struct));
uint32_t read_bytes = read_size > PGSIZE ? PGSIZE : read_size;
temp_aux->vmfile = file;
temp_aux->ofs = offset;
temp_aux->read_bytes = read_bytes;
temp_aux->zero_bytes = PGSIZE - read_bytes;
temp_aux->writable = writable;
temp_aux->upage = va;
if(!vm_alloc_page_with_initializer(VM_FILE, va, writable,
lazy_load_file, temp_aux))
return NULL;
read_size -= read_bytes;
va += PGSIZE;
offset += read_bytes;
}
return addr; // load_segment()와 달리 매핑된 주소 리턴
}Memory-mapped pages도 ANON_PAGE 처럼 lazy load 되어야한다. vm_alloc_page_with_initializer() 로 페이지를 만들어준다.
offset 바이트에서 시작해 addr 에 있는 프로세스의 가상 주소 공간에 fd(file descriptor)로 열린 파일의 length(bytes) 만큼을 매핑한다. 성공한다면 매핑된 가상 주소를 반환한다. load_segment() 와 비슷하지만 UNINIT 페이지를 만들때 타입을 VM_FILE로 설정 해 주고, 주소를 리턴한다.
munmap() system call
/* @syscall.c */
case SYS_MUNMAP:
munmap(f->R.rdi);
break;munmap() 시스템콜은 해당 주소가 유저 가상주소 공간인지 확인 후 do_munmap()을 호출한다. 이는 지정된 주소 범위 addr에 대한 매핑을 해제한다. 이때 이 주소는 아직 해제되지 않은, 동일한 프로세스의 mmap() 호출에서 반환된 가상 주소여야 한다.
/* @file.c */
void
do_munmap (void *addr) {
struct page *page = spt_find_page(&thread_current()->spt, pg_round_down(addr));
struct file *file = page->file.file;
off_t read_size = file_length(file);
while(page = spt_find_page(&thread_current()->spt, addr)) {
if(page->file.file != file)
return;
if(pml4_is_dirty(thread_current()->pml4, addr)) {
pml4_set_dirty(thread_current()->pml4, addr, false);
file_write_at(page->file.file, addr, page->file.read_byte, page->file.offset);
}
addr += PGSIZE;
}
}페이지에 연결되어 있는 물리 프레임과의 연결을 끊어준다. 유저 가상 메모리의 시작 주소 addr부터 연속으로 나열된 페이지 모두를 매핑 해제한다. 이때 페이지의 Dirty bit이 1인 페이지는 매핑 해제 전에 변경 사항을 디스크 파일에 업데이트해줘야 한다. 이를 위해 페이지의 file 구조체에서 연결된 파일에 대한 정보를 가져온다.
/* Initialize the file backed page */
bool
file_backed_initializer (struct page *page, enum vm_type type, void *kva) {
/* Set up the handler */
page->operations = &file_ops;
struct file_page *file_page = &page->file;
/* -- Project 3 -- */
struct aux_struct *dummy = (struct aux_struct *)page->uninit.aux;
file_page->file = dummy->vmfile;
file_page->offset = dummy->ofs;
file_page->read_byte = dummy->read_bytes;
file_page->zero_byte = dummy->zero_bytes;
file_page->type = type;
if(file_read_at(dummy->vmfile, kva, dummy->read_bytes, dummy->ofs)
!= dummy->read_bytes) {
return false;
}
return true;
}file-backed page를 초기화한다. page->operations에서 핸들러를 설정하고, uninit aux에서 정보를 받아와서 비교해 실패한다면 false를 반환한다.
mmap()과 malloc의 차이
여러가지 free-list, fit, coalesce 정책들을 아용 해 malloc을 구현해 본 적이 있다. 이 둘은 무엇이 다를까?
mmap()은 파일이나 장치들을 매핑 해 메모리를 할당하고,malloc()은 힙에서 메모리를 할당해준다.mmap()은 프로세스 간에 메모리 공유를 지원하지만,malloc()은 그러지않는다.mmap()은 0으로 초기화된 메모리를 반환해주지만,malloc()은 초기화 되지 않은 메모리를 반환 할 수 있다.
FAQ
Q :정확히 어느 시점에 인터럽트 프레임의 rsp가 유저 스택을 가리키다 커널 스택을 가리키는가?
A : "Since the processor only saves the stack pointer when an exception causes a switch from user to kernel mode, reading rsp out of the struct intr_frame passed to page_fault() would yield an undefined value, not the user stack pointer." 에 대한 올바른 해석은:
- exception으로 인해 user -> kernel로 옮겨갈 때: intr_frame 에 유저 레벨의 %rsp가 저장됨
- exception으로 인해 kernel -> kernel로 옮겨갈 때: intr_frame 의 rsp 항목에 값이 백업 안됨
입니다. intr_frame 은 exception 등으로 인해 실행흐름이 옮겨갈 때 기존 값을 백업하려고 존재하는 구조라서 "rsp값이 유저 스택을 가리키다가 커널 스택으로 옮겨간다" 라는 메커니즘은 아닙니다.
Q : 쓰레드구조체의 rsp_stack에 인터럽트 프레임의 rsp, 즉 유저 스택의 rsp를 가리키는 값, 을 저장하는 코드가 exception.c에 위치하는게 타임라인상 옳은가?
A : intr_frame에 값을 백업하는 과정은 exception이 일어난 직후에 모두 이루어지므로 page_fault함수에 들어올 때는 이미 최종 값이 저장된 상태입니다. user=true 인 경우, exception이 일어나서 user->kernel로 실행흐름이 옮겨간 것이고 이때 intr_frame 의 rsp에 최종적으로 저장된 것은 유저의 %rsp 입니다. 그래서 f->rsp 값을 읽어서 rsp_stack 에 저장하는 것은 옳습니다.
Q :
syscall시에도 syscall_handler에서 인터럽트 프레임의 rsp값을 쓰레드 구조체의 rsp_stack에 저장하고 있는데, 이 또한 시기적으로 옳은가?
A : 옳습니다. 저기서 미리 저장해놔야 syscall을 처리하다가 발생하는 page fault에서 stack_growth를 처리할 때 올바른 유저 rsp값을 찾을 수 있습니다.
