흐름도

[준비]
supplemental_page_table_init()
 │
 └─ hash_init() 에게 규칙 전달
      ├─ 규칙1: page_hash (va로 해시값 계산)
      └─ 규칙2: page_less (va로 페이지 비교)

----------------------------------------------------

[실행]
spt_find_page(spt, 0x12345000)
 │
 ├─ 1. 임시 page 생성 { .va = 0x12345000 }
 │
 ├─ 2. hash_find(spt, 임시 page) 호출
 │      │
 │      ├─ 3. (내부) page_hash(임시 page) 호출 -> 해시값 'K' 계산
 │      │
 │      ├─ 4. (내부) 해시 테이블의 'K'번째 버킷으로 이동
 │      │
 │      └─ 5. (내부) page_less()로 버킷 내 페이지들과 va 비교
 │
 └─ 6. va가 일치하는 실제 page 발견 후 반환

<aside>

준비 단계 (초기화)

</aside>

프로세스가 처음 시작될 때, 해당 프로세스의 보조 페이지 테이블(SPT)을 사용할 수 있도록 초기 설정을 진행

1. supplemental_page_table_init() 함수가 호출
2. 이 함수는 내부적으로 hash_init()를 호출하여 SPT가 사용할 해시 테이블을 생성 & 초기화
3. 이때 가장 중요한 것은, 해시 테이블이 앞으로 struct page 데이터를 잘 다룰 수 있도록 두 가지 핵심 규칙(함수 포인터)을 알려주는 것
   • 규칙 1 : page_hash (주소 계산 규칙)
     • 역할: "이 페이지는 해시 테이블의 어디에 저장해야 하는가?" 라는 질문에 답함
     • 동작 : 페이지의 고유 식별자인 가상 주소(va)를 사용해 숫자 값(해시 값)을 만들어, 저장될 위치(버킷)를 결정
   • 규칙 2 : page_less (비교 규칙)
     • 역할 : "두 페이지가 같은 페이지인가?" 라는 질문에 답함
     • 동작 : 두 페이지의 가상 주소(va)가 같은지를 비교하여 동일한 페이지인지 판단
       • 이는 해시 충돌이 발생했을 때나 데이터를 검색할 때 필수적

<aside>

실행 단계 (페이지 찾기)

</aside>

이제 특정 가상 주소에 접근할 때, 해당 주소에 대한 정보가 SPT에 있는지 확인 (예 : 페이지 폴트가 발생했을 때)

1. spt_find_page(spt, target_va) 함수가 호출됩니다. target_va는 우리가 찾으려는 가상 주소
2. 함수 내에서 검색용 '키'로 사용할 임시 page 구조체를 하나 만듦
3. 이 임시 page의 va 멤버에 target_va 값을 설정
4. hash_find(spt, &임시_page->hash_elem)를 호출하여 해시 테이블 검색을 시작
5. hash_find는 준비 단계에서 등록한 규칙들을 사용
   • 먼저 page_hash 규칙을 임시 페이지에 적용하여 target_va에 해당하는 해시 값을 계산하고, 해당 버킷으로 즉시 이동
   • 그 다음, 버킷 안에 있는 실제 page들과 임시 page를 page_less 규칙으로 하나씩 비교하며 va가 정확히 일치하는 항목을 찾음
6. va가 일치하는 실제 page를 찾으면, hash_entry 매크로를 통해 hash_elem으로부터 struct page 전체의 주소를 얻어내어 반환
   • 만약 찾지 못하면 NULL을 반환