[PintOS - VM] Stack Growth

Stack Growth

 

Userprog 에서는 아래와 같이 단일 페이지의 스택만을 활용하였다.

/* Create a minimal stack by mapping a zeroed page at the USER_STACK */
static bool
setup_stack (struct intr_frame *if_) {
	uint8_t *kpage;
	bool success = false;

	kpage = palloc_get_page (PAL_USER | PAL_ZERO);
	if (kpage != NULL) {
		success = install_page (((uint8_t *) USER_STACK) - PGSIZE, kpage, true);
		if (success)
			if_->rsp = USER_STACK;
		else
			palloc_free_page (kpage);
	}
	return success;
}

 

 

 

 

 

 

 

그리고,  앞선 Anonymous Page 에서는 아래와 같이 stack_bottom을 설정해주었다.

 

/* Create a PAGE of stack at the USER_STACK. Return true on success. */
static bool
setup_stack (struct intr_frame *if_) {
	bool success = false;
	void *stack_bottom = (void *) (((uint8_t *) USER_STACK) - PGSIZE);
	/* You might need to provide the way to identify the stack. */

	/* TODO: Map the stack on (1).stack_bottom and
	                          (2).claim the page immediately.

	/* TODO: You should mark the page is stack. vm_type of vm/vm.h (e.g. VM_MARKER_0) to mark the page. */
	/* (1) stack_bottomVM_ANON | VM_MARKER_0 을 사용하여 익명 페이지 + Stack임을 Marking 하자. */
	if (vm_alloc_page(VM_ANON | VM_MARKER_0, stack_bottom, 1)) {
		success = vm_claim_page(stack_bottom); // (2).claim the page immediately.
		if(success) {
			/* TODO: If success, set the rsp accordingly.*/
			if_->rsp = USER_STACK; 
			thread_current()->stack_bottom = stack_bottom; 
		}
	}
	return success;
}

 

 

이제, 요구 사항에 맞춰서 stack을 확장하는 기능을 추가하여야 한다!

 

 

Stack Growth! 📈

 

1. 스택 확장
   • 프로젝트 2에서는 스택이 USER_STACK에서 시작하는 단일 페이지였으며 (위의 코드 참조), 프로그램의 실행은 이 크기로 제한되었습니다. 이제 스택이 현재 크기를 초과하면 필요한 경우 추가 페이지를 할당합니다.
2. 스택 접근 구분
   • 추가 페이지는 "stack accesses"으로 보일 때만 할당해야 합니다. 스택 접근을 다른 접근과 구별하려는 휴리스틱을 고안하십시오.
   • if (rsp - 8 <= addr && addr <= USER_STACK && addr >= USER_STACK - (1<< 20) )
3. 사용자 프로그램의 버그
   • 사용자 프로그램은 스택 포인터 아래의 스택을 쓰면 안 됩니다 (이 부분에서 많은 버그가 발생합니다). 실제 운영 체제는 signal 을 전달하기 위해 언제든지 프로세스를 인터럽트할 수 있기 때문입니다.
   • 그러나 x86-64 PUSH 명령어는 스택 포인터를 조정하기 전에 접근 권한을 확인하므로, 스택 포인터 아래 8바이트에서 페이지 폴트가 발생할 수 있습니다.
     •  Push 명령어는 스택에 값을 넣기 전에 스택 포인터를 8바이트 감소시킨 후, 메모리에 값을 쓰고 스택 포인터를 업데이트하기 때문입니다.
4. 현재 스택 포인터 값 얻기
   • 현재 사용자 프로그램의 스택 포인터 값을 얻을 수 있어야 합니다.
   • 시스템 호출 또는 사용자 프로그램에 의해 생성된 페이지 폴트 내에서, rsp 멤버를 syscall_handler() 또는 page_fault()에 전달된 struct intr_frame에서 가져올 수 있습니다.
5. 페이지 폴트 처리
   • 커널에서 페이지 폴트가 발생하는 경우를 처리해야 합니다.
   • 프로세서가 사용자 모드에서 커널 모드로 전환될 때만 스택 포인터를 저장하므로, page_fault()에 전달된 struct intr_frame에서 rsp를 읽으면 정의되지 않은 값이 됩니다. -> 해당 rsp는 커널 스택을 가르키고 있습니다!
   • UserMode 에서 KernelMode로 전환 시 rsp를 struct thread에 저장해야 합니다!
6. 스택 확장 기능 구현
   • 스택 확장 기능을 구현합니다.
   • 먼저 vm/vm.c의 vm_try_handle_fault를 수정하여 스택 확장을 식별해야 합니다.
   • 스택 확장을 식별한 후, vm/vm.c의 vm_stack_growth를 호출하여 스택을 확장해야 합니다.
   • vm_stack_growth를 구현하십시오.

 

 

vm_stack_growth

/* Growing the stack. */
static void
vm_stack_growth (void *addr UNUSED) {
	// Make sure you round down the addr to PGSIZE when handling the allocation.
	vm_alloc_page(VM_ANON | VM_MARKER_0, pg_round_down(addr), true);
	// 이거랑 위랑 똑같음. 매크로써서 인터페이스(?) 처럼 구현한거같음.
	// vm_alloc_page_with_initializer(VM_ANON | VM_MARKER_0, stack_bottom, true, NULL, NULL) 
}

 

 

 

 

vm_try_handle_fault

/* 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;

	/* TODO: Validate the fault */
	/* TODO: Your code goes here */
	/* Stack 관련 fault 인지, 진짜 데이터가 없어서인지 구분해야함.*/
	if (addr == NULL || is_kernel_vaddr(addr)) {
		return false;
	}

	void *rsp = f->rsp;
	if (is_kernel_vaddr(f->rsp)) { // 만약 커널영역이라면, thread에 저장한 user_rsp를 사용.
		rsp = thread_current()->user_rsp;
	}

	/* not_present 가 true인 경우, 물리페이지가 없는 것이다. */
	if (not_present) {
		/* Stack Growth 처리 */
		/* 1. Fault Address가 현재 스택 포인터 위에 있어야 함 		     addr < USER_STACK */
		/* 2. Fault Address가 스택의 최대 크기 제한을 벗어나지 않아야 함    addr >= USER_STACK - 1MB && 1MB = 2^20 bytes	*/
		/* 3. PUSH 명령에 의해 발생한 경우를 처리  						 addr == rsp - 8 */
		if (rsp - 8 <= addr && addr <= USER_STACK &&  /* 1,3 번 케이스를 다룸 */
			addr >= USER_STACK - (1<< 20) ) { 		  /* 2번 케이스를 다룸 */
			/* 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. */
			vm_stack_growth(addr);
		}

		page = spt_find_page(spt,addr);
		if (page == NULL) {
			return false;
		}
		if (write) {
			if (vm_handle_wp(page)) {
				return false;
			}
		}
		return vm_do_claim_page(page); 
 	}
	return false;
}

 

1. 스택 확장 후 rsp 값을 변경하지 않는 이유
   • 스택 확장 작업은 페이지 폴트 핸들러에 의해 수행됩니다.
   • 페이지 폴트 발생 시점에서의 rsp 값은 스택 확장 이전의 스택 최상단을 가리키고 있습니다.
   • 스택 확장 후에 rsp 값을 변경하지 않는 이유는, 이전 스택 프레임과의 연속성을 유지하고 프로그램의 실행 흐름을 그대로 이어가기 위해서입니다.
   • 만약 스택 확장 후에 rsp 값을 새로운 스택 최상단으로 변경한다면, 이전 스택 프레임과의 연결이 깨질 수 있습니다.
   • 따라서 스택 확장 후에도 rsp 값을 그대로 유지함으로써, 프로그램은 스택 확장 이전의 rsp 값을 기준으로 계속 실행될 수 있습니다.

 

 

 

스택 테스트 코드 분석! 🧐

 

pt-grow-stack.c

 

0:  55                  push   %rbp
1:  48 89 e5            mov    %rsp, %rbp
4:  48 81 ec 10 11 00 00 sub    $0x1110, %rsp
b:  48 8d 85 fe ee ff ff lea    -0x1102(%rbp), %rax
12: ba 06 00 00 00       mov    $0x6, %edx
17: 48 be 00 00 00 00 00 00 00 00 movabs $0x0, %rsi

 

• push %rbp: 현재 프레임 포인터(%rbp)를 스택에 저장합니다.
• mov %rsp, %rbp: 스택 포인터(%rsp)의 값을 프레임 포인터(%rbp)에 복사하여 새로운 스택 프레임을 설정합니다.
• sub $0x1110, %rsp: 스택 포인터(%rsp)를 0x1110(4368) 바이트만큼 감소시켜 지역 변수용 공간을 할당합니다.
• lea -0x1102(%rbp), %rax: 프레임 포인터(%rbp)에서 0x1102(4354) 바이트 떨어진 주소를 계산하여 %rax에 저장합니다.
• mov $0x6, %edx: %edx 레지스터에 6을 저장합니다.
• movabs $0x0, %rsi: %rsi 레지스터에 절대값 0을 저장합니다.

 

 arc4_init ( &arc4, "foobar" 6);  함수 호출!

21: 48 89 c7            mov    %rax, %rdi
24: b8 00 00 00 00      mov    $0x0, %eax
2b: 00 00
2e: ff d0               callq  *%rax

 

 

• mov %rax, %rdi: %rax에 저장된 값을 첫 번째 인자(%rdi)로 이동합니다.
• mov $0x0, %eax: %eax 레지스터에 0을 저장합니다.
• callq *%rax: %rax에 저장된 주소로 함수 호출을 합니다.

 

memset (stack_obj, 0, sizeof stack_obj)  함수 호출!

30: 48 8d 85 00 f0 ff ff lea    -0x1000(%rbp), %rax
37: ba 00 10 00 00       mov    $0x1000, %edx
3c: be 00 00 00 00       mov    $0x0, %esi
41: 48 89 c7             mov    %rax, %rdi
44: b8 00 00 00 00       mov    $0x0, %rax
4b: 00 00
4e: ff d0                callq  *%rax

 

• lea -0x1000(%rbp), %rax: %rbp에서 0x1000(4096) 바이트 떨어진 주소를 계산하여 %rax에 저장합니다.
• mov $0x1000, %edx: %edx 레지스터에 4096을 저장합니다.
• mov $0x0, %esi: %esi 레지스터에 0을 저장합니다.
• mov %rax, %rdi: %rax에 저장된 값을 첫 번째 인자(%rdi)로 이동합니다.
• mov $0x0, %rax: %rax 레지스터에 0을 저장합니다.
• callq *%rax: %rax에 저장된 주소로 함수 호출을 합니다.

.. 이하 생략 ..

 

뭔가 주저리 주저리 많지만 핵심은 간단하다.

 

char stack_obj[4096];

struct arc4 arc4;

 

해당 자료구조의 크기( 0x1110 )만큼 스택을 할당한 뒤, 함수 루틴을 실행하는 것이다.

해당 어셈블리 코드에서는  arc4_init 함수에 관한 어셈블리어는 포함되지 않았다. 만약 해당 함수에서 더 큰 스택 크기를 요구한다면 어떻게 될까?