Menu
Article Pintos

PintOS Project 3: VM

MaxLevSnail

• 6 min read

핀토스 프로젝트 3을 진행하며 중간중간 적었던 내용들을 정리했다.

이번 프로젝트 3의 경우 무엇보다 코드를 이해하는 것이 중요하다. 먼저 mmu.c에 어떤 함수들이 있는지 읽고 vm.c를 작성하기 시작하자. 또한 페이지가 어떻게 로딩되는지 알아볼 때는 process.c의 load 함수를 읽어보면 좋다. page fault 핸들링 또한 다시 읽어보자. 무지성으로 달려들었다가는 처음부터 다시 작성해야 할 수도 있으니 꼭 이해하고 시작하자.

이 프로젝트의 extra 부분은 Copy on Write를 구현하는 것이다. 주어진 sample testcase가 매우 빈약해 extra credit을 노린다면 많은 testcase를 제작해 시험해보는 것이 중요하다. 예시로는 fork를 여러번 한 뒤 physical address를 확인해볼 수 있다. Copy on Write의 경우 fork와 관련되어 있기에 copy on write를 구현하기 시작하면 많은 testcase들이 터지게 된다. 그래서 꼭 데드라인보다 충분한 시간을 두고 시작해야 한다.

이 프로젝트부터는 시간에 치여 프로젝트를 진행했기에 기록을 많이 하지 못했다. 그래서 종강 이후 기억을 되짚어 작성하는 것이니 틀린 부분이 있을 수 있다.

먼저 적는 부분은 mmap까지 구현한 기록이다. 여기까지 완료하면 

FAIL tests/vm/page-merge-par
FAIL tests/vm/page-merge-stk
FAIL tests/vm/page-merge-mm
FAIL tests/vm/swap-file
FAIL tests/vm/swap-anon
FAIL tests/vm/swap-iter
FAIL tests/vm/cow/cow-simple

와 같이 8개 테스트 케이스만 실패하게 된다.

Stack growth의 경우 다음과 같았다.
(git으로 과거 기록을 확인해본 것이라 구현 상 버그로 인해 fail한 testcase도 있을 수 있다)

FAIL tests/vm/pt-write-code2
FAIL tests/vm/page-merge-par
FAIL tests/vm/page-merge-stk
FAIL tests/vm/page-merge-mm
FAIL tests/vm/mmap-read
FAIL tests/vm/mmap-close
FAIL tests/vm/mmap-unmap
FAIL tests/vm/mmap-overlap
FAIL tests/vm/mmap-twice
FAIL tests/vm/mmap-write
FAIL tests/vm/mmap-ro
FAIL tests/vm/mmap-exit
FAIL tests/vm/mmap-shuffle
FAIL tests/vm/mmap-bad-fd
FAIL tests/vm/mmap-clean
FAIL tests/vm/mmap-inherit
FAIL tests/vm/mmap-misalign
FAIL tests/vm/mmap-null
FAIL tests/vm/mmap-over-code
FAIL tests/vm/mmap-over-data
FAIL tests/vm/mmap-over-stk
FAIL tests/vm/mmap-remove
FAIL tests/vm/mmap-zero
FAIL tests/vm/mmap-bad-fd2
FAIL tests/vm/mmap-bad-fd3
FAIL tests/vm/mmap-zero-len
FAIL tests/vm/mmap-off
FAIL tests/vm/mmap-bad-off
FAIL tests/vm/mmap-kernel
FAIL tests/vm/lazy-file
FAIL tests/vm/swap-file
FAIL tests/vm/swap-anon
FAIL tests/vm/swap-iter
FAIL tests/vm/cow/cow-simple

그리고 그 때 당시 메모했던 내용들이다. 구현을 다 마치고 적은 것이 아니기에 수정해야 할 부분이 여러 곳 존재할 수 있다.

Memory Management

  • spt는 hash table로 구성되어 있음.
    • init, find, insert는 hash table로 사용됨
    • 이를 위해 hash_elem 이 struct page에 들어가 있음.
    • hashfunc와 page_less는 hash table 작동을 위한 함수들.
  • vm_get_frame: palloc으로 페이지 받은 뒤 frame 만들어서 리턴
  • vm_do_claim_page: frame과 page struct를 연관짓고 pml4_set_page로 페이지 설정
  • vm_claim_page: malloc으로 페이지 struct 만든 뒤 vm_do_claim_page

Anonymous page

  • vm_alloc_page_with_initializer
    • upage 주소가 spt에 없으면 페이지 스트럭트 malloc으로 만든 뒤 type에 맞게 uninit_new 호출
    • upage 주소가 있으면 그 페이지 spt에서 remove 한 뒤 새로 만들어 삽입
      (spt kill 을 잘못 만들고 짠거라 현재는 없어도 될 듯?)
  • uninit_initialize, vm_anon_init, anon_initializer: 손 안 댐
  • load segment
    • load_aux 이용해서 lazy loading에 필요한 정보들 저장한 뒤 aux로 전달
  • lazy load segment: aux 정보 이용해서 파일 읽음. 그리고 dirty false로 바꾸어서 초기상태라는걸 알림
  • supplemental_page_table_copy
    • hash iterator 이용해 spt iteration.
    • page의 type 확인 후 알맞게 alloc.
    • 만약 lazy loaded 된 페이지라면 memcpy 실행
  • supplemental_page_table_kill
    • hash_clear 이용해 kill. hash_clear 위해서 destruct_spt 함수 만듦.
  • uninit_destroy, anon_destory: 손 안 댐

Stack Growth

  • vm_try_handle_fault
    • 그냥 rsp와 addr 비교해서 8 차이나면 stack_growth 실행
  • vm_stack_growth
    • 필요한 페이지 모두 alloc.

Memory Mapped File

  • thread에 file_mapped list 추가.(그 thread가 mmap해 놓은 파일들 확인용)
  • file_mapped struct는 시작 주소, mmap된 페이지수, file 포인터로 구성되어 있음.
  • do_mmap
    • arguments verification 이후 load_segment 실행. (코드 복붙함... 그냥 include 해도 되었을듯..)
    • load_segment 완료하면 thread에 file_mapped struct 추가.
  • do_munmap
    • thread의 file_mapped list traversal 하면서 해당하는 addr에 mmap된 파일 있나 확인
    • 있으면 없애기
      • 모든 페이지마다 dirty이면 write 실행 후 삭제
      • 모든 페이지를 다 없앤 뒤 file 닫고 list_remove실행
  • vm_file_init, file_backed_initializer, file_backed_destroy: 손 안 댐

그 다음 swap부터는 그 때 코딩하면서 적은 것이 아닌, 종강 후 코드를 다시 보면서 적는 것이고, 내가 아닌 플메가 작성한 부분도 있기에 잘 못 적은 내용도 있을 수 있다. 이 점 유의하고 읽어주었으면 한다.

Swap in/out

  • Anon page의 경우 swap table을 사용한다.
    • swap table의 경우 calloc을 통한 array로 사용하였다.
    • swap table의 경우 synchronization때문에 lock이 필요할 수도 있다.
  • File backed page의 경우 그냥 straightforward하게 구현하면 될 것이다.
  • frame table의 경우 FIFO policy를 채택하였고, 그래서 list를 사용하였다.
    • LRU 등 더 복잡한 policy를 사용해도 되지만, FIFO로도 충분하다.

Copy on Write

  • Copy on write에서는 생각해야 할 점이 많다.
    • parent process에서 copy되기 전에 parent가 끝날 수 있으니 이 점을 처리해야 한다.
    • parent process에서 copy되기 전 fork가 더 일어날 수 있다.
    • swap이 될 때 경우를 생각해주자.
    • 등등 (솔직히 더는 잘 기억이 안 난다)
  • 나는 page struct에 copy가 필요한지 변수를 넣어 구현하였다.
    • 그리고 copy on write가 필요한 child들을 기억하기 위해 list를 사용했다.

여담으로 VM의 경우 multi-oom 테스트가 없기 때문에 약간의 memory leak는 있어도 크게 문제 없다.

Share