2025.06.02

TIL(TODAY I LEARN)

---

• 오늘한 내용 : PintOS - Project3: Virtual Memory - SPT 구현!

• WEEK 12 : 정글 끝까지(PintOS) - Virtual Memory

---

1) supplemental_page_table 구현

1. SPT 구현 (vm/vm.c, include/vm/vm.h):

SPT 함수부터 완성 → 페이지 폴트 시 “어떤 페이지”인지 찾아 올 수 있어야 함.

• spt → hash 방식으로 사용

struct supplemental_page_table
{
	struct hash spt_hash; // hash 형식으로 spt 관리
};

• 해시 테이블?
  • hash.h에 구현이 되어있으므로 가져다가 쓰자

    /* Hash table. */
    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'. */
    };
    
    /* A hash table iterator. */
    struct hash_iterator {
    	struct hash *hash;          /* The hash table. */
    	struct list *bucket;        /* Current bucket. */
    	struct hash_elem *elem;     /* Current hash element in current bucket. */
    };
    

• page 구조체에 hash_elem 추가

struct page
{
	...
	/* Your implementation */
	struct hash_elem hash_elem; // spt_hash를 위해 추가
	...
}

• spt 초기화

/* Initialize new supplemental page table */
void supplemental_page_table_init(struct supplemental_page_table *spt UNUSED)
{
	// 해시 테이블 초기화
	hash_init(&spt->spt_hash, page_hash, page_less, NULL);
}

• hash_init()을 위한 함수 구현

/* 해시 함수: page->va 주소 자체를 바이트 배열로 보고 해싱
	pintos에서 제공해주는 해시 함수 hash_bytes() 사용
*/
static unsigned page_hash(const struct hash_elem *e, void *aux UNUSED)
{
	struct page *p = hash_entry(e, struct page, hash_elem);

	return hash_bytes(&p->va, sizeof p->va);
}

/* 비교 함수: 두 page의 va 값을 포인터 크기 기준으로 비교 후 bool 값 리턴 */
static bool page_less(const struct hash_elem *a, const struct hash_elem *b, void *aux UNUSED)
{
	struct page *pa = hash_entry(a, struct page, hash_elem);
	struct page *pb = hash_entry(b, struct page, hash_elem);

	return pa->va < pb->va;
}

• spt 찾기, 삽입, 삭제 구현

/* Find VA from spt and return page. On error, return NULL. */
struct page *
spt_find_page(struct supplemental_page_table *spt, void *va)
{
	struct page *page = NULL;
	/* TODO: Fill this function. */
	struct hash_elem *he;
	struct page tmp; // 검색용 임시 페이지 변수
	/* va를 페이지 경계(시작위치)로 내림(round down) */
	tmp.va = pg_round_down(va);

	he = hash_find(&spt->spt_hash, &tmp.hash_elem);
	if (he == NULL)
		return NULL;

	page = hash_entry(he, struct page, hash_elem);
	return page;
}

/* Insert PAGE into spt with validation. */
bool spt_insert_page(struct supplemental_page_table *spt, struct page *page)
{
	int succ = false;
	/* TODO: Fill this function. */
	// hash_insert()는 성공 시 null을 반환, 이미 같은 키가 있으면 기존의 hash_elem 반환
	struct hash_elem *he = hash_insert(&spt->spt_hash, &page->hash_elem);
	if (he == NULL)
		succ = true;
	return succ;
}

bool spt_remove_page(struct supplemental_page_table *spt, struct page *page)
{
	/* hash_delete 추가 */
	struct hash_elem *he = hash_delete(&spt->spt_hash, &page->hash_elem);
	if (he == NULL)
		return false;

	vm_dealloc_page(page);

	return true;
}

• spt 전체 해제 구현
• hash_clear(...)
  • 기능: 해시 테이블 안의 모든 요소를 비우고, elem_cnt를 0으로 만들며, 각 버킷 리스트를 빈 상태로 초기화.
  • 버킷 배열 유지: 버킷 배열(h->buckets)은 그대로 남으므로 “빈 해시 테이블”으로 재사용 가능.
• hash_destroy(...)
  • 기능: (선택적) destructor로 각 요소를 정리한 뒤,
  • 버킷 배열 해제: free(h->buckets)를 호출하여 버킷 배열 메모리 자체를 해제.
  • 결과: 이 함수 이후에는 h를 다시 쓰려면 hash_init(&h, ...) 같은 재초기화가 필요하다.
• hash_destroy를 사용 & process_exec() 수정

/* Free the resource hold by the supplemental page table */
void supplemental_page_table_kill(struct supplemental_page_table *spt)
{
	/* TODO: Destroy all the supplemental_page_table hold by thread and
	 * TODO: writeback all the modified contents to the storage. */

	struct hash_iterator i;
	struct page *p;

	/* 전체 해쉬 테이블 순회하면서 vm_dealloc_page 수행*/
	hash_first(&i, &spt->spt_hash);
	while (hash_next(&i))
	{
		p = hash_entry(hash_cur(&i), struct page, hash_elem);

		vm_dealloc_page(p);
	}

	// 버킷 배열 메모리 자체를 해제
	hash_destroy(&spt->spt_hash, NULL);
}

------------------------------
process.c
int process_exec(void *f_name)
{
	...
	/* We first kill the current context */
	process_cleanup();

	#ifdef VM
	/* project 3) 새 프로그램 로드를 위해 빈 SPT로 다시 초기화 추가*/
	supplemental_page_table_init(&thread_current()->spt);
	#endif

	...
}

---