Project3 Final

[Daegyeom-Ryu]

hash 테이블에서 va에 해당하는 페이지 찾기

💡 해쉬 구조체에는 page에 대한 정보가 없음

struct hash {
	size_t elem_cnt;            /* Number of elements in table. */
	size_t bucket_cnt;          /* Number of buckets, a power of 2. */
	struct list *buckets;       /* Array of `bucket_cnt' lists. */
	hash_hash_func *hash;       /* Hash function. */
	hash_less_func *less;       /* Comparison function. */
	void *aux;                  /* Auxiliary data for `hash' and `less'. */
};

💡 페이지 구조체에는 hash 테이블의 구성요소인 hash_elem이 있음

struct page {
	const struct page_operations *operations;
	void *va;              /* Address in terms of user space */ 	// va는 hash table의 key가 된다. page->va
	struct frame *frame;   /* Back reference for frame */
	struct hash_elem hash_elem;	//spt의 구성요소
	...
}

❗ hash 테이블에서 va에 해당하는 페이지를 찾기 위해서는 hash_elem을 통해 접근해야 함 hash_entry 사용해서 hash_elem을 page로 변환할 수 있고 page→va 찾을 수 있음

→ hash 테이블의 인덱스에 접근할 수 있는 hash 함수 사용해서 bucket 찾음
→ bucket에서 less 함수를 사용해서 bucket에 담긴 hash_elem의 va와, 더미에서 넘긴 hash_elem의 va가 같은지 확인

code flow

spt_find_page→hash_find→find_bucket(with hash)→find_elem(with less)

1. spt_find_page (struct supplemental_page_table *spt UNUSED, void *va UNUSED)
   1. dummy page를 만들고, 받은 va를 VPN으로 바꾸고 page→va에 저장
   2. hash_find로 hash 테이블에서 va 해당하는 hash_elem 찾기
   3. 인자로 hash 테이블과 더미페이지의 hash_elem 넘김
2. hash_find(&spt→spt_hash, &page→hash_elem)// h: &spt→spt_hash, e: &page→hash_elem
   1. find_elem(h,find_bucket(h,e),e) 호출 → 인자로 find_bucket(h,e)
3. find_bucket(h, e)
   1. hash 함수인 hash를 사용해서 인덱스를 얻어내서 그 인덱스에 해당하는 bucket 찾음
4. find_elem(h,bucket,e)
   1. bucket에서 less를 사용해서 bucket에 담긴 hash_elem의 va와, 더미에서 넘긴 hash_elem의 va가 같은지 확인 후 bucket의 hash_elem의 주소 반환
5. hash_entry 사용해서 bucket의 hash_elem을 page로 변환

---

tests/vm/swap-fork 실패 트러블 슈팅

❗테스트 실행 시, swap-fork가 터지면서 아래 오류가 발생한다.
→ Kernel panic in run: PANIC at ../../threads/thread.c:330 in thread_yield(): assertion `!intr_context ()' failed.
→ thread_yield() 함수에서의 ASSERT (!intr_context ()) 부분에서 문제가 발생하는 것 같다.
→ intr_context() 함수는 외부 인터럽트를 처리 중일 때는 true를 반환하고, 아니면 false를 반환하는 함수다.
→ 즉, 외부 인터럽트가 들어오면 테스트에서 FAIL이 발생하는 것이다.
→ 따라서, 외부 인터럽트가 아닐 때만 thread_yield() 함수를 실행하도록 아래와 같이 코드를 수정했다.

→ 수정 전, 코드

/* ready_list에서 우선순위가 가장 높은 스레드와 현재 스레드의 우선순위를 비교하는 함수 */
void test_max_priority (void) {
	// Ready_list가 비어있지 않고, ready_list에서 우선순위가 가장 높은 스레드보다 현재 스레드의 우선순위가 더 작은 경우
	if(!list_empty (&ready_list) && ((thread_current ()->priority) < (list_entry(list_front (&ready_list), struct thread, elem)->priority))) {
		thread_yield (); // thread_yield() 함수를 호출하여 현재 스레드의 CPU를 양보
	}
}

→ 수정 후, 코드

/* ready_list에서 우선순위가 가장 높은 스레드와 현재 스레드의 우선순위를 비교하는 함수 */
void test_max_priority (void) {
	// Ready_list가 비어있지 않고, ready_list에서 우선순위가 가장 높은 스레드보다 현재 스레드의 우선순위가 더 작은 경우
	if(!list_empty (&ready_list) && ((thread_current ()->priority) < (list_entry(list_front (&ready_list), struct thread, elem)->priority))) {
		if (!intr_context()) {
			thread_yield (); // thread_yield() 함수를 호출하여 현재 스레드의 CPU를 양보
		}
	}
}

---

stack_growth() 트러블 슈팅

stack_growth()를 구현 하는 중
💡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)

    /* ...... */

   if ((USER_STACK - (1 << 20) <= rsp - 8 && rsp - 8 == addr && addr <= USER_STACK) ){
			vm_stack_growth(addr);
		}


    /* ...... */

💡vm_stack_growth()

vm_stack_growth (void *addr UNUSED){
   vm_alloc_page(VM_ANON | VM_MARKER_0, pg_round_down(addr), 1); // 1 anon페이지 할당 
}

처음엔 이렇게 page_fault가 발생할 때 USER_STACK 안에서 rsp-8과 page_fault 주소 addr이 같은 곳을 가리키면 stack_growth를 실행하게 구현을 했었는데,

💡pt-grow-stack.c

void
test_main (void)
{
  char stack_obj[4096];  
// pt-big-stk-obj.c 에서는  char stk_obj[65536];

  struct arc4 arc4;

  arc4_init (&arc4, "foobar", 6);
  memset (stack_obj, 0, sizeof stack_obj);
  arc4_crypt (&arc4, stack_obj, sizeof stack_obj);
  msg ("cksum: %lu", cksum (stack_obj, sizeof stack_obj));
}

pt-grow-stack 테스트에서는 문제가 없었지만 pt-big-stk-obj 테스트에서는 stk_obj[65536] 크기의 공간을 할당하다보니 rsp보다 addr의 위치가 더 위쪽에 있는 경우가 발생하는데 그 부분을 처리를 해주지 않아서 big-stk 테스트에서 fail이 발생함.
그래서 stack_growth를 page_fault가 발생하면 addr 주소를 0x1000만큼 증가시키고 spt_find_page(&thread_current()->spt,addr)를 반복하며 해결함

💡vm_stack_growth()

static void
vm_stack_growth (void *addr UNUSED) {
    /* 스택 크기를 증가시키기 위해 anon page를 하나 이상 할당하여 주어진 주소가 더 이상
    예외 주소(faulted address) 가 되지 않도록 합니다. */
     struct page *page = NULL;
	 addr = pg_round_down(addr);
     while(true){
         if(page = (struct page*)spt_find_page(&thread_current()->spt,addr)){
             break;
         }else{
            vm_alloc_page(VM_ANON | VM_MARKER_0, addr, 1); // 1 anon페이지 할당 
            addr += 0x1000;
         }
     }
}
}

해결을 하고 다른 사람은 어떻게 했나 궁금해서 찾아보니 아래의 방식으로 계속 page_fault를 발생할때마다 stack_growth를 해주는 방법도 있었습니다.

💡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)

    /* ...... */

   if ((USER_STACK - (1 << 20) <= rsp - 8 && rsp - 8 == addr && addr <= USER_STACK) ){
			vm_stack_growth(addr);
		}

else if (USER_STACK - (1 << 20) <= rsp && rsp <= addr && addr <= USER_STACK)
			vm_stack_growth(addr);


    /* ...... */

💡vm_stack_growth()

static void
vm_stack_growth (void *addr UNUSED) {
  vm_alloc_page(VM_ANON | VM_MARKER_0, pg_round_down(addr), 1); // 1 anon페이지 할당 
}