Stack Growth

카이스트 핀토스의 stack growth

이전까지 프로그램에 할당되는 stack의 크기는 4kb였다. 이를 초과하면 프로그램은 종료되게 설정되어 있다. 허나 이번 과제를 완수하면 4kb 이상의 stack 공간이 필요해질 때 stack을 동적으로 늘릴 수 있게 된다!

생각보다 쉬울 것이라 예상했으나, 예상치 못한 곳에서 나를 혼란스럽게 했다. 바로... Document에 설명된 말이 무슨 뜻인지 이해가 가지 않는다는 것이다.

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.

위는 핀토스를 구현하며 약 2, 3일간 나를 고민에 빠지게 한 문장이었다. 스택 포인터 rsp가 4kb를 초과하게 될 때 스택 포인터가 미리 거기를 가보고??? 스택이 할당되지 않은 공간이면 page fault를 낸다는 것인지... 흠... 핀토스에서 요구하는, stack growth가 필요하여 발생하는 page fault를 어떻게 감지할 것인지 머리 속에 그려지지 않았다.

일단 stack growth가 필요함에 의해 page fault가 발생하면 인터럽트 프레임 f의 rsp가 stack bottom 밑에 존재한다는 것은 알겠다. 근데 이것이 왜 8바이트 밑이여야 할까? 스택 푸쉬는 8바이트씩 움직이는 건가?

근데 테스트 케이스들을 보면 바로 8바이트 밑에 있는게 또 아니었다. 한 번에 여러 페이지 크기만큼의 스택이 필요한 경우가 있는 것 같다.

궁금한 점이 많아 팀원인 수연이와 함께 질문을 해보기로 결정했다! 모르더라도 있는 그대로 표현하면서 해답을 얻어나갈 수 있었고, 나뿐만 아니라 다른 동기들도 이 부분을 제일 궁금해 했었다는 것을 알게 되었다.

• 수연이의 질문
  

• 조교님의 답변
  

그렇다...! 테스트 케이스 중 한 번에 4096바이트, 즉 1페이지 만큼의 크기를 필요로 하는 배열이 선언된다. 또한 arc4라는 구조체가 선언이 되는데 이것 또한 스택 공간을 필요로 한다. 따라서 1페이지 이상의 스택 공간을 할당해달라고 OS에게 요구하게 된다.(어셈블리어에서는 rsp가 sub로 0x1110만큼 위치가 감소한다. 즉 한 페이지를 넘어선 곳에 위치하게 된다)

하지만 이렇게 rsp가 이동했다고 해서 stack growth로 인한 page fault가 일어나는 건 아니다.

rsp가 이동하는 데에는 -+8씩 이동하는 push/pop instruction 말고도 앞선 상황과 같이 sub 혹은 add로 한번에 이동하는 arithmetic instruction 또한 존재한다.

그렇다면 또 다른 의문점이 생긴다. 이렇게 rsp가 이동했는데 page fault가 발생한 것이 아니라면 대체 이 테스트 케이스는 무엇때문에 page fault가 일어난 것인가?

• 나의 질문
  

• 조교님의 답변
  

• 나의 질문(2) + 조교님의 답변
  

그렇다. 일단 이번 테스트 케이스에서 한 페이지를 뛰어넘는 스택 공간을 필요로 하는 변수들이 선언되면서 arithmetic instruction(여기서는 0x1110만큼 sub)이 일어나 rsp가 일어나는 반면, 여기서 page fault가 일어나는 것이 아니라 push instruction이 일어나면 stack growth를 위해 page fault가 일어나게 된다.

근데 그렇다면... rsp가 0x1110만큼 내려간 뒤 push가 일어나 page fault가 일어나게 된다는 것으로 이해했는데, 만약 여기에 계속해서 데이터들이 쌓이게 되는 것이면, 그 이전의 0x1110만큼의 공간은 버려...지는 건가???

• 나의 질문
  

미정 누나의 도움으로 objdump를 사용하여 해당 테스트 케이스를 어셈블리어로 뜯어보기도 했다...!(어렵지만 그래도 몇몇 부분은 해석이 가능했다)

테스트 케이스의 코드는 다음과 같다.

void
test_main (void)
{
  char stack_obj[4096];
  struct arc4 arc4;

  arc4_init (&arc4, "foobar", 6);
  memset (stack_obj, 0, sizeof stack_obj);
  arc4_crypt (&arc4, stack_obj, sizeof stack_obj);
  msg ("cksum: %lu", cksum (stack_obj, sizeof stack_obj));
}

• 조교님의 답변
  

pwndbg> disassemble test_main
Dump of assembler code for function test_main:
   0x00000000004000e8 <+0>:	push   rbp
   0x00000000004000e9 <+1>:	mov    rbp,rsp
   0x00000000004000ec <+4>:	sub    rsp,0x1110
   0x00000000004000f3 <+11>:	lea    rax,[rbp-0x1102]
   0x00000000004000fa <+18>:	mov    edx,0x6
   0x00000000004000ff <+23>:	movabs rsi,0x404690
   0x0000000000400109 <+33>:	mov    rdi,rax
   0x000000000040010c <+36>:	movabs rax,0x4001cd
   0x0000000000400116 <+46>:	call   rax
   0x0000000000400118 <+48>:	lea    rax,[rbp-0x1000]
   0x000000000040011f <+55>:	mov    edx,0x1000
   0x0000000000400124 <+60>:	mov    esi,0x0
   0x0000000000400129 <+65>:	mov    rdi,rax
   0x000000000040012c <+68>:	movabs rax,0x40304b
   0x0000000000400136 <+78>:	call   rax
   0x0000000000400138 <+80>:	lea    rcx,[rbp-0x1000]
   0x000000000040013f <+87>:	lea    rax,[rbp-0x1102]
   0x0000000000400146 <+94>:	mov    edx,0x1000
   0x000000000040014b <+99>:	mov    rsi,rcx
   0x000000000040014e <+102>:	mov    rdi,rax
   0x0000000000400151 <+105>:	movabs rax,0x4002db
   0x000000000040015b <+115>:	call   rax
   0x000000000040015d <+117>:	lea    rax,[rbp-0x1000]
   0x0000000000400164 <+124>:	mov    esi,0x1000
   0x0000000000400169 <+129>:	mov    rdi,rax
   0x000000000040016c <+132>:	movabs rax,0x4003d8
   0x0000000000400176 <+142>:	call   rax
   0x0000000000400178 <+144>:	mov    rsi,rax
   0x000000000040017b <+147>:	movabs rdi,0x404697
   0x0000000000400185 <+157>:	mov    eax,0x0
   0x000000000040018a <+162>:	movabs rdx,0x4005e4
   0x0000000000400194 <+172>:	call   rdx
   0x0000000000400196 <+174>:	nop
   0x0000000000400197 <+175>:	leave  
   0x0000000000400198 <+176>:	ret    
End of assembler dump.
pwndbg> x/2i arc4_init
   0x4001cd <arc4_init>:	push   rbp
   0x4001ce <arc4_init+1>:	mov    rbp,rsp
   
   pwndbg> x/i 0x4001cd
   0x4001cd <arc4_init>:	push   rbp
pwndbg> x/i 0x40304b
   0x40304b <memset>:	push   rbp
pwndbg> x/i 0x4002db
   0x4002db <arc4_crypt>:	push   rbp
pwndbg> x/i 0x4003d8
   0x4003d8 <cksum>:	push   rbp
pwndbg> x/i 0x4005e4
   0x4005e4 <msg>:	push   rbp

• 나의 답변
  

아... 3일간 묵은 체증이 쫙 내려가는 기분이었다. 그렇다 해당 빈 공간은 arc4_init, memset, arc4_crypt, cksum 등의 함수가 이 빈 스택을 사용하게 된다는 것이었다. 포인터로 이 함수들에게 전달되어 각 함수들은 해당 스택에 데이터를 쌓을 수 있게 된다.

그리고 가장 중요한 것!

arc4_init과 같은 함수를 딱 가르키게 되면 원래 test_main이라는 메인 함수로 돌아오기 위해 return address를 stack에 push하게 되는데 이 과정에서 push instruction이 일어나고 이 때 0x1110만큼 내려온 rsp가 -8만큼 또 내려가보려 했더니 stack으로 할당된 공간이 아니기에 page fault가 일어나게 된다는 것이다. 이를 통해서 stack growth가 필요하여 page fault가 일어난 것임을 판정하기 위해서는 앞에서 3일간 고민한 인용문처럼 faulted address === rsp - 8가 true이면 된다라는 것을 알 수 있게 되었다. 우리가 핀토스에서 구현한 판별문 코드는 다음과 같다.

USER_STACK - 1MB ≤ rsp-8 ≤ addr ≤ stack_bottom