[TIL] [WEEK11-12] Pintos Project(3) Stack Growth

프로젝트 2에서 스택은 USER_STACK에서 시작하는 단일 페이지였으며, 이 크기를 4KB로 제한해 실행했다.
이제 해당 파트에서는 스택이 현재 크기를 초과할 때 필요에 따라 추가 페이지를 할당하는 Stack Growth를 구현한다.

📍세 번째 과제, Stack Growth

Stack Growth?
: 접근한 가상주소에 매핑된 frame이 없어서 page fault가 발생한 경우, Stack을 늘려 추가 페이지를 할당해 page fault를 처리하는 방식이다.이는 가상주소가 stack에 접근하는 경우에만 적용된다.

우리가 생각해야 할 것은 크게 3가지다.

1. 접근한 가상주소가 stack인지 판별
2. stack growth로 해결할 수 있는 경우인지 판별
3. stack growth 기능 구현

---

🛠️ 접근한 가상주소가 stack인지 판별하기

pintOS에서는 Stack의 크기를 1MB로 제한하고 있다.
그렇다면 스택의 영역은 'USER_STACK'에서부터 'USER_STACK-1MB'일 것이다.
스택은 높은 주소에서 낮은 주소로 커지기 때문에 -1MB를 해야 한다.

이를 코드로 구현하면 'USER_STACK - (1 << 20)'이다.
Bit masking으로 표현한 것으로, 1 << 20 = 2의 20승 = 1MB

즉, USER_STACK - 1MB = 스택이 가질 수 있는 최대 크기의 최하단 주소가 된다.

if(USER_STACK - (1 << 20) <= addr && addr <= USER_STACK){
	= addr이 스택 영역 내를 가리킨다는 걸 의미
}

---

🛠️ Stack Growth로 page fault를 해결할 수 있는 경우인지 판별하기

그런데 접근한 가상주소가 stack인 경우더라도 모두 stack growth로 해결할 수 있는 건 아니다.
유저 프로그램은 스택 포인터 아래의 스택에 쓸 경우 버그가 발생하기 때문에, 'USER_STACK ~ 스택 포인터보다 높은 주소 값'인 경우에만 stack growth를 적용할 수 있다.

왜 스택 포인터 아래에선 stack growth를 적용할 수 없을까?? 🤔
: 스택 포인터보다 낮은 주소를 가리킬 때 해당 위치에 stack growth를 적용시키면 새 페이지를 할당하고 데이터를 써놓는다면, 데이터가 오염될 수 있다.
-> 이 말이 무슨 의미냐?
운영체제가 실행되다가 프로세스를 중단시킬 때 실행되던 정보를 stack에 저장하게 되는데, 스택 포인터 아래에 데이터를 써놓았다면? 데이터가 덮어씌워지면서 변경될 수 있다.
또한 이후에 rsp가 내려오면서 데이터를 삽입할 때도 마찬가지로 데이터가 덮어씌워질 수 있다.

그런데 스택 포인터보다 높은지 낮은지를 알기 위해서는 user stack의 스택 포인터(= rsp)를 먼저 알아내야 한다.

user program(User Mode)에서 발생한 page fault는 인자로 전달된 intr_frame을 통해 rsp로 가져올 수 있지만,

syscall(Kernel Mode)에서 발생한 page fault는 인자로 전달된 intr_frame->rsp가 user stack의 스택 포인터가 아닌 kernel stack의 스택 포인터를 얻게 된다.

따라서 kernel mode에서도 user stack의 rsp를 얻기 위해선 user mode->kernel mode 초기 전환 시(= syscall_handler()) struct thread에 저장해 전달하는 등의 방법을 준비해야 한다.

1. thread 구조체에 rsp 멤버변수 추가

struct thread 
{
	...
    #ifdef VM
	struct supplemental_page_table spt;
	void *rsp; // 스택 포인터 저장을 위한 멤버변수
	...
}

2. syscall_handler()에서 rsp 저장

void syscall_handler(struct intr_frame *f UNUSED)
{
	...
    /* 커널 모드로 전환될 때, 즉 시스템 콜이 호출될 때 스택 포인터 저장 */
	#ifdef VM
	thread_current()->rsp = f->rsp;
	...
}

이제 이 rsp를 활용해 판별할 수 있을 것이다.

그렇다면 조건문을 아래처럼 적용하면 될까?

void *rsp = f->rsp;
if (!user)
{
	rsp = thread_current()->rsp;
}
        
/* stack growth로 처리할 수 있는 경우 */
if (USER_STACK - (1 << 20) <= rsp && rsp <= addr && addr <= USER_STACK)
{
	vm_stack_growth(addr);
}

아니, 한 가지 고려할 경우가 더 있다.
rsp보다 낮은 주소에 접근하더라도 stack growth로 해결할 수 있는 경우가 있다.
x86-64의 PUSH 명령이다.

PUSH 명령은 스택 포인터를 조정하기 전에 접근 권한을 확인하기 때문에, 스택 포인터로부터 8바이트 아래에서 page fault를 발생시킬 수 있다.

rsp - 8byte인 이유? 🤔
스택에 값을 PUSH할 때, 64bit 시스템에서는 8byte 단위로 데이터를 push하기 때문이다. (register = rax)
물론 32bit 환경이라면 - 4byte이다. (register = eax)

그러니 가상주소가 rsp-8 을 가리키는 경우도 stack growth로 page fault를 처리할 수 있다.
최종 조건문은 아래와 같다.

bool vm_try_handle_fault(struct intr_frame *f UNUSED, void *addr UNUSED, bool user UNUSED, bool write UNUSED, bool not_present UNUSED)
{
	...
    /* 접근한 메모리의 물리 프레임이 존재하지 않는 경우, not_present = true */
	if (not_present)
	{
    	void *rsp = f->rsp;
		if (!user)
        {
			rsp = thread_current()->rsp;
        }
        
		/* stack growth로 처리할 수 있는 경우 */
		if (USER_STACK - (1 << 20) <= rsp && rsp <= addr && addr <= USER_STACK)
		{
			vm_stack_growth(addr);
		}else if(USER_STACK - (1 << 20) <= rsp - 8 && rsp - 8 == addr && addr <= USER_STACK){
        	vm_stack_growth(addr);
        }
        ...
    }
    return false;
}

해당 조건들을 아래와 같이 정리했다.

---

🛠️ Stack Growth 기능 구현

지금까지 stack growth로 페이지 폴트를 처리할 수 있는 경우를 따져 호출하는 것까지 구현했다.
이제 해당 함수만 구현하면 이번 파트의 과제를 완료한다.

vm_stack_growth() 구현은 사실 간단하다.
올바른 위치에 새 페이지를 할당하기만 하면 된다. 그렇다면 접근했던 주소가 faulted 주소에서 유효한 주소가 되어 page fault를 처리할 수 있다. 이를 위해 생각해야 할 점이 두 가지 있다.

1) 어떤 타입의 페이지를 할당해야 할까?
2) 어느 위치에서 페이지를 할당해야 할까?

일단 첫 번째는, 이전 파트인 anon 파트에 답이 있다.
anonymous page는 스택이나 힙 영역에서 사용된다고 했다.
아직 데이터가 매핑되지 않은 초기화된 페이지여야 하기 때문이다.

두 번째는 페이지 경계 주소 위치에서 할당해야 한다.
메모리는 페이지 단위로 관리되기 때문이다.

그렇다면 이를 토대로 vm_stack_growth()를 구현해보자.

static void
vm_stack_growth(void *addr UNUSED)
{
	/* addr을 PGSIZE 만큼 내려 anon page를 할당 */
	vm_alloc_page(VM_ANON | VM_MARKER_0, pg_round_down(addr), 1);
}

[최종 정리하자면]
1. page_fault 발생
2. vm_try_handle_fault() 호출
3. stack growth로 해결할 수 있는지 판별
4. 있다면 stack growth로 새 페이지 할당
5. spt에서 해당 가상 주소에 해당하는 페이지를 반환
6. 해당 페이지로 vm_do_claim_page()를 호출
7. 물리 프레임을 할당받고 매핑함으로써 page fault 처리

---

+) 추가로 정리할 것
: pg_round_down()이란 게 그냥 페이지 경계로 내림하는 매크로라고만 이해했었는데,
다른 동료의 발표를 듣고 더 자세히 알게된 점이 있다.

pg_round_down()? 🤔
가상주소는 PN(페이지 번호)+offset으로 이루어져 있다.
페이지 번호는 페이지 크기의 배수와 같고, 결국 페이지 경계는 페이지 번호나 마찬가지다.
offset은 해당 페이지 내의 정확한 위치를 지정하기 위한 부분이다.
그러니 pg_round_down은 offset을 떼어내 페이지 번호를 얻어내는 작업을 하는 것이다.
pg_round_down 매크로를 보면 더 자세히 알 수 있다.

/* Page offset bits (0:12). */
#define PGMASK  BITMASK(PGSHIFT, PGBITS)
/* Round down to nearest page boundary. */
#define pg_round_down(va) (void *) ((uint64_t) (va) & ~PGMASK)

---

이렇게 stack_growth 파트까지 완료했다.
stack 성장과 연관된 tc들이 통과하는 걸 확인할 수 있었다.

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
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
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
FAIL 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
FAIL tests/filesys/base/syn-read
pass tests/filesys/base/syn-remove
FAIL 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
35 of 141 tests failed.

---

⚙️ Modify List

- strcut thread
- syscall_handler()
- vm_try_handle_fault()
- vm_stack_growth()

---