[Jungle] Week10. Pintos Project 3. Stack Growth

Stack Growth

-> 사용자 프로그램이 더 많은 스택 공간을 필요로할 때 Stack을 확장할 수 있도록

project 2에서 스택은 USER_STACK부터 시작하는 단일 페이지였다.

이제 project 3부터는 스택이 현재 크기를 초과하면 필요에 따라 추가 Page를 할당하도록 한다.

그렇다면 스택을 동적으로 할당하는 이유?

• 고정 할당의 문제점 : 예측 불가능한 사용량 -> 미리 큰 스택을 할당하면 메모리 낭비가 생긴다.
• 동적할당 -> 효율성: 필요한 만큼만 메모리를 사용하게끔

stack growth를 하는 시점

• page fault가 발생할 때
  : 프로그램이 실행되며 스택에 점점 데이터가 쌓이면 rsp(stack pointer)가 점점 내려간다.
  그러다가 할당된 스택 영역을 벗어나게 되면 Page fault가 발생한다.
  => page fault handler 가 호출되어 새로운 페이지를 할당하고 스택 크기를 늘린다.

---

• USER_STACK : 사용자 스택의 시작 주소
• 최대 스택 크기: 1MB

• USER_STACK - 1MB(0x100000) 보다 낮은 주소라면 잘못된 접근

• 접근한 주소는 USER_STACK과 USER_STACK - 1MB 사이가 되어야 한다.

• 스택 포인터(rsp)보다 높은 주소에 접근한 경우만 stack growth를 통해 페이지 폴트를 처리

• 스택 포인터 아래의 주소에 접근하는 것은 일반적으로 잘못된 접근으로 간주하지만,
  

• rsp - 8에 접근한 경우 (x86-64 PUSH 명령어)실행 시 stack growth를 통해 처리할 수 있다.
  => 함수 호출 시 매개변수를 스택에 전달하거나 함수 내에서 로컬 변수를 스택에 할당할 때

PUSH 명령어

1. rsp가 8byte 감소한다.
2. 감소된 rsp 주소에 데이터를 저장한다.
   일반적으로 rsp 아래 주소에 접근하는 것은 잘못된 접근이지만, PUSH 명령어로 인해 rsp가 감소하면서 새로운 페이지를 참조하게 되면 Page fault가 발생할 수 있다.
   -> 따라서 rsp - 8 주소에 접근한 경우에도 stack growth를 통해서 페이지 폴트를 처리할 수 있다.

예시>
현재 rsp가 0x7fffffffe000라고 가정하면,
PUSH 명령어가 실행되어 rsp가 0x7fffffffdff8로 감소하게 되고, 감소된 주소(0x7fffffffdff8)에 데이터를 저장하려고 시도
만약 0x7fffffffdff8 주소가 아직 할당되지 않은 페이지에 속해 있다면, 페이지 폴트가 발생
=> 운영체제는 page fault를 감지하고, 새로운 페이지를 할당하여 stack growth
이제 rsp - 8 주소에 데이터를 저장할 수 있게 된다.

---

rsp 유저 스택 포인터

• 사용자 모드에서의 page fault
  : struct intr_frame의 rsp가 유저 스택 포인터를 가리키고 있으므로 이를 사용하면 된다.
• 커널 모드에서의 page fault
  : struct intr_frame의 rsp가 커널 스택을 가리키고 있으므로 유저 스택 포인터를 얻기 위해서 thread 구조체 내에 저장된 rsp를 사용하면 된다.

1. rsp 스택 포인터를 확인
   : user mode or kernel mode에서 발생한 page fault인지에 따라 적절한 rsp를 가져온다.
2. page fault 주소가 user stack의 최대 범위에 있는지, rsp - 8 (PUSH 연산인지) 확인한다.
3. 위의 조건을 만족하면 vm_stack_growth 함수를 호출해서 스택에 추가 페이지를 할당하고 크기를 늘린다.

---

rsp ?

스택은 높은 주소에서 낮은 주소로 아래로 성장한다.

• rsp: 가장 최근에 추가된 데이터의 위치
• stack_bottom : 스택의 하단(가장 낮은 주소) - 스택 오버플로우는 이를 벗어날 때

높은 주소
|		   스택 
|  +------------------+
|  |                  |
|  |   이전 함수의    	  |
|  |   스택 프레임    	  |
|  |                  |
|  +------------------+
|  |  리턴 주소         |  <-  함수 호출 시 저장된 리턴 주소
|  +------------------+
|  |  매개변수 a        |  <- 함수의 매개변수
|  +------------------+
|  |  로컬 변수 b       |  <- 함수의 로컬 변수
|  +--------rsp-------+  <- 현재 스택 포인터 
|  |                  |
|  |      ....        |
|  |                  |
|  +------------------+
|  |                  |
|  +---stack_bottom---+
낮은 주소

---

vm_try_handle_fault

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;
	/* TODO: Validate the fault. page fault 주소에 대한 유효성 검증*/

	static void *STACK_MINIMUM_ADDR = USER_STACK - (1<<20); /* 스택이 확장될 수 있는 최하단 경계 주소
	1 << 20: 2의 20승 => 1MB (0x100000)
	스택의 최소 주소 - USER_STACK - (1MB) => 사용자 스택의 최상위 주소  - (1MB) */

	//page fault가 나는 주소 addr == NULL인 경우
	if (addr == NULL) 
		return false;

	/*접근한 가상 주소 va가 커널 주소인 경우 - return false
	사용자 프로그램이 커널 주소 공간에 접근하는 것을 막음
	사용자 요청에 의한 fault 또한 처리 불가 - return false */
	if (is_kernel_vaddr(addr))
		return false; 

	//not_present true => page fault가 발생한 경우
	//접근한 페이지의 물리적 페이지가 존재하지 않는 경우 
	if (not_present){
		struct thread *cur = thread_current();

		void *rsp = is_kernel_vaddr(f->rsp) ? cur->rsp : f->rsp; 

		if (rsp - 8 <= addr && STACK_MINIMUM_ADDR <= addr && addr <= USER_STACK){
			vm_stack_growth(pg_round_down(addr)); //stack growth
		}

		page = spt_find_page(spt, addr); //spt에서 addr와 일치하는 page가 있는지 찾기

		//page를 찾지 못하는 경우
		if (page == NULL){
			return false;
		}

		//쓰기 요청인데 페이지가 쓰기 불가능한 경우
		if (write && !page->writable) {
			return false;
		}
		//page를 claim하지 못한 경우 - addr와 kva 물리 메모리 프레임을 매핑하지 못한 경우 
		if (!vm_do_claim_page (page)) {
			return false;
		}
		//모든 조건을 만족하면 return true
		return true;
	}
	return false;
}

1. user mode 에서 page fault
   - intr_frame의 rsp에 현재 사용자 스택의 rsp, 스택 포인터가 저장되어 있을 것
2. kernel mode 에서 page fault
   - 커널 모드에서 intr_frame의 rsp에는 커널 스택의 rsp가 저장되어 있을 것
   - 따라서 사용자 모드에서 커널 모드로 전환될 떄 thread 구조체에 rsp를 저장해서 불러온다. (syscall_handler())
   

if (rsp - 8 <= addr && STACK_MINIMUM_ADDR <= addr && addr <= USER_STACK){
			vm_stack_growth(pg_round_down(addr));
}

addr(page fault가 발생한 va)가 사용자 스택의 가상 주소 범위를 초과하지 않는지 확인
rsp - 8 <= addr : 현재 스택 포인터에서 8 byte 아래까지의 주소보다 addr 이 크거나 같아야 한다.
STACK_MINIMUM_ADDR <= addr : 그리고 USER_STACK - 1MB 보다 낮은 주소이면 안된다.
addr <= USER_STACK : 또한 스택의 가장 큰 주소보다는 작거나 같아야 한다!

---

조건에 맞는다면 stack_growth로 fault를 해결해준다.

vm_stack_growth

static void
vm_stack_growth (void *addr UNUSED) {
	struct thread *cur = thread_current;

	//VM_ANON => stack은 파일 시스템에 직접 매핑되지 않는 메모리 영역 
	if (vm_alloc_page(VM_ANON | VM_MARKER_0, addr , 1)){

		cur->stack_bottom -= PGSIZE; 
		//stack_bottom을 한 페이지 크기만큼 내림 -> 새로운 페이지가 스택에 추가되어 아래로 성장
	}
}

vm_alloc_page로 새로운 페이지를 할당한다.

• VM_ANON: 파일 시스템과 매핑되지 않았으니 anonymous
• VM_MARKER_0: 스택 메모리임을 표시

---

이렇게 했을 때 35 of 141 나옴 - stack grow 관련 테스트가 통과되어야 한다.