[Pintos-KAIST] Project 3 :: Stack Growth (Pintos의 스택 확장 메커니즘)

오박사님, 유진이와 함께 정리한 내용😆

 

Stack Growth

Project 2까지 사용하던 스택은 USER_STACK을 시작으로 하는 단일 페이지였으며, 프로그램의 실행은 이 크기로 제한되어 있었다.
Stack Growth를 구현하면 스택이 현재 크기를 초과하면 추가 페이지를 할당한다.

 

즉, 접근한 가상 주소에 매핑된 frame이 없어서 page fault가 발생한 경우 중에서
접근한 가상 주소가 Stack 영역 내에 존재할 경우에는 추가 페이지를 할당해 page fault를 해결해보자!

 

 

우선 접근한 주소가 Stack 영역 내에 존재하는지 판별해야 한다.

접근한 주소가 Stack 영역 내에 존재하는지 판별하기

page fault가 발생했을 때 접근한 주소가 stack 안에 있는지 판별하고, stack에 접근한 경우에는 stack growth를 통해서 page fault를 해결해야 한다.

• Pintos에서는 최대 스택 크기를 1MB(1,048,576 bytes)로 제한한다.
  • USER_STACK - 1MB보다 낮은 주소를 가리키면 잘못된 접근으로 판별한다. (return false)
• USER_STACK ~ USER_STACK - 1MB 사이에 접근한 것이 맞더라도 전부 stack growth로 해결하는 것은 아니고, rsp보다 높은 주소 값에 접근한 경우에만 stack growth를 통해서 해결한다. rsp <= addr
  • 🤔 Why? 운영체제가 실행되다가 signal에 의해서 프로세스를 중단시키면 실행되던 정보를 스택에 저장하는데, 유저 프로그램이 스택 포인터 아래 스택에 데이터를 써놨다면, 이때 데이터가 덮어씌워지면서 변경될 수 있기 때문이다.
  • 이러한 이유로, 일반적으로 프로그래밍에서 스택 포인터 아래에 쓰기를 시도하는 것은 위험하며, 버그를 일으킬 수 있으니 이 경우에는 stack growth가 아닌 잘못된 접근으로 판별해야 한다. (return false)
• rsp보다 낮은 주소인 rsp - 8에 접근했을 경우에도 stack growth로 해결할 수 있는 경우가 있는데, 바로 PUSH 명령어가 실행되는 상황이다. rsp - 8 == addr
  • x86-64 PUSH 명령은 스택 포인터를 조정하기 전에 접근 권한을 확인하므로, 스택 포인터로부터 8바이트 아래에서 페이지 폴트(page fault)가 발생할 수 있다.
  • 따라서, rsp - 8 지점에 접근한 경우에도 stack growth를 통해서 해결한다.
  • 참고로, PUSH 명령은 주로 함수 호출 시 매개변수를 스택에 전달하거나, 함수 내에서 로컬 변수를 스택에 할당할 때 사용된다.

 

💡 따라서, Stack 영역 내에 존재하면서 stack growth로 해결할 수 있는 경우인지 판별하기 위해서는 유저 스택의 스택 포인터 rsp를 알아야 한다.

 

rsp 가져오기

• User 프로그램에서 발생한 page fault는 page_fault()에 전달된 intr_frame의 rsp에서 유저 스택의 스택 포인터를 가져올 수 있다.
  • 이 intr_frame은 vm_try_handle_fault 함수에 f로 전달되므로 f->rsp로 접근하면 된다.
• 반면, System call(Kernel 모드)에서 발생한 page fault는 syscall_handler()에 전달된 intr_frame의 rsp에서 유저 스택의 스택 포인터를 가져와야 한다.
  • 커널 모드에서 예외가 발생한 경우에는 vm_try_handle_fault로 전달되는 f 인자에서 rsp에 접근했을 때, 유저 스택이 아닌 커널 스택의 스택 포인터를 얻게 된다. 따라서 사용할 수 없음!
  • 유저 모드에서 커널 모드로의 초기 전환 시 struct thread에 rsp를 저장해야 한다.
  • So, 커널 모드로 전환될 때 (즉, syscall_handler() 함수에서) 미리 유저 스택의 스택 포인터를 저장해두고 사용해야 한다.

 

vm_try_handle_fault에 intr_frame이 전달되는 과정

 

vm_try_handle_fault에 전달된 인자 f에 정말 유저 스택의 스택 포인터가 담기는 것이 맞는지 확인하기 위해서
intr_frame이 전달되는 과정을 따라가 보았다. 🏃‍♀️🏃🏃‍♂️

intr_stubs.S

page fault가 발생하면 intr_stubs.S의 어셈블리 코드에서
현재 CPU의 컨텍스트를 인터럽트 프레임에 저장하고 인터럽트 핸들러를 호출한다.

intr_handler

인터럽트 핸들러에서는 vector number를 확인해서 현재 인터럽트에 해당하는
page fault 함수를 호출한다. (인자로 frame 전달)

page_fault

page_fault 함수에서는 vm_try_handle_fault가 호출되는 과정을 거치게 되고,
동시에 user-level에서의 컨텍스트가 인터럽트 프레임에 전달되기 때문에
vm_try_handle_fault의 인자로 전달된 f를 통해 스택 포인터에 접근할 수 있다는 것을 알 수 있다.

 

 

이제 위 내용을 바탕으로 실제로 구현해보자!

💡 Implement stack growth functionalities.

1) stack growth 식별하기

USER_STACK - (1 << 20) <= rsp <= addr <= USER_STACK

• 명령이 호출되면 rsp는 필요한 메모리만큼 이미 이동해있는 상태이다.
• addr가 rsp보다 높은 주소를 가리켰을 때를 stack 접근으로 판별한다.
• PUSH 명령인 경우에는 rsp가 아직 이동하기 전에 page fault가 발생하므로 rsp-8에 접근한 경우에도 stack growth로 해결한다.

vm_try_handle_fault

# 인자 설명
`f`
    - page fault 예외가 발생할 때 실행되던 context 정보가 담겨있는 interrupt frame이다.
`addr`
    - page fault 예외가 발생할 때 접근한 virtual address이다. 즉, 이 virtual address에 접근했기 때문에 page fault가 발생한 것이다.
`not_present`
    - true: addr에 매핑된 physical page가 존재하지 않는 경우에 해당한다.
    - false: read only page에 writing 작업을 하려는 시도에 해당한다.
`write`
    - true: addr에 writing 작업을 시도한 경우에 해당한다.
    - false: addr에 read 작업을 시도한 경우에 해당한다.
`user`
    - true: user에 의한 접근에 해당한다.
    - false: kernel에 의한 접근에 해당한다.

/* vm.c */

/* 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;
    if (addr == NULL)
        return false;

    if (is_kernel_vaddr(addr))
        return false;

    if (not_present) // 접근한 메모리의 physical page가 존재하지 않은 경우
    {
        /* TODO: Validate the fault */
        // 페이지 폴트가 스택 확장에 대한 유효한 경우인지를 확인한다.
        void *rsp = f->rsp; // user access인 경우 rsp는 유저 stack을 가리킨다.
        if (!user)            // kernel access인 경우 thread에서 rsp를 가져와야 한다.
            rsp = thread_current()->rsp;

        // 스택 확장으로 처리할 수 있는 폴트인 경우, vm_stack_growth를 호출한다.
        if (USER_STACK - (1 << 20) <= rsp - 8 && rsp - 8 == addr && addr <= USER_STACK)
            vm_stack_growth(addr);
        else if (USER_STACK - (1 << 20) <= rsp && rsp <= addr && addr <= USER_STACK)
            vm_stack_growth(addr);

        page = spt_find_page(spt, addr);
        if (page == NULL)
            return false;
        if (write == 1 && page->writable == 0) // write 불가능한 페이지에 write 요청한 경우
            return false;
        return vm_do_claim_page(page);
    }
    return false;
}

struct thread

• 커널 모드로 전환될 때 (시스템콜이 호출될 때) 현재 유저 스택의 스택 포인터를 저장해두기 위한 필드를 thread 구조체에 추가한다.

/* thread.h */

struct thread
{
    ...

#ifdef VM
    /* Table for whole virtual memory owned by thread. */
    struct supplemental_page_table spt;
    void *rsp; // 추가
#endif

    ...

};

syscall_handler

• 커널 모드로 전환될 때 (시스템콜이 호출될 때) syscall_handler 함수에서 스택 포인터를 저장한다.

/* syscall.c */

/* The main system call interface */
void syscall_handler(struct intr_frame *f UNUSED)
{
    int syscall_n = f->R.rax;
#ifdef VM
    thread_current()->rsp = f->rsp; // 추가
#endif
    switch (syscall_n)
    {

    ...

    }
}

 

2) stack growth 구현하기

• vm_try_handle_fault에서 스택 성장을 식별한 후에는 vm_stack_growth 함수를 호출하여 스택을 성장시킨다.
• 스택 크기를 증가시키기 위해 anonymous pages를 할당하여 주어진 addr이 더 이상 예외 주소(faulted address)가 되지 않도록 한다.
• 할당할 때 addr을 PGSIZE로 내림하여 처리해야 한다.

/* Growing the stack. */
static void
vm_stack_growth(void *addr UNUSED)
{
    // todo: 스택 크기를 증가시키기 위해 anon page를 하나 이상 할당하여 주어진 주소(addr)가 더 이상 예외 주소(faulted address)가 되지 않도록 합니다.
    // todo: 할당할 때 addr을 PGSIZE로 내림하여 처리
    vm_alloc_page(VM_ANON | VM_MARKER_0, pg_round_down(addr), 1);
}

 

 

이제 모든 스택 성장 테스트 케이스가 통과된다.💖

• Test 결과 (29 of 141 tests failed.)

pass tests/userprog/args-none
pass tests/userprog/args-single
pass tests/userprog/args-multiple
pass tests/userprog/args-many
pass tests/userprog/args-dbl-space
pass tests/userprog/halt
pass tests/userprog/exit
pass tests/userprog/create-normal
pass tests/userprog/create-empty
pass tests/userprog/create-null
pass tests/userprog/create-bad-ptr
pass tests/userprog/create-long
pass tests/userprog/create-exists
pass tests/userprog/create-bound
pass tests/userprog/open-normal
pass tests/userprog/open-missing
pass tests/userprog/open-boundary
pass tests/userprog/open-empty
pass tests/userprog/open-null
pass tests/userprog/open-bad-ptr
pass tests/userprog/open-twice
pass tests/userprog/close-normal
pass tests/userprog/close-twice
pass tests/userprog/close-bad-fd
pass tests/userprog/read-normal
pass tests/userprog/read-bad-ptr
pass tests/userprog/read-boundary
pass tests/userprog/read-zero
pass tests/userprog/read-stdout
pass tests/userprog/read-bad-fd
pass tests/userprog/write-normal
pass tests/userprog/write-bad-ptr
pass tests/userprog/write-boundary
pass tests/userprog/write-zero
pass tests/userprog/write-stdin
pass tests/userprog/write-bad-fd
pass tests/userprog/fork-once
pass tests/userprog/fork-multiple
pass tests/userprog/fork-recursive
pass tests/userprog/fork-read
pass tests/userprog/fork-close
pass tests/userprog/fork-boundary
pass tests/userprog/exec-once
pass tests/userprog/exec-arg
pass tests/userprog/exec-boundary
pass tests/userprog/exec-missing
pass tests/userprog/exec-bad-ptr
pass tests/userprog/exec-read
pass tests/userprog/wait-simple
pass tests/userprog/wait-twice
pass tests/userprog/wait-killed
pass tests/userprog/wait-bad-pid
pass tests/userprog/multi-recurse
pass tests/userprog/multi-child-fd
pass tests/userprog/rox-simple
pass tests/userprog/rox-child
pass tests/userprog/rox-multichild
pass tests/userprog/bad-read
pass tests/userprog/bad-write
pass tests/userprog/bad-read2
pass tests/userprog/bad-write2
pass tests/userprog/bad-jump
pass tests/userprog/bad-jump2
pass tests/vm/pt-grow-stack
pass tests/vm/pt-grow-bad
pass tests/vm/pt-big-stk-obj
pass tests/vm/pt-bad-addr
pass tests/vm/pt-bad-read
pass tests/vm/pt-write-code
pass tests/vm/pt-write-code2
pass tests/vm/pt-grow-stk-sc
pass tests/vm/page-linear
pass tests/vm/page-parallel
pass tests/vm/page-merge-seq
pass tests/vm/page-merge-par
pass tests/vm/page-merge-stk
FAIL tests/vm/page-merge-mm
pass tests/vm/page-shuffle
FAIL tests/vm/mmap-read
FAIL tests/vm/mmap-close
FAIL tests/vm/mmap-unmap
FAIL tests/vm/mmap-overlap
FAIL tests/vm/mmap-twice
FAIL tests/vm/mmap-write
pass tests/vm/mmap-ro
FAIL tests/vm/mmap-exit
FAIL tests/vm/mmap-shuffle
FAIL tests/vm/mmap-bad-fd
FAIL tests/vm/mmap-clean
FAIL tests/vm/mmap-inherit
FAIL tests/vm/mmap-misalign
FAIL tests/vm/mmap-null
FAIL tests/vm/mmap-over-code
FAIL tests/vm/mmap-over-data
FAIL tests/vm/mmap-over-stk
FAIL tests/vm/mmap-remove
pass tests/vm/mmap-zero
FAIL tests/vm/mmap-bad-fd2
FAIL tests/vm/mmap-bad-fd3
FAIL tests/vm/mmap-zero-len
FAIL tests/vm/mmap-off
FAIL tests/vm/mmap-bad-off
FAIL tests/vm/mmap-kernel
FAIL tests/vm/lazy-file
pass tests/vm/lazy-anon
FAIL tests/vm/swap-file
FAIL tests/vm/swap-anon
FAIL tests/vm/swap-iter
pass tests/vm/swap-fork
pass tests/filesys/base/lg-create
pass tests/filesys/base/lg-full
pass tests/filesys/base/lg-random
pass tests/filesys/base/lg-seq-block
pass tests/filesys/base/lg-seq-random
pass tests/filesys/base/sm-create
pass tests/filesys/base/sm-full
pass tests/filesys/base/sm-random
pass tests/filesys/base/sm-seq-block
pass tests/filesys/base/sm-seq-random
pass tests/filesys/base/syn-read
pass tests/filesys/base/syn-remove
pass tests/filesys/base/syn-write
pass tests/threads/alarm-single
pass tests/threads/alarm-multiple
pass tests/threads/alarm-simultaneous
pass tests/threads/alarm-priority
pass tests/threads/alarm-zero
pass tests/threads/alarm-negative
pass tests/threads/priority-change
pass tests/threads/priority-donate-one
pass tests/threads/priority-donate-multiple
pass tests/threads/priority-donate-multiple2
pass tests/threads/priority-donate-nest
pass tests/threads/priority-donate-sema
pass tests/threads/priority-donate-lower
pass tests/threads/priority-fifo
pass tests/threads/priority-preempt
pass tests/threads/priority-sema
pass tests/threads/priority-condvar
pass tests/threads/priority-donate-chain
FAIL tests/vm/cow/cow-simple
29 of 141 tests failed.