[Pintos_project3 (3)] spt_insert_page

1. 개요

이번 함수 구현에 대한 이해는 이전보다 수월했다.

// vm/vm.c

/* Insert PAGE into spt with validation. */
bool
spt_insert_page (struct supplemental_page_table *spt UNUSED,
		struct page *page UNUSED) {
	/* [Pseudo]
	spt에 va가 있는 지 확인.
	(true) -> 페이지 insert가 일어나선 안되겠지
	(false) -> spt에 va에 해당하는 페이지 할당

	사전 : spt_find_page()를 통해 va로 할당된 페이지 유무를 확인.
	(있다면) ..?
	(없다면) page->hash_elem을 통해 해시값을 찾고, 
	       해시값의 위치에 해당되는 supplemental page table 위치에 insertion을 한다.
	(결론) 성공 결과를 반환한다.
	 */

}

 

위와  같은 흐름으로 진행될 것이라고 생각했다.

예상보다 더 쉽게, hash_insert라는 함수가 있어서, spt_hash와 hash_elem만 전달해 주면 되었다.

 

2. 본문 

// vm/vm.c

/* Insert PAGE into spt with validation. */
bool
spt_insert_page (struct supplemental_page_table *spt UNUSED,
		struct page *page UNUSED) {
	return hash_insert(&spt->spt_hash, &page->hash_elem) ? false : true;
}

 

hash_insert함수에 테이블과, 페이지의 hash_elem을 인자로 넣어주었다.

이제 hash_insert 함수에 대해서 알아보자.

 

/* Inserts NEW into hash table H and returns a null pointer, if
   no equal element is already in the table.
   If an equal element is already in the table, returns it
   without inserting NEW. */
struct hash_elem *
hash_insert (struct hash *h, struct hash_elem *new) {
	struct list *bucket = find_bucket (h, new);
	struct hash_elem *old = find_elem (h, bucket, new);

	if (old == NULL) // old 라는 건, 이미 기존에 hash_elem이 있다면...
		insert_elem (h, bucket, new);

	rehash (h); // 해시 테이블의 요소를 분산시키기 위해 버킷 개수를 재조정. 요소가 너무 많아져 충돌이 증가하면 버킷 개수를 늘려 충돌을 줄이는 등...

	return old;
}

hash_insert 함수는 페이지를 table에 넣기 전에, 해시값에 해당되는 페이지가 이미 삽입되어 있는지 확인한다.

 

따라서, find_bucket으로 해시값이 포함되어 있는 bucket을 찾고, bucket에서 hash_elem이 존재하는 지 찾는다.

만약 NULL이라면, 존재하지 않는 것이기 때문에, 바로 insert_elem을 하면 되지만,

 

기존에 존재하는 것이 있다면 remove_elem을 통해 해당 hash_elem을 지우고 insert_elem을 해준다.

 

'buckets'와 'bucket'은 다른 것을 가리킨다. 이 때문에, 개념이 조금 헷갈렸었기 때문에, 그림을 다시 그려서 표현해 보았다.

 

3. 결과

123 of 141 tests failed로 아직까지 테스트 결과는 동일하다.