Pintos - vm [페이지 할당 초기화 과정을 위한 흐름도]

https://gyumingomin.tistory.com/91

Pintos - SPT(Supplemental Page Table)와 Hash Table

 

https://gyumingomin.tistory.com/89

Pintos - 사용자 프로그램 흐름

와..

1. load_segment

load_segment에 대한 흐름으로 오기 위해 사용자 프로그램 흐름의
5. load(): argument 파싱, PML4 생성, ELF 파일 열기
6. Program Header 순회: 실제로 올릴 segment 고르기
7. read_bytes와 zero_bytes: file에 있는 부분과 0으로 채울 부분
8. load_segment(): page마다 frame을 잡고 파일 내용을 채움
부분을 먼저 읽기를 권장드립니다.

실제로 Pintos 내부에서
load()안의 validate_segment()에서 ELF segment를 메모리에 올려도 되는가?를 검증하고
load_segment()로 와서 그 segment를 실제 유저 가상 주소 공간에 어떻게 배치할까 등록하는 단계이다.

static bool
load_segment(struct file *file, off_t ofs, uint8_t *upage,
			 uint32_t read_bytes, uint32_t zero_bytes, bool writable)
{
	ASSERT((read_bytes + zero_bytes) % PGSIZE == 0);
	ASSERT(pg_ofs(upage) == 0);
	ASSERT(ofs % PGSIZE == 0);

	while (read_bytes > 0 || zero_bytes > 0)
	{
		/* Do calculate how to fill this page.
		 * We will read PAGE_READ_BYTES bytes from FILE
		 * and zero the final PAGE_ZERO_BYTES bytes. */
		size_t page_read_bytes = read_bytes < PGSIZE ? read_bytes : PGSIZE;
		size_t page_zero_bytes = PGSIZE - page_read_bytes;

		/* TODO: Set up aux to pass information to the lazy_load_segment. */
		void *aux = NULL;
		if (!vm_alloc_page_with_initializer(VM_ANON, upage,
					writable, lazy_load_segment, aux))
			return false;

		/* Advance. */
		read_bytes -= page_read_bytes;
		zero_bytes -= page_zero_bytes;
		upage += PGSIZE;
	}
	return true;
}

여기에서는 아직 구현하지 못한 lazy_load_segment는 일단 제쳐두고 vm_alloc_pag_with_initializer 부터 보고자 한다.
이유는 lazy_load_segment를 구현하려면 우선 page fault까지의 흐름이 이해가 되어야 그 다음 단계가 진행되기 때문

2. vm_alloc_page_with_initializer

vm_alloc_page_with_initializer (enum vm_type type, void *upage, bool writable, vm_initializer *init, void *aux)

/* Create the pending page object with initializer. If you want to create a
 * page, do not create it directly and make it through this function or
 * `vm_alloc_page`. */
bool
vm_alloc_page_with_initializer (enum vm_type type, void *upage, bool writable,
		vm_initializer *init, void *aux) {

	ASSERT (VM_TYPE(type) != VM_UNINIT)

	struct supplemental_page_table *spt = &thread_current ()->spt;
	upage = pg_round_down(upage);

	/* Check wheter the upage is already occupied or not. */
	if (spt_find_page (spt, upage) == NULL) {
		/* TODO: Create the page, fetch the initialier according to the VM type,
		 * TODO: and then create "uninit" page struct by calling uninit_new. You
		 * TODO: should modify the field after calling the uninit_new. */
		struct page *page = malloc(sizeof *page);
		if (page == NULL)
			goto err;
		
		bool (*initializer)(struct page *, enum vm_type, void *kva);

		switch (VM_TYPE(type)) {
			case VM_ANON:
				initializer = anon_initializer;
				break;
			case VM_FILE:
				initializer = file_backed_initializer;
				break;
			default:
				free (page);
				goto err;
		}

		uninit_new (page, pg_round_down(upage), init, type, aux, initializer);
		page->writable = writable;

		if (spt_insert_page (spt, page))
			return true;

		vm_dealloc_page(page);
	}
err:
	return false;
}

구현하기에 앞서 먼저 알아보기 위해 필요한 내용을 먼저 정리

2-1. bool (*initializer)(struct page *, enum vm_type, void *kva)

initializer 라는 변수는
struct page *, enum vm_type, void *를 인자로 받고 bool을 반환하는 함수의 주소를 저장할 수 있다.

bool anon_initializer(struct page *page, enum vm_type type, void *kva);
bool file_backed_initializer(struct page *page, enum vm_type, void *kva);

2-1-ⓐ. bool anon_initializer

/* Swap in the page by read contents from the swap disk. */
static bool
anon_swap_in (struct page *page, void *kva) {
	struct anon_page *anon_page = &page->anon;
}

/* Swap out the page by writing contents to the swap disk. */
static bool
anon_swap_out (struct page *page) {
	struct anon_page *anon_page = &page->anon;
}

/* Destroy the anonymous page. PAGE will be freed by the caller. */
static void
anon_destroy (struct page *page) {
	struct anon_page *anon_page = &page->anon;
}

// include/vm/anon.h
struct anon_page {
};

아직 anon_page는 구현되어 있지 않고, 이 부분에서 먼저 이해를 잡고 갈 부분은
anon_initializer()과 struct page_operations anon_ops 이다.
anon_initializer()
uninit 상태의 page를 anonymous page로 초기화하는 함수이다.
page->operations를 anon_ops로 바꾸고, anon page에 필요한 필드를 초기화한다.
실제 파일 내용을 읽는 lazy_load_segment는 이 후 init 콜백으로 실행된다.
anon_ops
anonymous page가 사용할 연산 테이블이다.
swap_in, swap_out, destroy 함수 포인터를 갖고 있으며, page가 anonymous page로 초기화된 뒤부터 이 동작들이 사용된다.

2-1-ⓑ. bool file_backed_initializer

/* Swap in the page by read contents from the file. */
static bool
file_backed_swap_in (struct page *page, void *kva) {
	struct file_page *file_page UNUSED = &page->file;
}

/* Swap out the page by writeback contents to the file. */
static bool
file_backed_swap_out (struct page *page) {
	struct file_page *file_page UNUSED = &page->file;
}

/* Destory the file backed page. PAGE will be freed by the caller. */
static void
file_backed_destroy (struct page *page) {
	struct file_page *file_page UNUSED = &page->file;
}

// include/vm/file.h
struct file_page {
};

아직 file_page도 구현되어 있지 않고, 이 부분에서 먼저 이해를 잡고 갈 부분은
file_backed_initializer()과 struct page_operations file_ops이다.
file_backed_initializer()
uninit 상태의 page를 file_page로 초기화하는 함수이다.
page->operations를 file_ops로 바꾸고, file page에 필요한 필드를 초기화한다.
실제 파일 내용을 읽는 lazy_load_segment는 이 후 init 콜백으로 실행된다.
file_ops
file page가 사용할 연산 테이블이다.
swap_in, swap_out, destroy 함수 포인터를 갖고 있으며, page가 file page로 초기화된 뒤부터 이 동작들이 사용된다.

2-2. uninit_new

아직 실제 물리 프레임에 올라가지 않은 page를 VM_UNINIT 상태로 만들고, 나중에 page fault가 발생했을 때 어떤 타입의 page로 초기화할지와 어떤 추가 초기화 작업을 할지를 저장하는 함수

2-2-ⓐ. struct page안의 uninit_page

2-2-ⓑ. struct page_operations uninit_ops

static const struct page_operations uninit_ops = {
	.swap_in = uninit_initialize,
	.swap_out = NULL,
	.destroy = uninit_destroy,
	.type = VM_UNINIT,
};

/* Initalize the page on first fault */
static bool
uninit_initialize (struct page *page, void *kva) {
	struct uninit_page *uninit = &page->uninit;

	/* Fetch first, page_initialize may overwrite the values */
	vm_initializer *init = uninit->init;
	void *aux = uninit->aux;

	/* TODO: You may need to fix this function. */
	return uninit->page_initializer (page, uninit->type, kva) &&
		(init ? init (page, aux) : true);
}

/* Free the resources hold by uninit_page. Although most of pages are transmuted
 * to other page objects, it is possible to have uninit pages when the process
 * exit, which are never referenced during the execution.
 * PAGE will be freed by the caller. */
static void
uninit_destroy (struct page *page) {
	struct uninit_page *uninit UNUSED = &page->uninit;
	/* TODO: Fill this function.
	 * TODO: If you don't have anything to do, just return. */
}

uninit_new() 함수를 통해 .uninit 멤버를 설정해주는 작업이 실제로 swap_in을 통해 하는 작업과 동일한 것을 볼 수 있다.
그 이유 : 아직 한 번도 메모리에 올라간 적 없는 uninit page를 처음 frame에 올릴 때도 swap_in()이라는 공통 인터페이스를 쓰기 때문에 사용

2-3. vm_dalloc_page

void
vm_dealloc_page (struct page *page) {
	destroy (page);
	free (page);
}

페이지 할당/등록에 실패했을 때 방금 만든 struct page를 정리하는 함수

destroy page

page->opertaions->destroy를 호출해서 페이지 타입별 자원을 정리

예를 들면 uninit 페이지면 uninit_destroy(), anon 페이지면 anon_destroy(), file 페이지면 file_backed_destroy()

free(page)

malloc(sizeof(struct page))로 만든 struct page 메타 데이터 자체를 해제

지금까지 ELF segment를 페이지 단위로 쪼개고 각 upage에 대한 struct page를 만들었고 SPT에 등록
하지만 frame은 없는 상태이므로 파일 내용도 아직 읽지 않음
아직 구현이 안된 부분이 많은데 페이지 폴트 인터럽트가 발생 후 실제 호출되는 위치를 찾은 후 구현을 하는 게 맞다는 판단에 스켈레톤 코드만 만들어 놓고 page fault 쪽으로 넘어가고 구현 예정

SPT:
  0x401000 -> VM_UNINIT page, frame = NULL, init = lazy_load_segment
  0x402000 -> VM_UNINIT page, frame = NULL, init = lazy_load_segment
  0x403000 -> VM_UNINIT page, frame = NULL, init = lazy_load_segment

정리
"다음으로 user instruction이 발생 후 작동 흐름은 아래와 같음"

process_exec()
  -> load()
      -> t->pml4 = pml4_create()
      -> process_activate(thread_current())
          -> pml4_activate(t->pml4)
              -> lcr3(vtop(pml4))   // CR3에 PML4 물리주소 로드
      -> load_segment()
          -> VM이면 SPT에 lazy page만 등록
      -> setup_stack()
      -> do_iret()
          -> user mode로 진입

user instruction fetch / load / store 발생
  -> CPU/MMU가 CR3의 PML4를 참조해서 주소 변환
  -> PTE가 없거나 present bit가 꺼져 있음
  -> CPU가 #PF, interrupt vector 14 발생
  -> page_fault()
      -> rcr2()로 fault address 읽음
      -> vm_try_handle_fault()
      -> SPT에서 fault addr에 해당하는 page 찾음
      -> frame 할당
      -> page table에 va -> frame 매핑
      -> swap_in()
      -> uninit_initialize()
      -> lazy_load_segment()
      -> 파일 내용 읽고 zero-fill
      -> 유저 프로그램 재개

이 흐름에서 궁금한 내용

①. user instruction fetch / load / store 발생이 무슨 말이지?
②. CPU가 #PF, interrupt vector 14 발생 시키는데 이건 무슨 인터럽트지?
③. rcr2로 fault address를 읽는데 이 코드는 어디에 있을까?
④. 파일 내용 읽고 zero-fill을 한다 무슨 말일까?

①. user instruction fetch / load / store 발생

user instruction : 유저 프로그램의 기계어 명령

[예시]
int x = arr[0];
arr[1] = 3;

컴파일 되면
mov (%rax), %rbx   ; load: rax가 가리키는 메모리에서 읽기
mov $3, 4(%rax)    ; store: rax+4 주소에 쓰기

CPU는 유저 모드에서 이 명령들을 실행하면서 메모리 접근을 계속 함
instruction fetch는 CPU가 명령어 자체를 메모리에서 가져오는 것

rip = 0x401000
CPU: 0x401000 주소에 있는 명령어 바이트를 읽자는 명령
MMU: 0x401000 가상주소를 물리주소로 변환
이때 0x401000 페이지가 아직 PML4에 매핑되어 있지 않으면, 명령어를 가져오는 순간에도 page fault가 날 수 있음
즉, 데이터를 읽거나 쓸 때만 fault가 나는 게 아니라 코드를 실행하려고 명령어를 가져올 때도 fault 발생가능

load : 명령어가 데이터 메모리를 읽는 것 [mov (%rax), %rbx]
store : 명령어가 데이터 메모리에 쓰는 것 [mov %rbx, (%rax)]
fetch : CPU가 rip 주소에서 명령어 바이트를 읽는 것

②.  CPU가 #PF, interrupt vector 14 발생

https://gyumingomin.tistory.com/93

Pintos - interrupt 비교 (#PF(page fault), Timer Interrupt)

③. rcr2로 fault address

rcr2() 함수는 "page fault가 난 가상주소를 CPU의 CR2 레지스터에서 읽어오는 함수"

실제로 pintos 내부에서는 intr_handler라는 함수 안에 handler가 #PF page_fault 함수안에 존재한다.

접은글 : intr_handler 함수와 page_fault 함수와 rcr2 함수 - (이미 구현되어 있는 코드)

 

CR2는 CPU가 주소 변환 중 page fault를 발견했을 때, "방금 접근하려다 실패한 linear/virtual address"를 하드웨어가 자동으로 적어두는 레지스터이다. [참고] : CR3는 현재 프로세스의 PML4 주소를 자동으로 적어두는 레지스터

char x = *(char *)0x8048123;
이 주소가 아직 매핑되지 않았다면 CPU가 #PF를 발생시키고, CR2에는 0x8048123 이 들어감
f->rip는 fault를 일으킨 명령어 주소이고, rcr2()가 읽는 값은 그 명령어가 접근하려던 주소이다.

정확히 rcr2가 어떤 흐름으로 호출이 되는지를 알기 위한 흐름 정리

1. 부팅 (threads/init.c) - main 초기화 흐름에서
exception_init() 호출

2. IDT에 등록 (userprog/exception.c) (threads/interrupt.c)
intr_register_int (14, 0, INTR_OFF, page_fault, "#PF Page-Fault Exception");
- 여기서 interrupt vector number = 14, #PF Page Fault를 page_fault() 함수에 연결
- INTR_OFF인 이유는 CR2가 "가장 최근 page fault 주소"를 담기 때문에, handler가 CR2를 읽기 전까지
  interrupt를 꺼서 값이 덮이는 상황을 피하려는 것

intr_handlers[14] = page_fault;
이때, IDT의 14번 entry가 intr14_stub, 실제로는 intr0e_stub 쪽을 가리키도록 설정됨

3. 유저 코드가 instruction fetch/laod/store을 하다 page fault 발생
CPU가 현재 CR3의 PML4부터 page table을 따라가다 PTE가 없거나 present bit가 꺼져 있거나 권한 위반일 경우
CR2 = faulting virtual address [vector 14 #PF 발생]

4. (intr-stubs.S)
STUB(0e, REAL) 이 page fault용 stub임. REAL은 CPU가 이미 error code를 push했다는 뜻
stub은 vector number 0x0e를 push하고 intr_entry로 점프
그리고 intr_entry는 레지스터들을 저장해서 struct intr_frame 모양을 만들고 call intr_handler를 호출함

5. (threads/interrupt.c)
- intr_handle()는 frame->vec_no를 보고 등록된 handler를 찾음
handler = intr_handlers[frame->vec_no];
handler (frame);
- frame->vec_no == 14 이므로 결국 page_fault(frame)이 호출됨

6. (userprog/exception.c)
fault_addr = (void *) rcr2();

init.c
  -> exception_init()
    -> intr_register_int(14, ..., page_fault)
      -> intr_handlers[14] = page_fault
      -> IDT[14] = intr0e_stub

나중에 유저 코드가 잘못된/아직 안 올라온 VA 접근
  -> CPU가 CR3 기반 page table walk
  -> 실패하면 CPU가 CR2에 fault VA 저장
  -> CPU가 IDT[14]로 진입
  -> intr0e_stub
  -> intr_entry
  -> intr_handler(frame)
  -> intr_handlers[14](frame)
  -> page_fault(frame)
  -> rcr2()
  -> fault address 획득

④. 파일 내용 읽고 zero-fill

ELF segment가 항상 "파일에 있는 바이트만큼만" 메모리에 올라가는 게 아님

실행 파일의 program header에는 2가지 크기가 존재

p_filesz : 파일 안에 실제로 존재하는 데이터 크기

p_memsz : 실행 중 메모리에서 차지해야 하는 크기

p_memsz >= p_filesz

(조건) - 왜 memsz가 더 클까?

어떤 segment는 파일에 일부만 저장되어 있고, 메모리에서는 그 뒤 공간까지 존재함.

파일에 없는 나머지 부분은 C/OS 규칙상 0으로 초기화되어야 함.

[대표 예시 .bss]

int global_initialized = 123;   // 파일에 값이 들어감, .data
int global_zero;                // 파일에는 안 들어감, .bss
char big_buffer[4096];          // 파일에 4096바이트를 저장하지 않음, .bss

global_zero나 big_buffe는 프로그램이 시작하면 메모리에 존재해야 하지만, 실행 파일에 전부 0으로 저장해두면 파일 크기가 쓸데없이 커짐. 그래서 ELF는 p_memsz > p_filesz로 표현

따라서 load_segment()에서 한 페이지마다 계산하는 것도 정상적으로 처리 가능

page_read_bytes = 이 페이지에서 파일로부터 읽을 바이트 수
page_zero_bytes = PGSIZE - page_read_bytes
[예시]
파일에서 읽을 부분:  1000 bytes
나머지 메모리 부분: 3096 bytes
             ↓
kva[0..999]       <- file_read()
kva[1000..4095]   <- memset(..., 0)

이렇게 해야 프로세스 입장에서는 해당 페이지 전체가 정상적인 메모리처럼 보이고, 파일에 없던 .bss/padding 영역도 0으로 보장됨. 또 하나 중요한 이유는 보안/정확성임. palloc_get_page(PAL_USER) 로 받은 물리 프레임에는 이전에 누군가 쓰던 쓰레기 값이 남아 있을 수 있어서 zero-fill을 하지 않으면 프로그램이 초기화되지 않은 커널/다른 프로세스 잔여 데이터를 보거나, 테스트에서 전역 0 초기화가 깨짐

파일에 있는 부분은 파일로 읽고, 파일에 없는 나머지는 반드시 0으로 만든다는 의미 (ELF 로딩 규칙)