[Pintos_project3 (1)] supplemental_page_table_init

1. 개요

project3의 첫 번째 관문으로 supplemental_page_table_init을 작성하는 것이었다.

// vm/vm.c

/* Initialize new supplemental page table */
void
supplemental_page_table_init (struct supplemental_page_table *spt UNUSED) {
	/* [pseudo]
	아마도,,, virtual page entry 개수 만큼의 리스트 할당. 이를 통해 spt 초기화
	*/
}

 

vm/vm.c에서 정의되어 있는 supplemental_page_table_init은 위와 같다.

spt는 가상 메모리 페이지의 상태를 저장하기 위한 목적으로 이용된다. 즉, Dirty bit, Acessed bit를 이용해서 수정되었는지, 그리고 접근 되었는 지를 추적한다.

 

따라서, supplemental_table_init은 virtual page entry 개수 만큼의 크기를 필요로 하는 자료 구조가 되지 않을까 라고 판단하였다.

 

따라서, 필요한 만큼의 데이터를 동적으로 할당할 수 있고 검색의 시간 복잡도가 O(1)인 해시를 이용해서 supplemental_page_table을 구성할 것이다.

 

2. 본문

void
supplemental_page_table_init (struct supplemental_page_table *spt UNUSED) {
	/* [pseudo]
	아마도,,, virtual page entry 개수 만큼의 리스트 할당. 이를 통해 spt 초기화
	*/
	hash_init(&spt->spt_hash, hash_func, less_func, NULL);
}

참고한 코드는 위와 같다.

 

여기서 사용되는 hash_init은 lib/kernel/hash.c에 선언되어 있다.

// lib/kernel/hash.c

/* Initializes hash table H to compute hash values using HASH and
   compare hash elements using LESS, given auxiliary data AUX. */
bool
hash_init (struct hash *h,
		hash_hash_func *hash, hash_less_func *less, void *aux) {
	h->elem_cnt = 0;
	h->bucket_cnt = 4;
	h->buckets = malloc (sizeof *h->buckets * h->bucket_cnt);
	h->hash = hash;
	h->less = less;
	h->aux = aux;

	if (h->buckets != NULL) {
		hash_clear (h, NULL);
		return true;
	} else
		return false;
}

해시 테이블을 초기화 하는 역할을 하는 hash_init에 대해서 알아보자. 첫 번째 인자인 struct hash *h는 초기화할 해시 테이블을 가리키는 포인터이다. 따라서, &spt -> spt_hash로 초기화할 hash를 지정해 주었다.

 

hash_init을 하고자 하는 대상은, supplemental page table의 멤버 중 하나인 spt_hash가 될 것이다.

spt에서 hash 자료구조를 사용할 것이라는 것을 나타내 주어야 하기 때문에, include/vm/vm.h 에서 supplemental_page_table을 찾아, spt_hash를 추가해 준다. [ &spt -> spt_hash ] 를 나타내주기 위함.

/include/vm/vm.h

/* Representation of current process's memory space.
 * We don't want to force you to obey any specific design for this struct.
 * All designs up to you for this. */
struct supplemental_page_table {
	struct hash spt_hash;
};

 

 

hash_func는 해시의 키에 따라 값을 계산하는 함수의 포인터이다. 나온 값을 어떤 기준으로 정렬할 것인지를 명시해주기 위해 less_func또한 정의해 주었다.

hash_init(&spt->spt_hash, hash_func, less_func, NULL);

 

hash.h에 선언해 주는 것도 잊지 않았다.

// include/lib/kernel/hash.h

/* project 3 */
uint64_t hash_func(const struct hash_elem *e, void *aux);
bool less_func(const struct hash_elem *a, const struct hash_elem *b, void *aux);

 

hash_func와 less_func에 대해서 알아보기에 앞서, hash_elem과 hash_entry에 대해서 알아보자.

hash_entry를 알아보려고 하는 이유는, hash_func에서 hash_entry를 사용하기 때문이다.

// include/lib/kernel/hash.h

/* Hash element. */
struct hash_elem {
	struct list_elem list_elem;
};


#define hash_entry(HASH_ELEM, STRUCT, MEMBER)                   \
	((STRUCT *) ((uint8_t *) &(HASH_ELEM)->list_elem        \
		- offsetof (STRUCT, MEMBER.list_elem)))
        
// 아래와 같이 hash_entry가 사용됨. 'e'의 자료구조는 hash_elem *
hash_entry(e, struct page, hash_elem);

 

HASH_ELEM : 해시 테이블에 저장된 데이터 요소인 hash_elem을 가리키기 위해 사용된다.

STRUCT : hash_elem을 포함하는 외부 구조체 타입인 page을 명시하기 위해 사용된다.

MEMBER: 외부 구조체인 STRUCT (page) 안에서 hash_elem이 정의된 멤버 변수의 이름을 나타낸다.

 

hash_entry의 목적은 hash_elem을 가리키고 있는 페이지의 시작주소를 얻기 위함이다.

따라서, 페이지의 hash_elem의 주소값 - (페이지에서 hash_elem까지의 주소값) 을 통해서, 페이지 시작 값을 계산해 준다.

 

아래는 struct page -> struct hash_elem -> struct list_elem 까지의 흐름을 나타내는 그림이다.

hash_entry 매크로는 hash_elem을 참조하는 외부 구조체인 page를 가리키는 포인터를 찾기 위한 용도이다.

처음에 코드가 잘 이해가 가지 않아서 갚게 파보았다. 

 

또한 아래는 hash table의 구조를 그려보았다. 그림으로 그려보니 훨씬 이해가 잘 된다.

 

우선 hash_func에 대해서 먼저 알아보자.

// lib/kernel/hash.c

/*returns hash index*/
uint64_t hash_func(const struct hash_elem *e, void *aux) {
	const struct page *p = hash_entry(e, struct page, hash_elem);
	return hash_bytes(&p->va, sizeof(p->va));
}

hash_entry를 이용해서, hash_elem을 참조하는 외부구조체인 page의 시작 주소를 얻는다. p가 페이지를 가리키는 포인터가 될 것이다.

페이지가 가지고 있는 va (virtual address)를 얻어서, 이를 통해 64비트 해시 값을 얻는다.

 

다음으로 less_func에 대해서 알아보자.

/*asc. sort*/
bool less_func(const struct hash_elem *a, const struct hash_elem *b, void *aux) {
	const struct page *pa = hash_entry(a, struct page, hash_elem);
	const struct page *pb = hash_entry(b, struct page, hash_elem);

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

less_func는 페이지 pa, pb에 대해서, virtual address의 값을 비교해서 반환한다. 이를 통해 해시 테이블을 정렬할 수 있도록 한다.

 

/* Initialize new supplemental page table */
void
supplemental_page_table_init (struct supplemental_page_table *spt UNUSED) {
	/* [pseudo]
	아마도,,, virtual page entry 개수 만큼의 리스트 할당. 이를 통해 spt 초기화
	*/
	hash_init(&spt->spt_hash, hash_func, less_func, NULL);
}

이렇게 supplemental_page_table을 init하기 위한 함수를 알아보았다.

3. 결과

supplemental_page_table 초기화 밖에 안했기 때문에, 123 of 141 tests failed 임을 확인할 수 있다.