[PintOS] Project 3 : VM - Memory Management - SPT(Supplemental Page Table) 함수 분석 및 구현 흐름 정리

PintOS의 가상 메모리 프로젝트에서는 사용자 가상 주소와 페이지 정보를 매핑하는 Supplemental Page Table(SPT)를 직접 구현해야 합니다. SPT는 각 프로세스마다 별도로 존재하며, lazy loading, swap, mmap 등 다양한 기능의 기반이 됩니다.

이번 글에서는 SPT를 구성하는 주요 함수 3가지를 정리하고, 각 함수가 어떻게 동작하는지 코드 분석과 함께 흐름도를 이용해 설명하겠습니다.

---

1. supplemental_page_table_init()

1.1 목적

새로운 프로세스가 시작되거나 fork() 시점에 SPT를 초기화하는 함수입니다.
내부적으로는 hash_init()을 이용하여 SPT용 해시 테이블을 초기화합니다.

---

1.2 구현 코드

void supplemental_page_table_init(struct supplemental_page_table *spt UNUSED)
{
   if (!hash_init(&spt->SPT_hash_list, my_hash, my_less, NULL))
      return;
}

1.2.1 인자 설명

• struct supplemental_page_table *spt : 현재 프로세스가 사용하는 SPT입니다. 여기서 SPT는 사용자 프로세스의 가상 주소 공간을 관리하기 위한 해시 테이블입니다. 즉, 커널의 페이지 테이블과는 별도로 사용자 영역에서만 쓰입니다. 
• &spt->SPT_hash_list : 실제 페이지 정보를 저장할 해시 테이블입니다. 이 필드는 struct hash 타입으로, 내부적으로 여러 개의 버킷(bucket)을 가지고 있으며 각 bucket은 연결 리스트로 구성됩니다.
• my_hash : SPT 해시 테이블에서 사용할 해시 함수 포인터입니다. 보통 va(가상 주소)를 기반으로 해시값을 계산합니다. 
• my_less : SPT에서 해시 충돌이 일어났을 때 원소를 비교하는 비교 함수 포인터입니다. 보통 va 기준으로 정렬
• NULL : 보조 인자로, 특별한 부가 정보(auxiliary data)가 없을 때는 NULL로 설정합니다. 

---

1.3 내부 함수 hash_init()

/* 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;
}

정글러라면 CSAPP을 읽고 퀴즈 또한 봤었겠지요? 여기서 쓰이는 hash는 체이닝을 사용합니다. 

퀴즈 정리본

1.3.1 인자 설명

• h->bucket_cnt = 4 : 해시 테이블의 초기 버킷 수는 4개입니다. 나중에 필요에 따라 resize 가능합니다.
• h->buckets : 각 버킷에 대한 메모리를 동적 할당합니다.
• hash, less, aux : 위에서 전달받은 해시 함수, 비교 함수, 부가 정보 포인터를 저장합니다.
• hash_clear() : 각 버킷을 빈 상태로 초기화합니다.

만약 메모리 할당에 실패하면 false를 반환하고, 호출자는 후속 처리를 담당해야 합니다.

---

2. spt_fine_page()

2.1 목적

주어진 가상 주소(va)에 해당하는 struct page *를 SPT에서 탐색합니다. 실패 시 NULL을 반환합니다.

2.2 구현 코드

/* Find VA from spt and return page. On error, return NULL. */
/* 가상 주소를 통해 SPT에서 페이지를 찾아 리턴합니다.
 * 에러가 발생하면 NULL을 리턴하세요 */
struct page *
spt_find_page(struct supplemental_page_table *spt UNUSED, void *va UNUSED)
{
   // 더미 SPT_entry를 생성하여 va 값 기반 hash 조회
   struct page *finding_page = NULL;
   struct SPT_entry lookup;
   lookup.va = pg_round_down(va);

   // 인자는 더미 SPT_entry, 반환된 finding_hash_elem은 실제 SPT_entry 소속 hash_elem
   struct hash_elem *finding_hash_elem = hash_find(&spt->SPT_hash_list, &lookup.elem);

   // 탐색 성공 시, hash_elem로 entry 조회, page 확보
   if (finding_hash_elem != NULL)
      finding_page = hash_entry(finding_hash_elem, struct SPT_entry, elem)->page;

   return finding_page;
}

2.3 플로우 차트

[시작]
   ↓
va 페이지 단위로 정렬 → pg_round_down()
   ↓
dummy SPT_entry 생성 (va만 설정)
   ↓
hash_find로 SPT 해시 테이블 탐색
   ↓
성공?
 ┌──────┐
 │아니오 | ───→ [NULL 반환]
 └──────┘
   ↓
성공한 hash_elem → SPT_entry → page 추출
   ↓
[page 반환]

2.3.1 포인트

• pg_round_down()으로 페이지 기준 정렬 필수
• 실제 hash_find()는 lookup.elem의 va 값을 기준으로 비교

---

3. spt_insert_page()

3.1 목적

가상 주소 va와 page 구조체 page를 연결하여 SPT에 삽입하는 함수입니다. 중복 삽입은 허용되지 않으며, 실패 시 false를 반환합니다.

3.2 구현 코드 

/* Insert PAGE into spt with validation. */
bool spt_insert_page(struct supplemental_page_table *spt UNUSED,
                     struct page *page UNUSED)
{
   // int succ = false;
   /* TODO: Fill this function. */

   // 예외 처리
   if (spt == NULL || page == NULL)
   {
      return false;
   }

   // 메모리 할당
   struct SPT_entry *entry = malloc(sizeof(struct SPT_entry));
   // 예외 처리
   if (entry == NULL)
   {
      return false;
   }

   entry->va = page->va; // 가상 주소 : page 구조체의 va 필드 -> SPT_entry의 va 필드
   entry->page = page;   // 페이지 참조 : page 구조체의 주소 -> SPT_entry의 page 포인터

   if (hash_insert(&spt->SPT_hash_list, &entry->elem) != NULL)
   {
      // 삽입 실패시 메모리 정리
      free(entry);
      return false; // 삽입 실패
   }

   return true; // SPT 페이지 삽입 성공
}

3.3 플로우 차트

[시작]
   ↓
예외처리 (spt == NULL || page == NULL)
   ↓
SPT_entry 동적 메모리 할당
   ↓
할당 성공?
 ┌──────┐
 │아니오|  ───→ [false 반환]
 └──────┘
   ↓
entry에 va, page 설정
   ↓
hash_insert 수행
   ↓
충돌 발생?
 ┌─────┐
 │  예   ──→ 메모리 해제 → [false 반환]
 └─────┘
   ↓
[true 반환 (삽입 성공)]

3.3.1 포인트

• hash_insert()는 기존에 동일한 키가 있으면 실패함.
• 삽입 실패 시 반드시 free()로 메모리 해제 필요.

---

마무리

함수	주요 역할	실패 시 처리
supplemental_page_table_init()	SPT 해시 테이블 초기화	아무 작업 안 함
spt_find_page()	va → page 매핑 탐색	NULL 반환
spt_insert_page()	page 삽입	중복 시 false, free()

이러한 함수들이 잘 구현되어 있어야, 가상 메모리 시스템에서 lazy loading, page fault 대응, mmap, swap 등 고급 기능이 제대로 작동합니다. 다음 글에서는 vm_alloc_page_with_initializer, vm_try_handle_fault 같은 핵심 함수들을 이어서 정리해 보겠습니다.