정글 [week11~12] WIL + PintOS VM

1. 이번 주 목표

이번 주의 목표는 PintOS Project 3의 Virtual Memory가 어떤 자료구조와 실행 흐름으로 동작하는지 코드 기준으로 이해하는 것이었다. 처음에는 “해싱한다”는 말부터 헷갈렸고, 이후 SPT가 왜 hash table을 쓰는지, page->va가 왜 key가 되는지, page fault가 발생했을 때 커널이 어떤 순서로 page를 실제 메모리에 올리는지를 따라갔다.

특히 아래 흐름을 하나의 연결된 구조로 이해하려고 했다.

```plain text load_segment() -> SPT에 lazy page metadata 등록 -> 실제 접근 시 page fault 발생 -> SPT에서 struct page 조회 -> frame 확보 -> PML4 매핑 -> swap_in() -> uninit page라면 anon/file page로 전환하고 실제 내용 채움

이번 주에 중심으로 본 개념은 다음과 같다.

| 개념 | 이번 주에 정리한 의미 |
| --- | --- |
| SPT | 프로세스별 user virtual page metadata 저장소 |
| Hash key | SPT에서는 `page->va` |
| Hash value | key를 hash 함수에 넣어 만든 중간값 |
| Bucket index | hash value를 bucket 개수에 맞춰 줄인 배열 index |
| `struct page` | 가상 page 하나의 metadata |
| `struct frame` | 물리 frame 하나의 metadata |
| PML4 | CPU가 실제 주소 변환에 사용하는 page table |
| Frame table | 현재 물리 메모리에 올라온 frame 목록 |
| `palloc_get_page()` | 실제 4KB user frame 공간 확보 |

## 2. 시도한 접근 방식

처음에는 PintOS의 hash table 동작을 먼저 확인했다. `hash_init`, `hash_insert`, `hash_find`, `hash_destroy` 흐름을 따라가며 bucket 배열과 linked list 기반 collision 처리 방식을 이해하려고 했다. 이때 `struct hash *h;`처럼 포인터만 선언하면 실제 hash 객체가 생기지 않는다는 점, 지역 변수로 만든 hash table은 함수가 끝나면 사라진다는 점도 함께 확인했다.

그 다음에는 SPT 기본 함수로 넘어갔다. `supplemental_page_table_init`, `spt_find_page`, `spt_insert_page`, `spt_remove_page`를 보면서 `struct page` 안의 `hash_elem`이 hash bucket list에 연결되고, `hash_entry()`를 통해 다시 `struct page`로 복원되는 구조를 정리했다.

이후에는 page fault 처리 흐름을 따라갔다. `vm_try_handle_fault()`에서 fault 주소가 처리 가능한지 판단하고, `spt_find_page()`로 page를 찾은 뒤, `vm_claim_page()`와 `vm_do_claim_page()`를 통해 frame 확보, PML4 매핑, `swap_in()`이 이어지는 구조를 이해하려고 했다.

AI는 주로 내가 이해한 구조가 맞는지 검증하는 용도로 사용했다. 특히 `hash_insert()` 반환값, `page_hash()` 구현 방향, `pg_round_down()`이 필요한 이유, `uninit_initialize()`가 언제 실행되는지 같은 부분을 질문하며 흐름을 정리했다.

## 3. 문제와 해결 과정

### 3-1. Hash에서 key, hash value, bucket index가 헷갈렸다

처음에는 hash된 값 자체가 key인지 헷갈렸다. 정리해보니 SPT에서 key는 `page->va`이고, hash value는 이 key를 hash 함수에 넣어 나온 중간값이며, bucket index는 hash value를 bucket 개수에 맞게 줄인 값이었다.

```plain text
page->va
-> page_hash()
-> hash value
-> bucket index
-> bucket list 탐색
-> 같은 key 여부 비교
-> 중복 없으면 삽입

같은 bucket에 들어가는 것은 단순 hash collision이므로 정상이다. 하지만 같은 key, 즉 같은 va를 가진 page는 SPT에서 중복 page이므로 삽입되면 안 된다. 그래서 hash_insert()가 NULL을 반환하면 삽입 성공이고, NULL이 아니면 기존 같은 key가 있다는 뜻으로 이해했다.

3-2. PintOS hash/list가 intrusive 구조라는 점이 어려웠다

처음에는 struct hash 안에 page가 직접 들어 있어야 한다고 생각했다. 실제로는 struct page 안에 hash_elem이 있고, hash table은 이 hash_elem만 bucket list에 연결한다.

```plain text thread -> supplemental_page_table -> hash_table -> bucket list -> page.hash_elem -> hash_entry() -> struct page

이 구조 때문에 `hash_elem`은 포인터가 아니라 `struct page` 내부에 값으로 들어간다. PintOS의 hash/list는 intrusive 구조라서, 연결 노드가 객체 내부에 직접 포함되어 있어야 한다. bucket list의 `head.next`는 실제로 어떤 `page.hash_elem`을 가리키고, `hash_entry()`는 그 내부 멤버 주소에서 바깥의 `struct page` 주소를 복원한다.

### 3-3. SPT, PML4, frame table의 역할이 섞였다

처음에는 SPT가 frame 정보까지 모두 관리하는 것처럼 느껴졌다. 하지만 역할을 나누면 더 명확했다.

| 구조 | 역할 |
| --- | --- |
| SPT | VA로 `struct page`를 찾는 metadata table |
| PML4 | CPU가 VA를 실제 frame으로 변환할 때 사용하는 page table |
| Frame table | 현재 물리 메모리에 올라온 frame 목록과 eviction 대상 관리 |
| Swap table | eviction된 page가 저장된 swap slot 추적 |

SPT에 page가 있다는 것은 “이 VA는 합법적으로 복원 가능한 page다”라는 뜻이다. 하지만 CPU는 SPT를 보지 않고 PML4를 본다. 그래서 실제 접근 가능하게 만들려면 `pml4_set_page()`로 VA와 frame을 매핑해야 한다.

### 3-4. Lazy loading 흐름이 처음에는 흩어져 보였다

`vm_alloc_page_with_initializer()`, `uninit_new()`, `anon_initializer()`, `file_backed_initializer()`, `uninit_initialize()`의 관계가 처음에는 복잡했다. 정리해보니 핵심은 등록 시점과 실행 시점을 분리하는 것이었다.

```plain text
load_segment()
-> page 단위로 upage, ofs, page_read_bytes, page_zero_bytes 계산
-> vm_alloc_page_with_initializer()
-> uninit_new()가 init, aux, initializer 저장
-> 아직 파일은 읽지 않음

첫 접근
-> page fault
-> vm_claim_page()
-> vm_do_claim_page()
-> vm_get_frame()
-> pml4_set_page()
-> swap_in()
-> uninit_initialize()
-> lazy_load_segment()
-> 파일 내용을 kva에 읽고 나머지를 0으로 채움

즉, load 시점에는 SPT에 lazy page 정보를 등록만 하고, 실제 파일 read는 page fault 이후에 실행된다.

3-5. upage와 file offset의 차이를 정리했다

ELF loading에서 upage와 file offset이 자주 헷갈렸다. upage는 프로세스 가상 메모리 쪽 좌표이고, file offset은 ELF 실행 파일 내부 좌표이다.

값	의미
`upage`	해당 page가 배치될 user virtual address
file offset	실행 파일 내부에서 읽기 시작할 위치
`read_bytes`	파일에서 실제로 읽어야 하는 바이트 수
`zero_bytes`	메모리에서 0으로 채워야 하는 바이트 수
`aux`	나중에 `lazy_load_segment()`가 사용할 정보 묶음

매핑이 되어 있다고 해서 메모리 내용이 올바르게 채워지는 것은 아니다. 파일에서 읽을 부분은 읽고, BSS나 padding처럼 파일에 없는 부분은 0으로 채워야 프로그램이 기대하는 초기 상태가 만들어진다.

4. 새롭게 배운 점

이번 주에 가장 크게 배운 점은 PintOS VM이 하나의 함수나 하나의 table로 끝나는 구조가 아니라는 점이다. SPT는 page metadata를 기억하고, PML4는 CPU 주소 변환을 담당하며, frame table은 실제 물리 frame을 관리한다. 각 구조가 맡은 책임이 다르기 때문에, 어디에서 어떤 정보를 찾아야 하는지 구분하는 것이 중요했다.

또 struct page와 struct frame의 관계도 더 명확해졌다. page->frame은 가상 page가 현재 올라간 물리 frame을 가리키고, frame->page는 해당 frame이 어떤 page를 담고 있는지 추적한다. 이 연결은 eviction이나 swap을 구현할 때 필요하다.

setup_stack()이 lazy loading과 다르게 즉시 claim되어야 하는 이유도 이해했다. 실행 파일의 code/data page는 실제 접근 전까지 미뤄도 되지만, stack은 load 과정에서 argv 문자열과 포인터를 바로 써야 하므로 즉시 frame과 PML4 매핑이 필요하다.

아직 eviction victim 선택, swap slot 관리, mmap dirty write-back은 개념적으로 이해한 수준이다. 특히 frame table을 이용해 어떤 frame을 쫓아낼지 고르는 정책과, mmap page가 수정되었을 때 원본 파일에 다시 반영하는 흐름은 다음에 더 구체적으로 봐야 한다.

5. 다음에 더 볼 것

이번 정리로 SPT, hash, page fault, lazy loading의 큰 흐름은 어느 정도 연결되었다. 다음에는 아래 항목을 더 구체적으로 확인해야 한다.

eviction victim 선택 정책
swap slot 관리 방식
mmap page의 dirty write-back 흐름

이번 주는 “virtual memory에서 load 시점과 실제 메모리 적재 시점을 분리한다”는 핵심 구조를 이해하는 주간이었다.