PintOS P3 #4 : SPT를 비롯한 구현

기존 글에서 구현 해야 할 네 가지를 다루었다. 이 네 가지는 너무 극 요약 한 것에 불과해서, 실제 구현에서만 다룰 수 있는 이게 뭐야 싶은 상황도 보게 될 것이다. 하지만 언제 그랬냐는듯 너만의 PintOS를 완성할 것이다. 아마도..

---

2025.06.03 - [구현하기] - PintOS P3 #3 : 뭐부터 할지 논하기

PintOS P3 #3 : 뭐부터 할지 논하기

이전 글에서 이어진다.

1. load_segment는 페이지 크기 단위의 순회를 돈다. 페이지 하나가 가리켜질 때 정보 누락이 없이 남김없이 챙겨서 alloc_page_with_initializer에 넘기는걸 목표로 하자.
2. SPT에 담기는 영역을 논하려면 SPT 초기화, SPT Insert, Find 해서 적어도 세 개는 구현해야겠다.
3. page fault가 발생하면 SPT에서 찾는 내용으로 연결 시켜야겠다. 찾으면 프레임에 담아다가 올리는 영역도 필요할 것이다.
4. 그리고 setup_stack을 이용한 스택 설정까지 마치면 진짜 정말 되는 것이다.

 

1. load_segment를 비롯한 load 계열 구현

• load_segment, lazy_load_segment를 구현하는 것이 목표이다.
• load_segment는 기존 Project 2와 유사한 구조이다.
  • load에서 발생한 read_bytes와 zero_bytes 중 하나가 양수 인 경우 계속 돌아간다.
  • 이 while문은 4KB 단위로 SPT에 등록하는 역할을 하는 것이다. 파일에 대한 정보를 논 할 구조체 한 개가 필요 할 것이다.

struct file_lazy_aux {
	struct file *file;
	off_t ofs;
	size_t read_bytes;
	size_t zero_bytes;
    bool writable; // for permission bit in page table
}; // 이 내용은 재량껏 vm.h에 추가한다.

static bool load_segment (struct file *file, off_t ofs, uint8_t *upage,
		uint32_t read_bytes, uint32_t zero_bytes, bool writable) {
	ASSERT ((read_bytes + zero_bytes) % PGSIZE == 0);
	ASSERT (pg_ofs (upage) == 0);
	ASSERT (ofs % PGSIZE == 0);

	while (read_bytes > 0 || zero_bytes > 0) {
		/* Do calculate how to fill this page.
		 * We will read PAGE_READ_BYTES bytes from FILE
		 * and zero the final PAGE_ZERO_BYTES bytes. */
		size_t page_read_bytes = read_bytes < PGSIZE ? read_bytes : PGSIZE;
		size_t page_zero_bytes = PGSIZE - page_read_bytes;

		/* TODO: Set up aux to pass information to the lazy_load_segment. */
		struct file_lazy_aux* fla
        		= (struct file_lazy_aux *)malloc(sizeof(struct file_lazy_aux));
		fla->file = file;					 // 내용이 담긴 파일 객체
		fla->ofs = ofs;					 // 이 페이지에서 읽기 시작할 위치
		fla->read_bytes = page_read_bytes; // 이 페이지에서 읽어야 하는 바이트 수
		fla->zero_bytes = page_zero_bytes; // 이 페이지에서 read_bytes만큼 읽고 공간이 남아 0으로 채워야 하는 바이트 수
		fla->writable = writable;

		if (!vm_alloc_page_with_initializer (VM_ANON, upage,
					writable, lazy_load_segment, fla))
			return false;

		/* Advance. */
		read_bytes -= page_read_bytes;
		zero_bytes -= page_zero_bytes;
		upage += PGSIZE;

		ofs += page_read_bytes;
	}
	return true;
}

vm_alloc_page_with_initializer(..)는 3번에서 구현하겠다. 

파일 한 개가 10KB라고 가정해보자. 그러면 while문은 4KB단위로 끊어야 하기 때문에 세 번 수행된다. 그리고 당연한 이야기지만 한 프레임 내지 한 페이지에 두 개의 파일을 담을 수 없다. 그래서 file_lazy_aux 구조체에 file을 한 개만 논하는 것은 지극히 상식적이다.

4KB 단위로 한개, 4KB 단위로 한 번 더, 그리고 2KB가 실제 내용이고 2KB가 비어있는 상태로 불린다. load_segment를 호출하며 동시에 가져와야 했던 매개변수들을 적극적으로 vm_initializer 메서드에 넘기는 모습이다.

 

bool lazy_load_segment (struct page *page, void *aux) {
	ASSERT(page != NULL);
	struct file_lazy_aux *fla = (struct file_lazy_aux *) aux;
	ASSERT(fla != NULL);

	uint8_t *kva = page->frame->kva;

    if (file_read_at(fla->file, kva, fla->read_bytes, fla->ofs) != (int) fla->read_bytes)
        return false;

	memset(kva + fla->read_bytes, 0, fla->zero_bytes);

	return true;
}

lazy_load_segment의 존재 의의는 Lazy Loading으로, 필요할때 불러온다는 것이 주된 요약이다. 즉, 페이지 하나를 SPT에 등록 할 떄 이러한 콜백 함수를 같이 등록 시킨다. 그리고 앞에서 봤던 load_segment에서 aux를 각 파일에 대한 범위로써 던진 매개변수를 받아와서 해당 내용으로 file 계열 함수를 작동시킴으로써 실제 Lazy Load를 실현 할 수 있다.

---

2. SPT에 대한 메서드들을 만들기 | init, insert, find

• SPT는 해시 테이블로 만들어야한다고 권장되고 있으니, 이에 대한 범용적 구성체인 hash.c에서 요구하는 형태만 갖추어서 init을 만들 것이다.
• insert, find 모두 이러한 사전 정의된 해시 테이블의 함수를 이용한 형태를 취 할 것이다.

struct supplemental_page_table {
	struct hash main_table;
};

SPT 자체는 무척 간단하게 구현된다.

 

void
supplemental_page_table_init (struct supplemental_page_table *spt ) {
	hash_init(&spt->main_table, page_hash, page_less, NULL);
}

hash_init은 해시 테이블을 초기화하는데, 이 부분에 대해 형식상으로건 아니건 채워주어야 할 것이 있다 :

• spt->main_table : 무슨 테이블을 초기화 하시는데요?
• page_hash : 이 테이블에 검색 조건 내지 입력을 받으면, 어떤 내용에 어떤 해시 함수를 쓸까요?
• page_less : 동일한 버킷에 배치될경우, 어떤 것이 우선 되면 좋을까요?
• aux : hash, less에 논해지는데에 적합한 매개변수가 있나요?

논외로, page_less는 이 해시 테이블이라는 자료구조의 범용성 때문에 필요한 것이지, SPT 형성에 그다지 기여도 있는 함수는 아닌걸로 보인다. 여기서 마음 가짐이 확실히 괜찮다라고 느낀 것이, 안되면 그 때 생각하고 작동되면 그냥 되는 거겠거니 짚고 넘어가는것이 최고다.

page_hash, page_less는 hash.c에서 다양한 참조가 가능한데 우리 팀원분이 간단하게 구현해주셨다.

unsigned page_hash(const struct hash_elem *p_, void *aux UNUSED) {
	const struct page *p = hash_entry(p_, struct page, page_hashelem);
	return hash_bytes(&p->va, sizeof p->va);
}

hash_bytes는 uint64_t 타입 함수인데, va를 적절히 던져서 괜찮은 hash로 변환한다. 이미 제공되는 함수이다. 그냥 있는대로 쓰기~

 

bool page_less(const struct hash_elem *a_,
			   const struct hash_elem *b_, void *aux UNUSED
){
	const struct page *a = hash_entry(a_, struct page, page_hashelem);
	const struct page *b = hash_entry(b_, struct page, page_hashelem);
	return a->va > b->va;
}

page_less는 동일 버킷 기준으로 가상주소의 순수 값이 더 큰 놈이 우선시 시키기로 한다. 사실 별 의미 없음. 담기기만 하면 됐다.

 

이제 Insert 해보자. 아이템이 있어야 Find 하니 Insert부터 할 거임

bool spt_insert_page (struct supplemental_page_table *spt ,struct page *page) {
	int succ = true;
	struct hash_elem *result = hash_insert(&spt->main_table, &page->page_hashelem);
	if(result != NULL) succ = false;
	return succ;
}

 

ㅁ

이거 심각하게 주의 :

result == NULL이 실패가 아니다 Not NULL이 실패다 왜냐하면 hash_insert는 중복을 허용하지 않아서 중복이 있는 경우 기존 아이템을 반환하려고 하기 때문이다 하지만 우리는 삽입 성공 여부만 봐야하기 때문에 Not Null은 실패라고 가정해야한다 이 점을 부디 조심하길 기대한다.......

그 부분만 빼면 그냥 hash_insert를 하는 간단한 형태이다. vm.c에서 작성하는 만큼 hash.h를 불러오기 때문에 hash_insert를 다이렉트로 때려박는 경우도 물론 가능하지만, 이왕이면 성공 실패여부를 따질 수 있는 이 함수를 사용하면 좋다..

 

 

Find 해보자.

struct page * spt_find_page (struct supplemental_page_table *spt, void *va){
    ASSERT (spt != NULL);
	
    /* VA의 field set 기반으로 더미 struct page를 만듦 */
	struct page* page_p = (struct page *)malloc(sizeof(struct page));
	struct page* found_page = NULL;
    page_p->va = pg_round_down (va); // 페이지 경계에 맞도록 조정

    /* 해시 테이블을 조회 */
    struct hash_elem *e = hash_find (&spt->main_table, &page_p->page_hashelem);
    if (e != NULL){
		found_page = hash_entry (e, struct page, page_hashelem);
	}
	free(page_p);
    return found_page;
}

insert나 find나 해쉬 함수는 va 하나로 따지지만, 구색 갖추기를 위해 그 va를 담기 위한 페이지를 따로 만들어서 검색 조건으로 던지게 된다. 즉, SPT의 본체인 해쉬 테이블이 알아 들을 수 있는 형태로 만들어준다에 의의가 있다. hash_find는 못찾으면 NULL을 반환하는 정석적인 순회 검색 형 함수이다.

---

3. page fault 발생 시

• Project 2의 Page Fault는 그냥 프로그램 개박살!!!! 이었다.
• 하지만 Project 3는 개박살나기 전에 가져와가 되었다. 우린 SPT에서 VM으로 올리는 행위를 이 과정을 통해 구현한다.

static void
page_fault (struct intr_frame *f) {
	bool not_present;  /* True: 존재하지 않는 페이지, false: 읽기 전용 페이지에 쓰기. */
	bool write;        /* True: 접근이 쓰기였음, false: 접근이 읽기였음. */
	bool user;         /* True: 사용자에 의한 접근, false: 커널에 의한 접근. */
	void *fault_addr;  /* 폴트 주소. */

	fault_addr = (void *) rcr2();
	intr_enable ();

	not_present = (f->error_code & PF_P) == 0;
	write = (f->error_code & PF_W) != 0;
	user = (f->error_code & PF_U) != 0;

#ifdef VM
	/* For project 3 and later. */
	if (vm_try_handle_fault (f, fault_addr, user, write, not_present))
		return;
#endif
.... (exit)

page_fault는 vm_try_handle_fault를 불린다. 이 것은 사실 사전에 이미 있다. exit의 위치에 주의하라. vm_try_handle_fault의 호출되는 상태를 보기로 하자.

 

/* Return true on success */
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;

	if (addr == NULL || is_kernel_vaddr(addr) | !not_present)
		return false;
	
	/* TODO: Validate the fault */
	// todo: 페이지 폴트가 스택 확장에 대한 유효한 경우인지를 확인해야 합니다.
	void *rsp = f->rsp; // user access인 경우 rsp는 유저 stack을 가리킨다.
	if (!user)			// kernel access인 경우 thread에서 rsp를 가져와야 한다.
		rsp = thread_current()->rsp;

	// 스택 확장으로 처리할 수 있는 폴트인 경우, vm_stack_growth를 호출
	page = spt_find_page(spt, addr);
	if (page == NULL)
    {
		// 페이지가 SPT에 없음
		return false;
     }
        
	//	write 불가능한 페이지에 write를 요청시
	return vm_do_claim_page(page);
}

Page Fault의 사유는 다양하기에, 이것이 실제로 해결 할 수 있는 영역의 Fault인지를 먼저 확인해야 한다.

그런 부분에 있어서 유효성 검사를 빡빡하게 한다음, 2번에서 만들었던 spt_find_page를 호출하게 된다.2번의 형태를 그럭저럭 잘 해놨다면 결과는 적절한 페이지를 찾아올 것이고, vm_do_claim_page를 통해 프레임에 배치하는 형태를 취하게 된다.

 

static bool vm_do_claim_page (struct page *page) {
	ASSERT (page != NULL);
	struct frame *frame = vm_get_frame ();
	if (frame == NULL) return false;

	frame->page = page;
	page->frame = frame;

	/* PML4 하드웨어에 등록 */
	uint64_t *pml4 = thread_current()->pml4;
	void *upage = page->va;
	void *kpage = frame->kva;
	bool rw = page->writable;

	bool is_page_set = pml4_set_page(pml4, upage, kpage, rw);

	if (!is_page_set) {
		page->frame = NULL;
		frame->page = NULL;
		vm_free_frame(frame);
		return false;
	}

	bool is_swapped_in = swap_in(page, frame->kva);
	return is_swapped_in;
}

vm_do_claim_page는 적절한 frame을 하나 찾아와서 frame과 page끼리 연결 시킨다 : 이것을 frame에 담는다는 표현으로 쓴다. vm_get_frame은 이후 victim 페이지를 찾는 개념을 논해야하지만 지금은 무조건 frame을 가져올 것이라는 전제로 작성을 이어나가보자.

그리고 각 페이지마다 부여되는 swap_in(...)을 이용하여 필요한 것들을 가져오는 행위를 수행한다. 여기까지 작동하려면 각 타입에 따른 swap_in도 작성되어야 할텐데, 여긴 당장 설명하기가 버거워서.. 행운을 액션 빔

---

4. setup_stack 만들기

static bool setup_stack (struct intr_frame *if_) {
    bool success = false;
    void *stack_bottom = (void *) (((uint8_t *) USER_STACK) - PGSIZE);

    success = vm_alloc_page(VM_ANON, stack_bottom, true);
    if (!success) return false;

    success = vm_claim_page(stack_bottom);
    if (!success) return false;
	
    if_->rsp = USER_STACK;
    return success;
}

4KB를 하나 만들어서 그냥 자 넌 이제부터 Stack이야~ 라고 하는 것에 불과하다. 여기서 작동되는 메서드 두개를 보자.

• vm_alloc_page는 사실 

#define vm_alloc_page(type, upage, writable) \
	vm_alloc_page_with_initializer ((type), (upage), (writable), NULL, NULL)

그냥 싼마이의 _with_initializer를 호출하는 것에 불과하다.

 

• vm_claim_page는

bool vm_claim_page (void *va) {
	struct page *page = NULL;
	struct supplemental_page_table *spt = &thread_current()->spt;
    
	page = spt_find_page(spt, va);
	if (page == NULL) return false;

	return vm_do_claim_page(page);
}

이제 보면 Fault로 인한 새 페이지 배정과 대단히 유사하다.

---

좋다. 주소 정렬 등 생각해야 할 것이 좀 많겠지만 이정도하면 Proj 2의 기본 시스템 콜 수행들은 통과 할 것이다.

61 of 141 tests failed.

read-boundary가 안된다면 주소 정렬에 대해 좀 더 정밀하게 생각해야한다. 뭔가 방법이 있었던 것 같은데..

이어 fork, exec, wait을 어서 복구해야한다. SPT_kill, SPT_copy를 비롯한 여러 내용을 구현해야한다. 생각보다 copy가 녹록치 않다.