[PintOS] Project 3 - Virtual Memory, Stack Growth

stack growth 부분 깃북을 정리해 보겠다.

 

프로젝트 2에서 스택은 USER_STACK이라는 주소에서 시작하는 '단일 페이지'였고, 이를 4KB로 제한하여 실행했다.

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

• 현재 크기라는 것이 1MB를 말하는 것인지 4KB를 말하는 것인지?

 

추가 페이지는 '스택'에 접근하는 경우에만 할당한다.

스택에 접근하는 경우와 아닌 경우를 구별하는 방법을 찾아야 한다.

• 페이지 폴트가 발생한 주소가 스택이라고 지정된 주소 사이인지를 검증하는 로직이 필요하다.

 

User program은 스택 포인터 아래의 스택에 쓸 경우 버그가 발생하는데, 이는 일반적인 실제 OS가 스택의 데이터를 수정하는 시그널을 전달하기 위해 프로세스를 언제든지 중단할 수 있기 때문이다. 하지만 x86-64 PUSH 명령어는 스택 포인터를 조정하기 전에 접근 권한을 검사하므로, 스택 포인터 아래 8바이트에 대해서 Page Fault를 발생시킬 수 있다.

• 페이지 폴트가 발생한 주소가 rsp보다 낮은 곳에 있으면 안되지만, 만약 스택 포인터보다 8바이트 낮은 곳이라면 접근 권한을 검사하기 위한 PUSH 명령어의 조치 중 하나로 발생할 수 있다.

User Program의 스택 포인터의 현재 값을 얻을 수 있어야 한다.

system call 또는 user program에 의해 발생한 page fault 루틴에서 각각 syscall_handler() 또는 page_fault()에 전달된 struct intr_frame의 rsp멤버에서 검색할 수 있습니다.

• rsp를 가져올 수 있어야 하는데, user program에 의해서 발생한 page_fault()에서 어떻게 가져올지와 system_call()을 통해서 발생한 커널 단에서의 rsp 처리를 할 수 있어야 한다.

잘못된 메모리 접근을 감지하기 위해 Page Fault에 의존하는 경우, 커널에서 page fault가 발생하는 경우도 처리해야 한다. 프로세스가 스택 포인터를 저장하는 것은 예외로 인해 유저 모드에서 커널 모드로 전환될 때 뿐이므로 page_fault()로 전달된 struct intr_frame에서 rsp를 읽으면 유저 스택 포인터가 아닌 정의되지 않은 값을 얻을 수 있다.

유저 모드에서 커널 모드로 전환 시 struct thread에 저장하는 것과 같은 다른 방법을 준비해야 한다.

• 커널에서 page_fault가 발생하고 그 인터럽트 프레임의 rsp를 참조하면 그것은 커널의 스택 포인터이다. 우리는 유저 프로그램의 스택 포인터를 조절하는 것이므로, system call에서 커널 모드로 전환되기 전 유저 프로그램의 스택 포인터를 어떻게 받아올지 생각해 봐야 한다.

스택 증가 기능을 구현한다.

이 기능을 구현하려면 먼저 vm/vm.c에 있는 vm_try_handle_fault를 수정하여 stack growth를 확인한다.

stack growth를 확인한 후에는 vm/vm.c에서 vm_stack_growth를 호출해서 스택을 증가시켜야 한다.

vm_stack_growth를 구현해라.

• stack growth를 확인하라는 말은 stack growth가 가능한지를 확인하라는 말이다. 조건에 맞으면 vm_stack_growth()를 호출한다.

bool vm_try_handle_fault (struct intr_frame *f, void *addr,
    bool user, bool write, bool not_present);

 

이 함수는 page fault 예외를 처리하는 동안 userprog/exception.c의 page_fault()안에서 호출된다.

page fault가 스택을 증가시켜야 하는 경우에 해당하는지 아닌지를 확인해야 한다.

stack growth로 page fault 예외를 처리할 수 있는지 확인한 경우, page fault가 발생한 주소로 vm_stack_growth를 호출한다.

• page_fault() 내에서 #ifdef VM으로 선언되어 있고, VM일 경우 실제로 page fault를 처리하는 로직을 갖는다. stack growth가 가능하다면 이를 수행하고, 가능하지 않다면 수행하지 않는 로직을 추가해야한다.

void vm_stack_growth (void *addr);

 

하나 이상의 anonymous 페이지를 할당하여 스택 크기를 늘린다. 이로써 addr은 폴트가 발생한 주소 내에서 유효한 주소가 된다.

페이지를 할당할 때는 주소를 PGSIZE 기준으로 내림해라.

• 모든 조건을 통과하고 난 다음에, addr에 페이지를 할당하면 스택 크기가 늘어난다. pg_round_down을 사용해야 할 듯 싶다.

대부분의 OS에서 스택 크기는 절대적으로 제한되어 있지만, 일부 OS는 사용자가 크기 제한을 조정할 수 있게 한다.

많은 GNU/Linux 시스템에서 기본 제한은 8MB이지만, 이 프로젝트는 스택 크기를 최대 1MB로 제한한다.

• 핀토스의 스택 크기는 최대 1MB이다. 이는 프로세스 별 스택 크기인가?

따라서 다음과 같이 분기를 나누어 보았다.

stack growth 구현을 위한 여러 조건 처리

 

이를 위해 수정한 것들을 보겠다.

vm_try_handle_fault()

bool
vm_try_handle_fault (struct intr_frame *f, void *addr,
        bool user, bool write, bool not_present) {
    struct supplemental_page_table *spt = &thread_current ()->spt;
    struct page *page = NULL;
    /* TODO: Validate the fault */
    // implementation - pongpongie
    // TODO: 스택 증가를 확인하는 로직 추가
    // TODO: 스택을 증가시켜도 되는 경우인지 아닌지 확인
    // TODO: 만약 스택을 증가시켜도 되는 경우라면, addr로 vm_stack_growth 호출
    if (addr == NULL)
    {
        return false;
    }

    if (is_kernel_vaddr(addr))
    {
        return false;
    }
    
    // physical page가 존재하지 않는 경우
    if (not_present)
    {
        struct thread *t = thread_current();
        void *rsp;
        if (user)  // page fault가 user mode에서 발생한 경우
        {
            rsp = f->rsp; // rsp는 매개변수인 intr_frame 구조체에서 호출하면 됨
        }

        if (!user) // page fault가 kernel mode에서 발생한 경우
        {
            rsp = t->stack_pointer; // rsp는 유저 모드에서 커널 모드로 전환 이전의 값을 저장한 stack_pointer을 사용해야 유저 스택의 값을 가리킬 수 있음
        }

        if (addr <= USER_STACK && USER_STACK - (1 << 20) <= addr)
        {
            if (addr >= rsp)
            {
                vm_stack_growth(addr);
            }
            if (rsp - 8 == addr)
            {
                vm_stack_growth(addr);
            }
        }
    
        page = spt_find_page(spt, addr);
        if (page == NULL)
        {
            return false;
        }
        if (!page->writable && write)   // 쓰기가능하지 않은데 쓰려고 한 경우
        {
            return false;
        }
        return vm_do_claim_page(page) ? true : false;
    }
    return false;
}

 

 

깃북에서 설명한 조건들을 만족시키기 위해 분기를 나누어 처리했다.

코드가 더럽긴 하지만 나에게 가장 직관적이어서 더 수정하지 않았다.

 

struct thread

struct thread {
	/* Owned by thread.c. */
	tid_t tid;                          /* Thread identifier. */
	enum thread_status status;          /* Thread state. */
	char name[16];                      /* Name (for debugging purposes). */
	int priority;                       /* Priority. */
	int original_priority;				/* 원래의 우선도(priority)*/
	int64_t sleep_ticks; 				/* 자고 있는 시간*/
	int has_lock;
	/* Shared between thread.c and synch.c. */
	struct list_elem elem;              /* List element. */
	struct list_elem donor_elem;

	struct list donors;					/* 해당 쓰레드에 기부한 목록*/
	struct lock *wait_on_lock;			/* 이 락이 없어서 못 가고 있을 때*/

	int nice_value;
	int recent_cpu;
	struct list_elem all_elem;
	
#ifdef USERPROG
	/* Owned by userprog/process.c. */
	uint64_t *pml4;                     /* Page map level 4 */
	struct list fd_table;
	unsigned last_created_fd;


#endif
#ifdef VM
	/* Table for whole virtual memory owned by thread. */
	struct supplemental_page_table spt;
    void *stack_pointer;
#endif
    
	/* Owned by thread.c. */
	struct intr_frame tf;               /* Information for switching */
	unsigned magic;                     /* Detects stack overflow. */

	//구현
	struct list child_list;
	struct list_elem child_list_elem;

	struct thread *parent;


	int exit_status; 

	struct intr_frame parent_tf;
	// struct file **descriptor_table;
	int fd_idx;

	struct file *running;
	/* 자식 프로세스의 fork가 완료될 때까지 기다리도록 하기 위한 세마포어 */
	struct semaphore process_sema;
	struct semaphore wait_sema;
	struct semaphore exit_sema;
};

 

 

stack_pointer를 추가하여 user mode에서 kernel mode로 넘어갈 때 유저 스택 포인터를 스레드에 저장할 수 있도록 한다.

syscall_handler()

void
syscall_handler (struct intr_frame *f) {
	// TODO: Your implementation goes here.

	struct thread *t = thread_current();
	t->tf = *f;

	// int size = palloc_init();
	
	//주소가 유호한지 확인
	if(!is_user_vaddr(f->rsp)){
		printf("isnotvaddr\n");
		thread_exit();
	}

	else if(f->rsp > KERN_BASE || f->rsp < 0){
		printf("smaller\n");
		thread_exit();
	}
	
	int addr = (f->rsp + 8);
	if (!is_user_vaddr(addr) || (addr > KERN_BASE || addr<0)) {
		printf ("third condition\n");
		thread_exit();
	}
    #ifdef VM
    thread_current()->stack_pointer = f->rsp;
    #endif

	// addr = f->R.rsi;
	
	switch(f->R.rax){
	case SYS_HALT:
		halt();
		break;		
        
	...

	case SYS_CLOSE:
		close(f->R.rdi);
		break;

	default:
		break;
	}
}

 

#ifdef로 전처리 선언을 해서, 커널로 넘어가는 switch 문으로 가기 전에 스레드의 stack_pointer에 interrupt frame의 rsp를 저장할 수 있도록 한다.

 

Reference

https://e-juhee.tistory.com/entry/Pintos-KAIST-Project-3-Stack-Growth-Pintos%EC%9D%98-%EC%8A%A4%ED%83%9D-%ED%99%95%EC%9E%A5-%EB%A9%94%EC%BB%A4%EB%8B%88%EC%A6%98

[Pintos-KAIST] Project 3 :: Stack Growth (Pintos의 스택 확장 메커니즘)