[PintOS] Project 3 : Virtual Memory - Stack Growth

chohk10·2023년 5월 23일
pintos운영체제정글
0

PintOS

목록 보기
5/8
post-custom-banner

3. Stack Growth

If the stack grows past its current size, we need to allocate additional pages as necessary.
Allocate additional pages only if they "appear" to be stack accesses.

  • Devise a heuristic that attempts to distinguish stack accesses from other accesses.

User programs are buggy if they write to the stack below the stack pointer, because typical real OSes may interrupt a process at any time to deliver a "signal," which modifies data on the stack. However, the x86-64 PUSH instruction checks access permissions before it adjusts the stack pointer, so it may cause a page fault 8 bytes below the stack pointer.

👉🏻 흔한 운영체제에서는 특정한 시그널을 보내기 위한 인터럽트가 언제든지 발생할 수 있으며, 이는 stack 상에서 데이터를 수정하기 때문에 유저 프로그램이 작업하고 있던 데이터가 오염될 수 있다. 따라서 유저 프로그램은 stack pointer 밑에서 무언가를 write해서는 안된다. (사실 당연하게 느껴지는 이야기인데, 이 이야기를 왜 하느냐하면) Stack pointer 밑에서 작업을 하기 보다는 먼저 stack pointer 아랫 부분의 access permission을 먼저 확인해본다. Permission이 있다면 stack pointer를 내려준 후 작업하려던 것을 stack pointer 위에서 하면 된다. Permission 이 없다면 stack pointer 밑의 8바이트에 대해 page fault를 발생시킴으로서 해당 주소에 페이지를 할당받는 등의 stack growth로 이어질 수 있다.

You will need to be able to obtain the current value of the user program's stack pointer. Within a system call or a page fault generated by a user program, you can retrieve it from the rsp member of the struct intr_frame passed to syscall_handler() or page_fault(), respectively. If you depend on page faults to detect invalid memory access, you will need to handle another case, where a page fault occurs in the kernel. 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. You will need to arrange another way, such as saving rsp into struct thread on the initial transition from user to kernel mode.

👉🏻 'Exception에 의해서', '유저모드에서 커널모드로 변경된다'는 두가지 조건을 만족할 때에만 프로세서는 스택 포인터를 저장한다.
👉🏻 따라서 커널모드에서 작업을 하다가 page fault가 발생했을 때는 유저모드에서 커널모드로 넘어오는 과정이 없기 때문에 스택 포인터를 저장하지 못한다. 따라서 이 때 rsp를 참조하려고 하면 값이 정의되어있지 않을 것이다.
👉🏻 이를 해결하기 위해 처음 유저모드에서 커널모드로 변경될 때 thread struct에 rsp 포인터를 저장하는 등 다른 방법을 고안해야한다.
👉🏻 아직까지는 유저모드에서 커널모드로 넘어가는 경우는 1. page fault 2. system call 두가지 경우이다!

  • 이 두가지의 경우에 rsp를 thread struct에 저장할 수 있도록 코드 추가

Implement stack growth functionalities

first modify vm_try_handle_fault in vm/vm.c to identify the stack growth.
make a call to vm_stack_growth in vm/vm.c to grow the stack.
Implement the vm_stack_growth.

bool vm_try_handle_fault (struct intr_frame *f, void *addr,
    bool user, bool write, bool not_present);

In this function, you need to check whether the page fault is a valid case for a stack growth or not. If you have confirmed that the fault can be handled with a stack growth, call vm_stack_growth with the faulted address.

👉🏻 이 부분을 구현하려고 하는데 쉽게 와닿지 않았던 것은 현재 나에게 주어진 정보는 주소밖에 없는데 어떻게 이게 stack growth를 원하는 상황인지를 판단할 수 있는가였다.
그런데 사실 fault handling에서는 아직 물리 메모리까지는 가지도 않았고, 프로세스별 가상 메모리에 대해서만 다루고 있다는 점을 생각해보면 의미가 없는 의문이었다.
내가 헷갈렸던 것은 물리 메모리에 대해서 다루는 거라면, 커널 영역의 주소를 다루는거라면, 산발적으로 페이지가 위치하고 있고, 일정한 layout이 없기 때문에 주소의 상대적인 위치만 가지고는 알 수 있는게 없다.
하지만 우리는 프로세스마다 가지고 있는 가상 주소 공간을 사용하고 있고, 각각의 가상 주소 공간은 위쪽에 stack 영역이 아래 쪽에 text, data 등의 영역이 있다.
따라서 내가 받은 addr라는 가상주소가 유저 영역에 있는 경우 spt를 확인해볼 수 있고, spt에 없는 주소 중에서도 rsp 근처 또는 그 위쪽에 있는 주소라면 stack을 확장하고 싶어하는 상황이라는 것을 알 수 있다.
구현할 때에는 아무래도 물리 메모리의 주소를 직접적으로 생각해야하는 경우는 거의 없기 때문에 최대한 가상 주소 공간을 머릿속에 잘 그리면서 구현하는 것이 중요한 것 같다!

void vm_stack_growth (void *addr);

Increases the stack size by allocating one or more anonymous pages so that addr is no longer a faulted address. Make sure you round down the addr to PGSIZE when handling the allocation.

Most Oses impose some absolute limit on stack size. Some OSes make the limit user-adjustable, e.g. with the ulimit command on many Unix systems. On many GNU/Linux systems, the default limit is 8 MB. For this project, you should limit the stack size to be 1MB at maximum.

Now, all the stack-growth test cases should be passed.

버그를 잡자

FAIL tests/vm/pt-grow-stack
FAIL tests/vm/pt-grow-bad
FAIL tests/vm/pt-big-stk-obj
pass tests/vm/pt-bad-addr
FAIL tests/vm/pt-bad-read
FAIL tests/vm/pt-write-code
FAIL tests/vm/pt-write-code2
FAIL 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
FAIL 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
FAIL tests/vm/mmap-ro
FAIL tests/vm/mmap-exit
FAIL tests/vm/mmap-shuffle
pass 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
pass tests/vm/mmap-bad-fd2
pass tests/vm/mmap-bad-fd3
pass 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
FAIL tests/vm/swap-fork
FAIL tests/vm/cow/cow-simple
35 of 141 tests failed.

stack growth 구현을 모두 하고 테스트를 돌렸는데 다 틀렸다..
왜일까?

FAIL tests/vm/pt-grow-stack
Kernel panic in run: PANIC at ../../vm/vm.c:156 in vm_get_frame(): TODO: swap
Call stack: 0x8004217f56 0x80042210a3 0x80042213c0 0x80042213a1 0x80042211ea 0x80042212dd 0x800421cf9b 0x8004208f6b 0x8004209389 0x400f46 0x400f8f
Translation of call stack:
0x0000008004217f56: debug_panic (lib/kernel/debug.c:32)
0x00000080042210a3: vm_get_frame (vm/vm.c:160)
0x00000080042213c0: vm_do_claim_page (vm/vm.c:236)
0x00000080042213a1: vm_claim_page (vm/vm.c:231)
0x00000080042211ea: vm_stack_growth (vm/vm.c:179)
0x00000080042212dd: vm_try_handle_fault (vm/vm.c:203)
0x000000800421cf9b: page_fault (userprog/exception.c:153)
0x0000008004208f6b: intr_handler (threads/interrupt.c:352)
0x0000008004209389: intr_entry (threads/intr-stubs.o:?)
0x0000000000400f46: (unknown)
0x0000000000400f8f: (unknown)
bool vm_try_handle_fault (struct intr_frame *f UNUSED, void *addr,
   bool user UNUSED, bool write UNUSED, bool not_present UNUSED) {
   struct supplemental_page_table *spt = &thread_current()->spt;
   struct page *page = NULL;
  
   page = spt_find_page(spt, pg_round_down(addr));
     
   if (page == NULL) {
      uintptr_t rsp = thread_current()->rsp;
      if (rsp - 8 <= addr <= USER_STACK && USER_STACK - (uintptr_t)addr < (1<<20)) {
         vm_stack_growth(addr);
         return true;
      }
      return false;
   }
  
   return vm_do_claim_page (page);
}

vm_stack_growth 후에 return true를 안썼었다... (바보)
stack growth를 해줘서 이제 문제 상황이 다 해결이 되었는데, 그 밑으로 가서 return false를 하고 있었다..ㅎ

FAIL tests/vm/pt-grow-stack
Kernel panic in run: PANIC at ../../vm/vm.c:156 in vm_get_frame(): TODO: swap
Call stack: 0x8004217f56 0x80042210a3 0x80042213c7 0x80042213a8 0x80042211ea 0x80042212dd 0x800421cf9b 0x8004208f6b 0x8004209389 0x400f46 0x400f8f
Translation of call stack:
0x0000008004217f56: debug_panic (lib/kernel/debug.c:32)
0x00000080042210a3: vm_get_frame (vm/vm.c:160)
0x00000080042213c7: vm_do_claim_page (vm/vm.c:236)
0x00000080042213a8: vm_claim_page (vm/vm.c:231)
0x00000080042211ea: vm_stack_growth (vm/vm.c:179)
0x00000080042212dd: vm_try_handle_fault (vm/vm.c:201)
0x000000800421cf9b: page_fault (userprog/exception.c:153)
0x0000008004208f6b: intr_handler (threads/interrupt.c:352)
0x0000008004209389: intr_entry (threads/intr-stubs.o:?)
0x0000000000400f46: (unknown)
0x0000000000400f8f: (unknown)

아직 같은 문제가 발생하고 있다.
stack growth 안에 있는 함수들 중에서도 frame 할당하는 부분에서 TODO: swap으로 panic이 일어난다고..?
stack growth 를 무한대로 해서 더이상 alloc할 frame이 없는 상태가 된 것으로 보인다.
stack growth의 while loop에서 주소값에 대해서 printf를 찍어보니 주소값이 끝도 없이 증가하는 것을 확인했다.
페이지 단위로 증가하면서 이미 spt에 들어가있는 주소의 경우 넘어갈 수 있도록 처리르 해 주었고, 유저 프로세스가 시작될 때 항상 setup stack을 해줄텐데 왜 USER_STACK 범위를 벗어나기 전에 걸리는 지점이 없는 것인지 이해가 가지 않는다. setup_stack이 아직 실행되지 않은 상태도 고려해야하는 것인가 싶다.
우선은 여기서 멈추지를 않으니 USER_STACK을 벗어나는 경우도 while loop의 조건에 추가해주었다.
그랬더니 이번에는 테스트 결과 stack growth 관련 테스트를 모두 통과하였다!

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
FAIL tests/vm/pt-bad-read
FAIL tests/vm/pt-write-code
FAIL 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
FAIL tests/vm/page-merge-par
FAIL 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
FAIL tests/vm/mmap-ro
FAIL tests/vm/mmap-exit
FAIL tests/vm/mmap-shuffle
pass 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
pass tests/vm/mmap-bad-fd2
pass tests/vm/mmap-bad-fd3
pass 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
FAIL tests/vm/swap-fork
FAIL tests/vm/cow/cow-simple
32 of 141 tests failed.

vm_try_handle_fault에서 kernel 가상 주소가 들어오는 경우 걸러주고, 잘못된 문법을 고쳐주었을 때 2개의 테스트 케이스가 더 성공하였다.

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
FAIL tests/vm/pt-write-code
FAIL 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
FAIL tests/vm/page-merge-par
FAIL 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
FAIL tests/vm/mmap-ro
FAIL tests/vm/mmap-exit
FAIL tests/vm/mmap-shuffle
pass 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
pass tests/vm/mmap-bad-fd2
pass tests/vm/mmap-bad-fd3
pass 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
FAIL tests/vm/cow/cow-simple
30 of 141 tests failed.

추가로 쓰기 권한이 없는 페이지에 대해서 쓰기를 하려는 경우 걸러주면 세개 케이스를 더 성공할 수 있다!!

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
FAIL 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
FAIL tests/vm/mmap-ro
FAIL tests/vm/mmap-exit
FAIL tests/vm/mmap-shuffle
pass 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
pass tests/vm/mmap-bad-fd2
pass tests/vm/mmap-bad-fd3
pass 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
FAIL tests/vm/cow/cow-simple
27 of 141 tests failed.

팀원들과 페어 프로그래밍으로 만든 코드에서는 29개 fail 했었는데 어떤 부분이 달라서 2개를 더 맞은건지 분석해봐야할 것 같다 🤔
👉🏻 코드를 비교해서 달랐던 부분들 몇가지를 하나씩 바꿔가서 테스트를 돌려봤는데, stack growth 에서 현재 위치 위쪽의 페이지들을 미리 할당해주지 않는 경우 테스트 케이스 한개의 성공 여부가 달라지는 것으로 확인하였다.
👉🏻 여러번 돌려봤는데.. 결국 돌릴 때마다 다른 결과가 나오는 케이스들이 몇개 있는 것 같다 ㅠ

profile
chohk10
이전 포스트

[PintOS] Project 3 : Virtual Memory - Anonymous Page

다음 포스트

[PintOS] Project 3 : Virtual Memory - Memory Mapped Files

post-custom-banner

0개의 댓글