가상메모리 페이지 - page
물리 메모리 페이지 -frame

supplemental page table -> physical memory page frame

page structure and operation

struct page

struct page {
	const struct page_operations *operations;
	void *va;              /* Address in terms of user space */
	struct frame *frame;   /* Back reference for frame */

	union {
		struct uninit_page uninit;
		struct anon_page anon;
		struct file_page file;
#ifdef EFILESYS
		struct page_cache page_cache;
#endif
	};
};

• union: 여러 개의 타입 중 하나만 사용하는 자료구조
• 모든 멤버는 같은 메모리 공간을 공유하며 동시에 여러 멤버를 사용할 수 없다
• 이 페이지가 어떤 유형인지에 따라 하나의 멤버만 활성화됨
  • 예: 익명 페이지면 anon 멤버만 사용

struct page_operations

struct page_operations {
	bool (*swap_in)(struct page *, void *);
	bool (*swap_out)(struct page *);
	void (*destroy)(struct page *);
	enum vm_type type;
};

• 이 구조체는 3개의 함수 포인터를 포함한 하나의 함수 테이블로 이해하면 됨

• 한 페이지는 다음 중 하나의 타입을 가짐:

  • VM_UNINIT (초기화되지 않은 페이지)
  • VM_ANON (익명 페이지, 스왑용)
  • VM_FILE (파일 기반 페이지)

• 각 페이지 유형에 따라 다른 함수 포인터 테이블을 가짐 (예: anon_ops, file_ops)

• 예: destroy(page) 호출 시 → page->operations->destroy(page) 실행됨

page->operations = &anon_ops; // 익명 페이지면
destroy(page); // 라고만 써도
→ page->operations->destroy(page);
→ anon_destroy(page); // 타입에 맞는 함수가 호출됨

---

file-backed 페이지에서 destroy() 함수가 호출되는 과정

1. 어떤 페이지 page가 VM_FILE 타입이라고 가정
2. vm_dealloc_page(page) 함수가 호출됨
3. 함수 내부에서 destroy(page) 호출

destroy 매크로 정의:

#define destroy(page) \
  if ((page)->operations->destroy) (page)->operations->destroy(page)

→ 실제로는 page->operations->destroy(page) 호출과 같음

page가 VM_FILE이므로
→ page->operations는 file_ops를 가리킴
→ file_ops.destroy는 file_backed_destroy를 가리킴
→ 결과적으로 file_backed_destroy(page) 함수가 호출됨

---

파일 기반 페이지(VM_FILE)는 destroy(page) 호출 시 자동으로 file_backed_destroy()가 실행되도록
함수 포인터 테이블(file_ops)을 통해 연결되어 있다.

implement supplemental page table

기본 페이지 테이블(PML4)은 하드웨어가 사용하는 테이블로, 가상 주소와 물리 주소의 매핑을 관리하지만
페이지 폴트 처리나 페이지 타입 정보 관리 등은 못 하므로 커널이 직접 관리하는 보조 페이지 테이블(SPT)이 필요하다.

보조 페이지 테이블은 각 가상 주소(va)에 대응되는 struct page 정보를 저장하고,
이 페이지가 어떤 타입인지(anon, file, uninit), 어떤 파일에 연결되어 있는지, 스왑 영역에 있는지 등을 추적한다.

---

보조 페이지 테이블의 주요 함수

1. void supplemental_page_table_init(struct supplemental_page_table *spt);
   → 새로운 프로세스를 시작하거나 fork로 자식 프로세스를 만들 때 호출됨
   → 보조 페이지 테이블 spt를 초기화함

void
supplemental_page_table_init (struct supplemental_page_table *spt UNUSED) {
	hash_init(&spt->spt_hash, page_hash, page_less, NULL);
}

2. struct page spt_find_page(struct supplemental_page_table spt, void *va);
   → SPT에서 가상 주소 va에 해당하는 struct page를 찾아 반환
   → 없으면 NULL 반환

/* Find VA from spt and return page. On error, return NULL. */
struct page *
spt_find_page (struct supplemental_page_table *spt UNUSED, void *va UNUSED) {
	struct page *page = NULL;
	uint64_t key=hash_bytes(&va,sizeof(va));
	struct hash_iterator i;

	hash_first (&i, &spt -> spt_hash);
	while (hash_next (&i))
	{
	struct page *p = hash_entry (hash_cur (&i), struct page, hash_elem);
		if (p->va==va){
			page=p;
			break;
		}
	}
	return page;
}

3. bool spt_insert_page(struct supplemental_page_table spt, struct page page);
   → 새로운 페이지 정보를 보조 페이지 테이블에 삽입
   → 중복 va가 존재하지 않는 경우에만 삽입함
   → 내부적으로 spt_find_page(spt, page->va)로 중복 여부 검사 필요

/* Insert PAGE into spt with validation. */
bool
spt_insert_page (struct supplemental_page_table *spt UNUSED,
		struct page *page UNUSED) {
	bool succ = false;
	/* TODO: Fill this function. */
	// uint64_t key=hash_bytes(&page->va,sizeof(page->va));
	if (spt_find_page(spt, page->va)==NULL){
		hash_insert(&spt->spt_hash, &page->hash_elem );
		succ=true;
	};

	return succ;
}

---

frame management

보조 테이블은 가상 주소에 대한 정보를 담고 있지만,
실제로 데이터를 담는 물리 메모리 페이지는 frame이 관리한다.

struct frame {
	void *kva;           // 커널 가상 주소 (실제로 데이터를 담는 곳)
	struct page *page;   // 이 프레임에 연결된 가상 페이지
};

---

구현해야 할 함수들 (vm/vm.c)

1. static struct frame *vm_get_frame(void);
   → palloc_get_page()로 유저 공간 프레임 한 개를 가져온다
   → struct frame을 할당하고 초기화한 뒤 반환
   → 실패 시 PANIC("todo")

static struct frame *
vm_get_frame (void) {
	struct frame *frame = NULL;
	/* TODO: Fill this function. */
	struct frame *frame=palloc_get_page(PAL_USER);
	frame->kva=NULL;
	frame -> page=NULL;

	ASSERT (frame != NULL);
	ASSERT (frame->page == NULL);
	return frame;
}

2. bool vm_do_claim_page(struct page *page);
   → 인자로 받은 struct page에 대해 물리 메모리 프레임을 할당한다
   → 내부에서 vm_get_frame() 호출하여 frame을 할당받고
   → page->frame에 연결하고, MMU를 통해 가상 주소 <-> 물리 주소 매핑을 등록한다
   → 성공 시 true 반환

static bool
vm_do_claim_page (struct page *page) {
	struct frame *frame = vm_get_frame ();

	/* Set links */
	frame->page = page;
	page->frame = frame;

	/* TODO: Insert page table entry to map page's VA to frame's PA. */
	//pml4에서 해당 pte를 갖고와라?
	if (!spt_insert_page(&thread_current()->spt, page)){
		return false;
	}

	return swap_in (page, frame->kva);
}

3. bool vm_claim_page(void *va);
   → 특정 가상 주소에 대해 페이지를 할당하고, 해당 페이지에 프레임을 매핑함
   → spt_find_page(spt, va)로 해당 주소에 이미 page가 있는지 확인
   → 있으면 그 page를 대상으로 vm_do_claim_page() 호출
   → 없으면 새로운 page를 만들어 spt_insert_page() 후 vm_do_claim_page() 호출

bool
vm_claim_page (void *va UNUSED) {
	struct page *page = NULL;
	/* TODO: Fill this function */
	if (va==NULL) return false;
	if (page=spt_find_page(&thread_current()->spt,va)==NULL){
		page=palloc_get_page(PAL_USER);
		page->va=va;
	}
	return vm_do_claim_page (page);
}

---

전체 흐름 정리

[ 가상 주소 va ]
↓
spt_find_page(spt, va) // 보조 테이블에서 페이지 존재 확인
↓ (없으면)
spt_insert_page(spt, page) // 새 페이지 생성 후 테이블에 삽입
↓
vm_claim_page(va) // 이 주소에 페이지를 실제로 매핑하기 위해
↓
vm_do_claim_page(page) // 페이지에 프레임 연결
↓
vm_get_frame() // 새 물리 메모리 프레임 할당
↓
page <-> frame 연결
↓
MMU(PML4) 에 매핑 추가 // 가상 주소와 물리 주소 연결 완료

/* Copy supplemental page table from src to dst */
//fork 시 부모 → 자식 SPT 복사
bool
supplemental_page_table_copy (struct supplemental_page_table *dst UNUSED,
		struct supplemental_page_table *src UNUSED) {
	memcpy(&dst->spt_hash, &src->spt_hash, sizeof(struct supplemental_page_table));
}

/* Free the resource hold by the supplemental page table */
void
supplemental_page_table_kill (struct supplemental_page_table *spt UNUSED) {
	/* TODO: Destroy all the supplemental_page_table hold by thread and
	 * TODO: writeback all the modified contents to the storage. */
	hash_destroy(&spt->spt_hash, &spt->spt_hash.hash);
}

• hash

unsigned
page_hash (const struct hash_elem *p_, void *aux UNUSED) {
  const struct page *p = hash_entry (p_, struct page, hash_elem);
  return hash_bytes (&p->va, sizeof p->va);
}

/* Returns true if page a precedes page b. */
bool
page_less (const struct hash_elem *a_,
           const struct hash_elem *b_, void *aux UNUSED) {
  const struct page *a = hash_entry (a_, struct page, hash_elem);
  const struct page *b = hash_entry (b_, struct page, hash_elem);

  return a->va < b->va;
}

struct page *
page_lookup (const void *address) {
  struct page p;
  struct hash_elem *e;

  p.va = address;
  e = hash_find (&pages, &p.hash_elem);
  return e != NULL ? hash_entry (e, struct page, hash_elem) : NULL;
}
profile