크래프톤 정글 WEEK11 DAY 86 - PintOS Project3 - Stack Growth 완성

📆2024.4.1

1. Stack Growth 완성
2. 백준 - 숨바꼭질

 

 

Stack Growth 조건

 

1. addr이 rsp보다 높은 주소를 가리켜야 한다.

2. rsp - 8에 접근한 경우에도 stack growth로 해결한다.

3. USER_STACK 아래에 있어야 하고, USER_STACK - (1MB) 위에 있어야 한다. -> USER_STACK 영역 내에 있어야 한다.

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;
    if (addr == NULL)
        return false;

    if (is_kernel_vaddr(addr))
        return false;

    // true: addr에 매핑된 physical page가 존재하지 않는 경우에 해당한다.
    // false: read only page에 writing 작업을 하려는 시도에 해당한다.
    if (not_present) // 접근한 메모리의 physical page가 존재하지 않은 경우
    {
        /* TODO: Validate the fault */
        // 페이지 폴트가 스택 확장에 대한 유효한 경우인지를 확인한다.

        void *rsp = f->rsp; // user access인 경우 rsp는 유저 stack을 가리킨다.
        if (!user)            // kernel access인 경우 thread에서 rsp를 가져와야 한다.
            rsp = thread_current()->stack_rsp;

        // 스택 확장으로 처리할 수 있는 폴트인 경우, vm_stack_growth를 호출한다.
        if (USER_STACK - (1 << 20) <= rsp - 8 && rsp - 8 <= addr && addr <= USER_STACK)
            vm_stack_growth(addr);

        page = spt_find_page(spt, addr);
        if (page == NULL)
            return false;
        if (write == 1 && page->writable == 0) // write 불가능한 페이지에 write 요청한 경우
            return false;
        return vm_do_claim_page(page);
    }
    return false;
}

 

stack_bottom을 이용해서 구현하려 했지만 어려움을 겪고 테스트가 왜 안되는거야!!..

 

static void
vm_stack_growth (void *addr UNUSED) {
	vm_alloc_page(VM_ANON|VM_MARKER_0, pg_round_down(addr), true);
}

 

 

1. tests/vm/pt-write-code / tests/vm/pt-write-code2

 

이 테스트를 통과하려면 시스템 콜 read 함수를 수정해야 했다.

계속해서 저 테스트 부분에서 fail이 떠서 곰곰히 생각해보다 시스템 콜 쪽 문제일 것 같다는 생각이 들었고 나의 생각이 맞았다는 점이 기뻤다!

 

일단 현재 인자로 주어진 버퍼가 spt에 있는지 확인 후 page를 받아서 해당 page의 쓰기 가능 여부를 확인하고 아니라면 exit(-1)을 했어야 했다.

 

그러나 나의 습관적인 실수로 page가 있는데 이 해당 page가 쓰기가 불가능해! 그러면 나가! 라고 했어야 했떤걸 !page &&!page->writable 로 걸어둬서 자꾸 fail이 떴었던.. 문제가 있었다

 

동료 분이랑 얘기하다 뭔가 잘못된 점을 깨닫고 바로 수정해주었다.

 

🤔의문이었던 점

처음에 왜 read()에서 현재 페이지가 쓰기 가능한지 여부를 체크하지? write가 아니라 왜 read에서? 라는 생각이 들었었다. 

read는 파일에서 buffer로부터 읽는것(써주는 것) 이고, read , write 모두 쓰기한 페이지여야 한다고 한다.

그래서 쓰기 가능해야 buffer에 쓸 수 있으니까 read에서 체크를 하는 것!

둘 다 해줘도 상관 없다고 한다.

 

int read(int fd, void *buffer, unsigned size) {
	check_address(buffer);
	int byte = 0;
	char *_buffer;
	if (fd == STDIN_FILENO) {
		_buffer = buffer;
		while (byte < size) {
			_buffer[byte++] = input_getc();
		}
	}
	else{
		struct file *_file = get_file_from_fd(fd);
		if (_file == NULL) {
			return -1;
		}
		struct page * _page = spt_find_page(&thread_current()->spt, buffer);
		if(_page && !_page->writable){
			exit(-1);
		}
		lock_acquire(&filesys_lock);
		byte = file_read(_file, buffer, size);
		lock_release(&filesys_lock);
	}
	return byte;
}

 

 

 

2. tests/vm/pt-grow-stk-sc

 

이 테스트는 동적 변수가 아닌 정적 변수를 만들어서 두 개의 데이터가 같은지 일관성을 확인하는 테스트였다. 

다른 테스트는 다 통과하는데 이 테스트만 통과가 안돼서 printf 문을 하나씩 찍으면서 확인해보니 check_address()에서 걸린다는 점을 확인했다!

 

정적 변수는 동적 변수가 아니기 때문에 page가 없으니까 당연히 spt_find_page() 예외처리문에서 걸려 종료되었던 문제였다.

그래서 이 예외처리를 주석 처리해주니 성공!!

	// if(spt_find_page(&thread_current()->spt, (void *)addr) == NULL) {
	// 	exit(-1);
	// }

 

 

stack growth 전체 통과로 이제 33 failed!

 

stack growth 생각보다 간단하고 코드도 많이 추가 안했는데 왜이리 시간을 오래 보냈는지...ㅜㅜ 그래도 이해하고 넘어갔으니 다행이라고 생각한다.

 

백준 숨바꼭질

 

x - 1, x + 1, x*2 세 가지의 조건을 확인하는 게 어려웠다.

import sys
from collections import deque
input = sys.stdin.readline

def bfs(n):
    q = deque()
    q.append(n)
    
    while q:
        x = q.popleft()
        if x == K:
            print(dist[x])
            break
        for nx in (x-1, x+1, x*2):
            if 0 <= nx <= MAX and not dist[nx]:
                dist[nx] = dist[x] + 1
                q.append(nx)
                
N, K = map(int,input().split())
MAX = 10**5
dist = [0] * (MAX+1)

bfs(N)