PintOS에 구현 되어 있는 Hash Table를 이해하고 hash_find() 탐구

발표 동기

• hash 사용에 있어 hash에 대한 정확한 이해를 필요
• 그 방법으로 hash_find()를 통하여 이해를 해보기로 하였다.

hash 사용 이유

• 페이지 폴트가 발생이 될때마다 참조해야 하는 struct supplemental_page_table
• 탐색 시간이 길어지게 되면 load가 길어 짐
• 스왑과정에서의 시간 복잡도도 증가

<aside> 💡 참조 되는 횟수가 많으면서도 찾아야 하는 데이터의 범위가 넓은 struct supplemental_page_table 를 해쉬 테이블로 관리하기로 결정

</aside>

hash_find()를 파헤쳐 보자

• kernel/hash.c → hash_find()

<aside> 💡 해쉬 테이블(h)에서 인자로 받은 해쉬 요소(e)와 va가 같은 요소(page)를 찾아서 찾은 요소(page)를 반환

</aside>

• 인자로 받은 hash 구조체와 hash_elem 구조체를 find_bucket()를 통해 버킷 인덱스를 받는다.

struct hash_elem *
hash_find (struct hash *h, struct hash_elem *e) {
	return find_elem (h, find_bucket (h, e), e);
}

• 버킷 인덱스 받는 과정

• kernel/hash.c → find_elem()

• 본격적으로 찾고자 하는 요소(page)를 찾자

• 해당 함수의 포인트는 bucket 리스트를 순회 하면서 얻는 hash_elem *hi와 인자로 받은 hash_elem *e가 같은 것을 찾는 것!

static struct hash_elem *
find_elem (struct hash *h, struct list *bucket, struct hash_elem *e) {
	struct list_elem *i;

	for (i = list_begin (bucket); i != list_end (bucket); i = list_next (i)) {
		struct hash_elem *hi = list_elem_to_hash_elem (i);
		if (!h->less (hi, e, h->aux) && !h->less (e, hi, h->aux))
			return hi;
	}
	return NULL;
}