PintOS Project 3. Virtual Memory - WIL

노션에 적어놓은 일일 일지를 정리해서 합친 글입니다.

지식 공유가 아닌, 저의 공부 일지를 저장하는 목적의 포스트이기 때문에

정돈되지 않은 글인 점, 유의 바랍니다.

 

프로젝트 3 키워드들

Virtual memory management

• paging
  • virtual page
  • physical frame
  • page table & supplementary page table
• Memory Management Unit (MMU)
• Translation Lookaside Buffer (TLB)

Page type

• Uninitialized page
  • Lazy initialization
• Anonymous page
  • stack growth
• file-backed page
  • mmap syscall

Swap in/out

• page replacement policy
• swap disk

Copy on Write (COW)

프로젝트 3주차 공부기록들

1. https://velog.io/@rivolt0421/Pintos-3.-VIRTUAL-MEMORY-1

간단 버전: 가상 주소 → MMU의 walking(번역) → 물리주소

핀토스의 가상 메모리 구조

• 유저 영역
• 커널 영역
  • 프로세스별 PT가 커널 영역에 존재
  • 프로세스가 실행될 때마다, CR3 레지스터에 프로세스의 PT 주소를 넣어줌(아마도 PML4 테이블일 것임. Page의 시작주소) → MMU의 walking → 4단계 거치면서 마지막 PT에 대한 PTE(Page Table Entry) 찾아 냄. Page = 4KB 이므로, 한 페이지에서 2^12개 물리주소 저장 가능
    • PTE는 PT 내의 각 요소들(페이지 테이블 엔트리)이고, *PTE = 물리주소

• 유저-커널 영역을 가르는 기준
  • LOADER_KERN_BASE = 0x8004000000
  • 64bit로 변환

• PML4 테이블의 1번째 인덱스
• PDP의 0번째 인덱스
• PD 테이블의 32번째 인덱스
• PT의 0번째 인덱스 → 페이지 구했다! → 4096B: 각 1B는 Physical Offset!

 

• 각 프로세스는 1개의 PML4 테이블을 갖는다.
• PML4 테이블을 포함한 모든 테이블은 프로세스의 커널 영역에 있다.
• process_activate(thread*)를 호출하면, CR3에 해당 쓰레드의 pml4 테이블이 들어간다.
  • 각 프로세스별 PML4는 다르기 때문에, 해당 프로세스의 PML4를 사용하도록 교체해주는 것이다.

2. 핀토스 VM docs - 한글판

Memory Terminology

Page

• 4096Byte의 연속된 가상 메모리 영역
• 각 페이지의 시작 주소는 2^12(4096)으로 나누어져야 한다. → 하위 12비트를 physical offset으로 사용하기 위해
  • 이유: 하위 12비트 = 2^11, 13비트부터 이제 주소는 2^12로 나누어지게 된다. 그리고 하위 12비트는 모두 0이어야 2^12로 나누어질 수 있다 → physical offset으로 활용

KERN_BASE 미만의 가상주소: user 영역

KERN_BASE 이상의 가상주소: kernel 영역

Frame

 

프레임은 위 그림처럼 프레임 넘버 + 오프셋 으로 이루어져 있다

→ 한 프레임은 512개의 주소로 이루어져 있다!

커널 가상 메모리의 첫 페이지 = 물리 메모리의 첫 프레임

커널 가상 메모리의 두번째 페이지 = 물리 메모리의 두번째 프레임

Page Tables

가상 주소 → 물리주소

= 페이지 → 프레임

가상 주소 + 페이지 테이블 → 물리주소

Swap Slots

• 스왑 파티션 내 디스크의 페이지 크기 영역
• Page(4kb) 크기
• 마찬가지로 page-aligned됨(시작 주소가 4096으로 나누어 떨어짐)

Resource Management Overview

1. Suplemental page table
   • Page Fault Handling 가능하도록 해줌
2. Frame table
   • eviction policy 구현에 도움을 줌
3. Swap table
   • 스왑 슬롯 사용을 추적함

위 3가지를 완전히 별개의 자료구조로 구현하는게 필수는 아니다.

각 자료구조가 어떤 필드를 가질지 정해야 함

자료구조의 범위를 전역(전체 시스템)으로 할지, 지역(프로세스)으로 할지 정해야 함

쉽게 구현하려면 malloc,calloc 써서 자료구조 내의 포인터가 유효한 상태로 유지되도록 할 수도 있음

Choices of implementation(Performance perspective)

array, list

• 구현이 간단.
• 순회하면서 찾는 비용

bitmap

• bit들이 원소인 배열
• 각 bit는 0과 1으로, false와 true를 나타냄
• bitmap[2] = 1이라면, 자원 2가 사용중임을 나타냄
• bitmap 크기는 고정되어 있지만, 리사이징되도록 변경 가능

hash

• 다양한 테이블 크기에서의 삽입, 삭제 효율적임

Managing the Supplemental Page Table

• 각 페이지에 대한 추가 정보를 바탕으로 페이지 테이블을 보조함
• 구성요소
  • 각각의 페이지가 어떤 영역에 위치하는지
    • frame, disk, swap
  • 포인터 정보?
  • active, inactive
• 사용예
  • 한 페이지에 대해 fage fault 발생시, 해당 페이지에 어떤 데이터가 있었어야 했는지를 보조 페이지 테이블에서 얻어올 때,
  • 프로세스 종료시 어떤 자원이 해제될지 파악할 때,
    • 프로세스가 사용하는 페이지들을 free 해줘야 함. → 어떤 페이지가 사용되는지 파악할 때 필요할 듯

Organization of Suplemental Page Table

• 세그먼트(segment, 연속적인 페이지) 측면 구조
• 페이지 측면 구조

Handling page fault

프로젝트1, 2에서의 page fault → 잘못된 접근, 에러

프로젝트3 → 파일 or 스왑 슬롯에서 페이지를 가져와야 함을 의미

userprog/exception.c 내 page_fault() → vm/vm.c 내 vm_try_handle_fault() 호출

page fault handler가 page fault를 처리하는 과정:

1. 보조 페이지 테이블에서 fault된 페이지에 해당하는 보조 페이지를 찾음
2. 메모리 참조가 타당하면, 해당 엔트리를 사용해서 페이지를 찾는다
   • file system or swap slot or all zero pages
   • copy-on-write

1. • 엔트리가 주는 정보가,
     • 접근하려던 주소에서 데이터 얻을 수 없다
     • 페이지가 커널 영역에 있다
     • 읽기 전용인데 쓰기 시도
     → 유효하지 않은 접근 → 프로세스 종료 + 프로세스의 모든 자원 해제
2. 페이지 저장을 위해 프레임 획득
   • sharing 구현한다면, 필요한 데이터는 이미 프레임 안에 있음 → 프레임 찾기
3. 데이터를 프레임에 넣어주는데, file system이나 swap, zeroing 방식 등으로 읽어서 넣어준다. sharing 구현했으면 이미 필요한 페이지가 프레임에 있기 때문에 무시해도 됨
   • sharing이 뭔가?
4. 폴트 발생한 가상주소에 대한 PTE가 해당 물리 페이지를 가리키도록 함(mmu.c)

Managing the Frame Table

→ for eviction policy

비어 있는 프레임이 없을 때, 쫓아낼 페이지를 찾아서 해제해서 생긴 공간을 사용할 때 필요함

유저 페이지를 위한 프레임들은 user pool에서 얻어야 함.

→ PAL_USER 플래그 사용

frame이 free 상태라면 그냥 해당 frame을 사용하면 되는데, free frame이 프레임 테이블에 없으면, free시킬 페이지를 쫓아내서 매핑되었던 프레임을 free로 만들어줘야 함

쫓아낼 프레임이 없을 때 → 스왑 슬롯에서 할당받음 → 실패했을 경우→ 커널패닉

eviction 절차

1. 페이지 재배치 알고리즘 구현
   • 쫓아낼 프레임 구함
   • acessed, dirty 비트(페이지 테이블 내의 ) 사용
2. 해당 프레임 참조하는 모든 페이지 테이블에서 참조 제거
3. 필요하면 페이지를 파일 시스템이나 스왑에 write하기

Accessed and Dirty Bits

페이지에 read, write할 때, PTE의 accessed bit를 1로 설정

write할 때, dirty bit를 1로 설정

→ CPU가 함

0으로 되돌리는 주체 → OS

 

같은 프레임을 참조하는 두 개 이상의 페이지들인 aliases를 조심해야 함.

각각의 페이지들은 서로 다른 PTE를 가지고 있고, 따라서 해당 프레임에 접근해서 read,write할 때

gpt 답변

핀토스에서 유저 가상페이지-커널 가상페이지: alias 관계

→ 유저 코드(프레임)에 대해 유저,커널페이지가 저 프레임을 참조함

• 양쪽 주소 모두를 위한 accessed, dirty 비트 확인 및 업데이트 해야함

→ 유저 가상 주소를 통해서만 유저 데이터에 접근하게 해서 커널이 이 문제 피하게 가능

Managing the Swap Table

사용중인 스왑 슬롯과 빈 스왑 슬롯을 추적함

스왑 슬롯의 역할 공부

내 예상: 메모리 내 프레임이 더이상 필요한 만큼 없을 때 → 페이지-프레임 연결 해제 → 페이지를 스왑 슬롯에 할당 → 이후 다시 스왑 슬롯 내의 페이지를 read 할 때 → 스왑 내 페이지 free 후 프레임 할당

 

Managing Memory Mapped File

파일을 메모리 할당해서 올리는 것 → 메모리 맵드 파일

어떤 메모리 영역이 memory mapped file에 의해 사용되는지를 추적해야 함

→ 페이지 폴트, 등등 다루기 위해

 

Memory Management

페이지와 프레임을 관리해야 함 → supplemental page table

• 누가 사용했는지,
• 사용되는지,
• 무슨 목적으로
• 등등

Page Structure and Operations

struct page

눈여겨 볼 곳

• • union 필드는 세 종류의 페이지로 이루어져 있는데, 저 한번에 저 3개 중 하나만 가질 수 있음
  • → 페이지의 상태: 비초기화 상태 or 익명 상태 or 파일 or 페이지 캐시(안씀, 4장)

page operations

• 앞서 말한 대로, 페이지는 3가지 타입이 존재함(uninit, anonymous, file)
• 페이지는 swap in, swap out, destroy(페이지 삭제) 동작 수행 가능
• 페이지 타입별로 destory 작동이 다름
• → 특정 페이지를 destory하려고 할 때, 해당 페이지의 타입을 확인해서 switch 구문 써서 맞는 destroy 함수 적용? → 이미 해당 페이지에 page_operations 구조체가 있고, 이 안에 destroy 함수가 있어서 이거 그냥 쓰면 되지 않나? → 이거 쓰면 되고, 함수 포인터를 이용해서 구현하였음
• 클래스 상속(class inheritance)
• 함수 포인터(function pointer)https://www.geeksforgeeks.org/function-pointer-in-c/

함수 포인터 사용예

implement supplemental page table

supplemental page table 설계 → supplemental_page_table_init 구현

supplemental_page_table_init(): initd(), __do_fork에서 호출됨

spt_find_page(struct supplemental_page_table *spt, void *va): spt에서 va에 해당하는 페이지 구조체 찾아서 반환

spt_insert_page(spt, page): spt에 page 삽입. 이미 같은 page가 존재하는지 확인해야 함

 

frame management

frame struct

vm.h에 만들어져 있는 frame 구조체. 필드 추가 가능

 

frame 관련 구현할 함수들

 

struct frame* vm_get_frame(void)

: frame 하나 받는 함수

1. palloc_get_page() 호출해서 물리메모리 페이지 가져옴
2. 물리메모리 페이지와 프레임을 연결시킴
   • 프레임 할당
   • 프레임 구조체 멤버 초기화
3. 해당 프레임 반환

bool vm_do_claim_page(struct page *page)

: page에 물리 메모리 frame 할당

1. vm_get_frame() 해서 frame 하나 얻기
2. MMU 세팅하기(page → frame 매핑 정보 추가)
3. 성공시 true, 실패시 false 리턴

bool vm_claim_page(void *va)

: 인자로 받은 va로부터 page를 get 한 후, vm_do_claim_page(page) 호출해서 결과 반환하는 함수

Anonymous Page

anonymous page = non-disk image

익명(anonymous)라고 불리는 이유: file-backed page와 달리 파일 소스를 가지고 있지 않기 때문에. 그리고 그 파일은 이름이 있기 때문에.

스택과 힙 영역에서 anonymous page 사용됨

file-baked pages: 코드, 데이터 섹션 로드시 사용

anonymous pages: 스택, 힙 섹션

 

관련 구조체

include/vm/anon.h의 anon_page

Page initialization with Lazy Loading

lazy loading: 페이지가 실제로 필요하기 전에는 메모리에 로딩을 하지 않다가, 필요해지면 페이지에 해당하는 데이터를 메모리에 로딩하는 것

페이지는 있지만, 프레임은 아직 없고, 프레임과 대응하는 실제 데이터(콘텐츠)도 아직 메모리에 로드되지 않은 상태

이후, 페이지를 사용하려고 할 때, 페이지와 연결된 프레임이 없어서 페이지 폴트 exception이 발생해서 page_fault()가 호출되면, vm_try_handle_fault()가 호출되어 page와 frame이 매핑된다.

페이지 초기화 과정

1. 커널: 새로운 페이지 달라는 요청 받음
2. vm_alloc_page_with_initializer() 호출
   • 페이지 생성, 초기화(타입에 맞는), 페이지 리턴
3. 근데 아직 페이지는 매핑된 프레임이 없음 → 페이지를 통해 프레임 접근시 페이지 폴트

 

페이지 폴트 처리과정에서 uninit_initialize() 호출 → 세팅해 놓았던 초기화 함수 호출됨

페이지 타입 별로 상태 변이 과정에서 호출되는 함수(프로시저)가 다름

Lazy Loading for Executable

실행파일을 메모리에 로드할 때, 딱 당장 필요한 만큼만 메인 메모리에 로드됨

모든 페이지는 처음에 uninit 타입으로 생성됨

 

10/10 화

가상 메모리 구조 블로그 읽고 정리(핀토스 3주차 공부자료들 내에 있음)

공식문서 VM 소개글 다 읽고 정리, Memory Management 반쯤 읽고 정리

 

10/11 수

할일

1. 공식문서 VM 다 읽고 정리 → 저녁 먹기 전까지 완료
   • memory management는 정리했음
   • anonymous page부터는 좀 쓰다가 읽기만 했음
2. 핀토스 코드 분석 → 24시 전까지 완료
   • palloc_init
   • pml4가 어떻게 초기화되는지
   • page_fault() 코드 확인
   • 궁금증 해결 필요
     • page_fault가 뜨는 부분은 맨 마지막 PT에서 뿐인가? 아니면 pml4 - pdpt - pdt ? 이런 과정 속에서도 page_fault가 뜰 수 있는가?
   • mmu에서 엔트리 값을 얻고 나서 어떻게 offset을 적용해서 다음 엔트리를 얻는지 코드로 확인
   • get_palloc() 이렇게 생긴 함수는 물리메모리에서 페이지를 할당받는거였다
     • 이 함수가 어떤식으로 작동하는지 파악하기
   • 전반적인 palloc.c, mmu.c 코드 파악
   • userprog 프로젝트에서 oom 테스트 코드 파악
   • init.c에도 페이지 초기화 관련 함수 있음 → 이거 파악
   • anon.c, anon.h
   • file.c, file.h
   • uninit.c, uninit.h
   • vm.c, vm.h
3. 앞으로 뭐 할지 정하기

시간 사용 일지

~ 13:20 - 기상, 점심

13:20 ~ 13:33 - 오늘 할일 작성

13:33 ~ 15:24 - 공식 문서 VM 보면서 정리(최대한 cow 전까지 하려고 하기)

• Memory Management
• Anonymous Page
• Stack Growth
• Memory Mapped Files
• Swap In/Out

일단 cow까지 다 보기는 했음

swap in: 디스크 or 스왑 디스크 or file에 있는 컨텐츠를 다시 메인 메모리에 올리기

swap out: 메인 메모리가 모두 사용중일 때 eviction policy를 써서 퇴출시킬 프레임 정하고, 해당 프레임에 속하는 컨텐츠를 타입에 맞게 퇴거시키기

cow: 자식프로세스 fork할 때 자식은 기존에는 그냥 모든 페이지 내 컨텐츠를 복사했었다. 그런데 굳이 그럴 필요 없이 그냥 read만 할 경우에는, 부모 프로세스 생성시 메인 프레임에 올려놓았던 컨텐츠를 부모와 공유해서 사용하면 된다. 그래서 자식의 가상메모리 페이지는 부모의 가상페이지와 매핑된 프레임들을 공유해서 사용한다. 이후, write요청이 들어왔을 경우에만 파일의 복사본을 만들어 메인 메모리에 올리고 프레임과 연결짓고 페이지-프레임 연결시켜준 후에 write 한다.

15:40 ~ 16:13

• paging_init(): 커널 영역을 페이징하기 위해 초기화 시켜주는 곳이후, pml4e_walk() → pdpe_walk() → pgdir_walk() 로 가면서, (uint64_t)pte & PTE_P 를 해서 false면 해당 엔트리에는 매핑된 물리주소가 없다는 소리다. true면 해당 엔트리에는 매핑된 물리주소가 있다는 소리다.결국 메모리주소 0에서 mem_end까지에 대해 base_pml4가 맨 처음 페이지이자 테이블이 되어 트리모양으로 싹 모든 메모리를 페이지로 잘라 초기화시켜주는 것이다.
• false인 경우, create == 1이면, palloc_get_page() 호출해서 물리 메모리로부터 물리페이지를 할당받는다. 이후, 속해 있는 단계에 해당하는 테이블에 엔트리를 넣어주어야 하는데, 엔트리는 결국 물리주소값이다. 따라서 저 할당받은 페이지(가상주소)를 물리주소로 바꾸고(vtop), 읽기,쓰기,타입(커널인지 유저인지) 비트를 켜준 후, 테이블에 넣는다.
• 커널 영역을 페이지 크기단위로 잘라서 우선 va를 구해준 후, (존재, 쓰기)비트 체크한 후, va가 start ≤ va < end_kernel_text 사이면 읽기 권한은 체크 해제함 → 왜인지 모름

16:13 ~ 17:13 - mmu.c의 walk 코드 공부중

한 번 pml4e_walk(uint64_t *pml4e, const uint64_t va, int create)가 호출될 시,

pml4e(=pml4 테이블 내 엔트리 하나)를 이용해서 최종 va에 해당하는 가상 주소

void *
pml4_get_page (uint64_t *pml4, const void *uaddr) {
	ASSERT (is_user_vaddr (uaddr));

	// user virtual address에 대응하는 physical address(페이지 테이블 엔트리) 반환 
	uint64_t *pte = pml4e_walk (pml4, (uint64_t) uaddr, 0);

	// 해당 페이지 가상주소
	if (pte && (*pte & PTE_P))
		return ptov (PTE_ADDR (*pte)) + pg_ofs (uaddr);
	return NULL;
}

이 코드 해석:

인자로 pml4와 user virtual address를 받는다.

pml4e_walk()에 인자로 pml4와 uaddr, create값 = 0을 넣는다.

반환값으로 pte를 받는데, 이 값은 pml4e_walk가 호출되면, pdpe_walk, pgdir_walk을 거치면서 각 테이블로 가다가, pdgir_walk에서는 pdp와 idx를 이용해서 pgdir 테이블의 시작주소를 받은 후,

ptov(PTE_ADDR(pdp[idx]) + 8 * PTX(va))를 해서 물리 페이지의 시작 주소(물리주소) → 가상주소 변환한 값을 받아 리턴

결국 pml4e_walk의 반환값 = 가상주소 uaddr가 속해 있는 물리페이지의 시작 주소를 가상주소로 변환한 후 반환됨.

이후, pte를 받으면, 이 가상주소는 물리페이지의 시작 주소에 해당하고, 여기에는 아직 uaddr의 offset값이 반영되지 않았으므로, pg_ofs(uaddr)값을 더해준 값을 반환한다.

/* Adds a mapping in page map level 4 PML4 from user virtual page
 * UPAGE to the physical frame identified by kernel virtual address KPAGE.
 * UPAGE must not already be mapped. KPAGE should probably be a page obtained
 * from the user pool with palloc_get_page().
 * If WRITABLE is true, the new page is read/write;
 * otherwise it is read-only.
 * Returns true if successful, false if memory allocation
 * failed. */
bool
pml4_set_page (uint64_t *pml4, void *upage, void *kpage, bool rw) {
	ASSERT (pg_ofs (upage) == 0);
	ASSERT (pg_ofs (kpage) == 0);
	ASSERT (is_user_vaddr (upage));
	ASSERT (pml4 != base_pml4);

	uint64_t *pte = pml4e_walk (pml4, (uint64_t) upage, 1);

	if (pte)
		*pte = vtop (kpage) | PTE_P | (rw ? PTE_W : 0) | PTE_U;
	return pte != NULL;
}

upage에 kpage를 연결시키는 함수

우선, pml4e_walk(pml4, upage, 1)을 호출하는데, create = 1이므로, 물리페이지 없을 땐 생성시키면서 계속 가서 물리페이지의 엔트리를 반환함

근데 pgdir_walk에서 마지막 페이지의 시작주소(엔트리 포인터)를 반환하는데, 이 엔트리 포인터가 NULL이 아닐까?

→ 근데 create = 1이므로, 일반적인 경우 무조건 NULL이 아님

따라서 해당 페이지의 엔트리값 *pte를 palloc_get_page() 호출결과인 kpage로 삼는다.

이때 kpage값 역시 가상주소이므로, 우선 vtop로 물리주소로 바꿔준 후에 flag 설정을 해준다.

이후 flag 설정: PTE_P, PTE_W, PTE_U

그리고 pte NULL이면 false, 그 외엔 true 리턴

/* Looks up the physical address that corresponds to user virtual
 * address UADDR in pml4.  Returns the kernel virtual address
 * corresponding to that physical address, or a null pointer if
 * UADDR is unmapped. */
void *
pml4_get_page (uint64_t *pml4, const void *uaddr) {
	ASSERT (is_user_vaddr (uaddr));

	// user virtual address에 대응4하는 physical address(페이지 테이블 엔트리) 반환 
	uint64_t *pte = pml4e_walk (pml4, (uint64_t) uaddr, 0);

	// 해당 페이지 가상주소
	if (pte && (*pte & PTE_P))
		return ptov (PTE_ADDR (*pte)) + pg_ofs (uaddr);
	return NULL;
}

여기에서 func == duplicate()이고, 여기에 va가 들어가는데, 이 va의 하위 12비트는 모두 0이다. 이후 duplicate() 내에서 pml4_get_page(pml4, va)를 해서 반환값으로 return ptov (PTE_ADDR (*pte)) + pg_ofs (uaddr); 인데, 지금 uaddr의 하위 12비트는 모두 0이므로, pg_ofs(uaddr) = 0이다. 따라서 물리페이지의 시작 주소에 0이 더해졌으므로 리턴값은 물리페이지의 시작주소다. 따라서, 이후에 dulicate_pte()에서 pml4_get_page의 반환값을 parent_page에 받아서 memcpy(newpage, parent_page, PGSIZE)를 해줄 때, parent_page는 물리페이지의 시작주소이므로, 4KB인 PGSIZE만큼을 전부 복사해줘도, 해당 페이지를 초과하여 복사되지 않는다는걸 알았다. 나는 pml4_get_page()가 물리페이지 시작주소 + offset값을 반환했을 때, 이후 memcpy(newpage, parent_page, PGSIZE)를 하면, parent_page의 중간부분부터 PGSIZE만큼 복사가 되기 때문에, 다른 페이지 데이터까지 복사가 될 수 있다고 생각했었다.

duplicate_pte (uint64_t *pte, void *va, void *aux) {
	struct thread *current = thread_current ();
	struct thread *parent = (struct thread *) aux;
	void *parent_page;
	void *newpage;
	bool writable;

	/* 1. TODO: If the parent_page is kernel page, then return immediately. */
	if (is_kernel_vaddr(va))
		return true;

	/* 2. Resolve VA from the parent's page map level 4. */
	parent_page = pml4_get_page (parent->pml4, va);
	if (parent_page == NULL)
		return false;

	/* 3. TODO: Allocate new PAL_USER page for the child and set result to
	 *    TODO: NEWPAGE. */
	newpage = palloc_get_page(PAL_USER);
	if (newpage == NULL)
		return false;

	/* 4. TODO: Duplicate parent's page to the new page and
	 *    TODO: check whether parent's page is writable or not (set WRITABLE
	 *    TODO: according to the result). */
	memcpy(newpage, parent_page, PGSIZE);
	writable = is_writable(pte);

	/* 5. Add new page to child's page table at address VA with WRITABLE
	 *    permission. */
	if (!pml4_set_page (current->pml4, va, newpage, writable)) {
		/* 6. TODO: if fail to insert page, do error handling. */
		return false;
	}
	return true;
}

parent_page = pml4_get_page() → 부모 페이지(프레임) 얻기

newpage = palloc_get_page(PAL_USER) → 새 페이지 만들기(page 전체가 0으로 초기화된 상태)

memcpy(newpage, parent_page, PGSIZE) → 프레임(한페이지) 전체를 parent_page에서 newpage로 복사

pml4_set_page(pml4, va, newpage, writable) → 우선, pml4에 va를 매핑시키고, va와 newpage를 연결시킨다.

pml4와 va(upage) 연결은 pml4e_walk()를 통해 이루어지고, 연결 결과 페이지엔트리가 들어갈 pte를 반환한다.

이제 pte와 newpage(kpage) 연결은 *pte = vtop(kpage) | PTE_P | (rw ? PTE_W : 0) | PTE_U

1. 앞으로 공부 순서
   
   • 조지아텍 OS 영상 보기
   • 공식문서 다시 읽기
   • 책 8장 9장
   • pintos3.pdf
   • 블로그(paging system에서의 evict policy, demand paging)
   • → 읽으면서 계속 큰그림 그리기
   • 질문 리스트 읽기

10/13 금

할 일

팀 vm저장소 사용해서 구현(주석 옮기기)

frame 테이블 구현

vm 함수들 구현

lazy loading 구현

맨 처음에 물리주소 전체영역에서palloc_get_page()를 한 결과를 커널 가상주소와 매핑을 한다

→ 물리메모리 페이지까지 뚫긴 하는데, 커널 가상주소 - 물리주소 매핑만 시켜주겨 실제로 palloc get page해서 물리메모리내 데이터가 담기는 페이지 할당은 안함

page 구조체 생성시 palloc get page 쓰는데 이거는 유저쪽

가서 더 보기

 

14:28 ~ vm_initializer 디버깅 시작

uninit_new() 호출시 초기화되는 page struct

bucket에 elem 넣었을 때 bucket 상황

 

head의 next와 tail의 prev가 모두 같은 elem 가리킴 → 들어갔음

vm_initializer에 spt find 조건문 내부에서 true false를 리턴해줘야 했는데 그런 코드가 없었어서 그냥 errror로 가면서 false 리턴했었음

이제 몇번 load_segment 하다보면 터진다

→ setup_stack() 호출되면서 터짐

vm_claim_page(va) 해서 va에 대해 struct page를 구하고,

vm_do_claim_page(page) 해서, 위에서 구한 페이지와 vm_get_frame()을 해서 얻은 frame을 서로 연결시키고 mmu 세팅도 해줌. 이후 swap_in(page, frame→kva) 호출해서 스왑인 해서 물리메모리에 올림

저녁 먹고 시작

해야할 것들

1. lazy_load_segment()에 넘겨줄 인자가 지금 aux인데, aux는 file_info struct를 넘겨줘야 함.
   • 이 file_info 구조체의 멤버
     • file
     • read_bytes
     • zero_bytes
   • 어디에 struct file_info를 만들지
   • file_info는 process.c에서 필요
2. file_info struct를 넘겨받은 lazy_load_segment() 함수는 저 file_info를 이용해서 file_read()를 수행해주는데, 구현은 기존의 load_segment()를 참고해서 한다.
3. 위 구현이 끝나면 이제 setup_stack() 함수 구현만 하면 됨
   • 스택도 마찬가지로 페이지를 할당해야 하는데, 페이지의 타입을 anonymous로 한다.
   • 스택도 마찬가지로 lazy_loading 방식으로 구현하므로, vm_initializer()을 호출해서 페이지를 얻는다.

남은 것

1. setup_stack()
   • 그냥 바로 페이지 할당해주는거로 구현하기
2. vm_try_handle_fault()
   • 유효한 페이지 폴트인지 검사
     • 유효하지 않은 경우
       • 유저모드인데 커널영역 접근
       • ?
     • 유효한 경우
       • 스택이 초과한 경우

스택도 lazy_loading 으로 하자

지금 lazy_load_segment() 함수내에서 프레임을 할당 받았나?

→ vm_do_claim_page() 해줄 때, frame을 받아서 page와 연결시켜주기 때문에 프레임은 이미 할당된 상태

 

parse_argv_to_stack() 호출

→ strlcpy(stack_ptr, argv[i], strlen(argv[i]) + 1) 호출

스택은 lazy_loading이기 때문에 page fault 발생

→ 핸들러 브레이크 포인트 찍어보기

stack접근시 page_fault 발생 → page_fault() → fault_addr 값(rcr2())

 

이후, vm_try_handle_fault() → spt_find_page() 호출 결과 page = NULL임(오류)

 

spt의 hash table에 va를 키값으로 insert, find해줄 때, va는 page-aligned 되어있어야 한다.

→ 한 페이지상의 0~4095위치의 주소를 찍을 때, 모두 하나의 페이지를 뽑아내야 한다. 따라서 가상주소의 하위 12비트를 버린 후, 페이지 시작주소만을 남긴 값을 키값으로 한다.

 

오류 발생

오류 원인: pml4_set_page()에서 vtop(kpage)할 때, is_kernel_vaddr(kpage) 체크를 하는데, 커널 가상주소가 아니란다.

 

 

확인해보니, vm_get_frame()에서 frame 구조체만 만들고, 막상 frame에 해당하는 물리메모리 영역은 할당하지 않았었다.

그래서 우선, malloc으로 frame을 만든 후, palloc_get_page()를 써서 물리메모리 할당을 해서 반환값인 kva를 frame→kva에 넣어줬다.

그런데 palloc_get_page()가 NULL인 경우, 모든 물리메모리 사용중이므로 이제는 evict할 프레임을 찾아서 evcit하고 frame을 반환해서 이걸 사용한다.

 

오류발생

vm_get_frame()에서 assertion (frame→page == NUL)L이 failed

→ frame의 page가 NULL이어야 하는데, NULL이 아닌거다.

 

malloc 대신 calloc으로 바꾼 후 수행

palloc_free_multiple(): assertion (bitmap_all(pool→used_map, page_idx, page_cnt) 실패

install_page()에서 안됨

1. 일단 넣었던 page가 나오는지 확인
   • setup_stack()에서 initializer() 호출할 때 넣은 page 주소랑 비교
2. install_page() → pml4_get_page() 할 때, pml4e_walk(pml4, (uint64_t)uaddr, 0)의 반환값인 pte = NULL이 나온다.
   • NULL이 나와야 한다. 아직 pml4에 page를 set하지 않았으므로,
   pml4_set_page()할 때,

문제 원인 발견

• vm_do_claim_page()에서 install_page()를 해줬었는데, 이후 swap_in()할 때 uninit_initialize()에서 또 install_page()를 해준다.

문제 또 발견

두번째 page_fault 발생시에 안됨

두번째 발생 page_fault의 가상주소값 = 0x400000

swap_in(page, frame→kva) 결과가 false임

 

lazy_load_segment() → file_read() 할 때 터짐

lazy_load_segment에서 f_info.file.inode를 찾아봤을 때

아이노드에 이상한 값이 들어있음

문제 원인

1. lazy_load_segment에 넘겨주는 file_info를 load_segment()에서 딱 한번 생성한걸 사용하고 있었다. 그런데 이렇게 하면 안된다. 왜? → 각 lazy_laod_segment()에 넘겨주는 file_info의 read_bytes, zero_bytes, offset은 모두 다르기 때문
2. 따라서 while문 안에서 vm_initializer()를 호출할 때마다 aux로 넣어주는 file_info를 계속 새롭게 만들어주면 해결
3. load() 함수가 끝나면 바로 file_close(file)해줬던 기존의 코드따라서 load()에 있는 file_close(file) 코드를 지우고, process_exit() 내에 file_close(file)을 넣어줌으로써, file 사용이 끝나기 전까지는 file을 유지하고 있도록 한다.
4. 기존의 코드는 eager loading 방식이었기 때문에 load()작업이 끝나면 파일을 닫아줬어도 됐었다. 하지만 lazy_loading 방식은 load()에서는 그냥 페이지 구조체만 spt에 넣어주는 작업을 하기 때문에, 아직 파일데이터를 실제 물리메모리에 적재해두진 않은 상태다. 이때 file_close()를 해버리면, 이후 페이지폴트가 발생해서 파일에 접근하려고 할 때, 이미 파일에 대한 자원이 free된 상태라서 쓰레기값이 들어가 있게 된다.
5. 따라서 load()에 있는 file_close(file) 코드를 지우고, process_exit() 내에 file_close(file)을 넣어줌으로써, file 사용이 끝나기 전까지는 file을 유지하고 있도록 한다.

10/14 토

할 일

1. 구현 완성유무 파악
   • vm_get_frame()
     • calloc()에 대해 NULL 체크를 안해줌
   • vm_do_claim_page
     • vm_get_frame()로 frame을 반환받아 사용하는데, vm_get_frame() 반환값은 NULL이면 안되도록 ASSERT 해놓았음. 따라서 무조건 frame은 잘 들어온다고 가정하고 코드짜기 → 그래도 NULL이면 false 리턴되게 해놨음
     • 원래 기존에는 여기서 install_page()를 했었는데, 이렇게 하면 이후 swap_in()할 때 실패할 수도 있는데 가상-물리 매핑정보가 페이지 테이블에 들어간다. 그래서 swap-in의 두번째 함수부분(lazy_load_segment)에 instal_page()를 넣었다.
   • supplemental_page_table_copy
     • struct hash hash;
       • size_t elem_cnt;
       • size_t bucket_cnt;
       • struct list* buckets;
       • hash_hash_func *hash;
       • hash_less_func *less;
       • void *aux;
     • 이걸 다 복사하려면?
       • 일단 새로운 spt는 있다.
       • elem_cnt, bucket_cnt: primitive 타입이라 그냥 가져다 붙이면 된다.
       • buckets: list* 타입이라 포인터값이다. 따라서 이 포인터 값을 복사한다면 자식 프로세스의 spt도 같은 buckets를 사용하게 된다.
       • → 각 리스트마다 복사하기
       • hash(), less(): 어차피 같은 함수 사용하므로 그냥 가져다 쓴다.
       • aux: 초기화할 때 NULL 넣으니까 그냥 NULL 넣기
       • 일단 supplemental_page_table_init() 한다.
         • 이후, h→elem_cnt 값 교체
         • bucket 개수는 h→bucket_cnt에 있고, 부모 spt의 buckets를 bucket_cnt만큼 돌면서, 자식의 buckets에 하나씩 복사해준다.
         • bucket에 insert할 때는

이런식으로 해줬었다. 즉, bucket은 list고, list에는 list_elem이 들어가 있다. bucket을 순회하며 발견하는 list_elem을 새 bucket에 넣자.

• hash_apply() 함수 적용하면 될듯
• 근데, do_fork 해서 자식을 만들 때, 부모의 spt를 자식의 spt에 복제해주는 이유
  • cow가 적용되지 않은 경우, fork를 할 때, 완전히 새로운 물리메모리를 할당한 후 page도 새롭게 만들어서 연결지어야 한다.
  • 일단, 부모의 spt 내 해시 버켓들을 순회하긴 해야 함. page를 확인 해서,
    1. 새 page 만들 때, uninit_new() 해서 만들기(부모page의 인자와 같게)
    2. 부모 page 확인 후, frame 값 확인
       • NULL인 경우
         • 끝
       • NULL이 아닌 경우
         • frame이 할당되어 있으므로, 자식page에도 frame 만들어줘야 함. frame 만들고, frame→kva에 부모의 frame→kva 값부터 4KB까지 복사
    • 이미 frame이 매핑된 경우(frame = NULL) 여부로 확인: 새 frame을 vm_claim_frame()으로 확보한 후, frame→kva 부터 PGSIZE만큼 복사하고, 연결지음
    • frame이 없는 경우 → 아직 lazy_load_segment 호출 전 상태: 그냥 struct page 복제하고 va만 바꿔주기
• frame table

지금 fork-once 테스트 해결중

• supplemental_page_table_copy() 구현중
• 구현 다 했는데,

이런식으로, 자식이 바로 exit(-1)됨

디버깅 계획:

• 일단, fork가 호출되면, syscall_handler() 호출됨
• fork → page_fault → syscall_handler →
• 여기까지 확인

1. 1번 부분 구현
2. 문서 보면서 anonymous까지 구현
3. 테스트 돌려보고 project2 실패하는 부분에 대해 고치기
4. 다 고쳤으면 stack growth 하기

• memcpy(도착지, 출발지, 사이즈) 이렇게 해줘야 했는데 도착지 출발지를 거꾸로 적었다.
• 해결

10/15 일

할일

실패한 테스트 확인

• FAIL tests/userprog/read-boundary
• FAIL tests/userprog/write-normal
• FAIL tests/userprog/fork-read
  • read(handle, buffer, 20) → buffer_validity_check()에서 pml4_get_page() 통과 못함
  • 위 함수에서 버퍼의 시작주소, 끝주소를 validate 하는 코드가 있는데, 끝주소에서 터진건지 확인 못했음 → 확인
  • 확인 결과

• 버퍼의 시작주소부터 pml4_get_page(addr) 결과 NUL이 나와서 false 리턴
• pml4_get_page(addr) 들어가보기
• 일단 buffer의 시작주소: 0x406f45

*pte = NULL임. 매핑 안되어 있음.

 

1. page fault나는 주소, round_down 주소 파악

페이지폴트 주소!!: 0x4747ff90 ROUNDED 페이지폴트 주소!!: 0x4747f000

페이지폴트 주소!!: 0x400d7b ROUNDED 페이지폴트 주소!!: 0x400000

페이지폴트 주소!!: 0x408200 ROUNDED 페이지폴트 주소!!: 0x408000

페이지폴트 주소!!: 0x401196 ROUNDED 페이지폴트 주소!!: 0x401000

페이지폴트 주소!!: 0x404750 ROUNDED 페이지폴트 주소!!: 0x404000

페이지폴트 주소!!: 0x4030a6 ROUNDED 페이지폴트 주소!!: 0x403000

페이지폴트 주소!!: 0x4021fd ROUNDED 페이지폴트 주소!!: 0x402000

 

2. buffer의 시작주소 파악: 0x406f45, page_fault 안남

 

3. load_segment()에서 upage 파악

mem_page: 0x3ff000

mem_page: 0x400000

mem_page: 0x406000

 

4. load_segment() → vm_alloc_page_with_initializer()에 들어가는 upage 파악

upage: 0x3ff000

upage: 0x400000

upage: 0x401000

upage: 0x402000

upage: 0x403000

upage: 0x404000

upage: 0x405000

upage: 0x406000

upage: 0x407000

upage: 0x408000

page_fault: 0x405…, 0x406…, 0x407… 없음

5. upage: 0x405…, 0x406…, 0x407…일 때 vm_initializer()에서 어떻게 되나 확인

- spt_insert_page(spt, page) 되기 전까지는 잘 들어옴.

 

→ 문제 원인, syscall read해서 pml4_get_page() 하는 시점이 buffer주소에 대해 page_fault가 발생한 이후인줄 알았다. 하지만 아직 저 주소에 대해 fault나지는 않아서 페이지테이블에 등록이 안된 상태인데 저함수의 반환값 == NULL이면 false가 되도록 했었다.

fork에서 문제

file_info는 malloc으로 할당받았는데, 다 썼으면 free 해줘야 한다. 그런데 자식이 먼저 레이지 로딩이 끝나고 free()를 해주면, 막상 부모쪽에서 file_info를 쓸 때 이미 free되어서 쓸 수가 없다. 따라서 자식에게 file_info 자체를 복사해서 넘겨주어야 한다.(부모쪽에서 lazy_loading이 끝난 경우에는 그냥 페이지에 적힌 데이터를 복붙하면 됨)

malloc, calloc으로 할당받았던거 다 썼으면 free 해주어야 함.

 

10/16 월

void* munmap(void* va) 구현중

일단 va에 대해 struct page가 있는지 판단(spt 사용)

있으면, 해당 페이지에 frame이 할당되었는지 판단

할당 되어 있으면, 이미 로딩된 상태임. 따라서 타입체크 매크로 사용함

• 타입이 file타입이면, 해당 페이지 구조체의 file.init_mapped_va 확인해서 munmap의 인자로 들어온 va와 같은지 판단
  • 같으면 유효한 do_munmap임
  • 다르면 exit(-1)
• 그 외 타입(anon)이면 exit(-1)

할당 안되어 있는 경우

• uninit.type 확인
  • 타입이 file인 경우, 아직 로딩되지 않은 file_mapped_page임. 따라서 uninit.aux.init_mmaped_va 확인 후 addr과 같은지 확인
  • 그 외 타입이면 exit(-1)

여기까지 살아남았으면 일단 유효한 주소(mmap() 호출시 반환주소)임

이제, addr부터 pgsize만큼 더해가면서 spt에서 page를 찾아내면서 타당성 판단함

일단, 할당 되어 있는 경우,

• 해당 페이지의 타입이 file이고 file.init_mmaped_va가 addr이면 free해줌
• 그 외의 경우 break

할당 안되어 있는 경우,

• uninit.type = vm_file이고, uninit.aux.init_mmaped_va가 addr이면 free 해줌
• 그 외의 경우 break

추가: mmap할 때 매핑되는 영역에 대한 검사 필요 → 커널영역 넘는지,

• 영역의 끝지점:rsp보다 작아야 함
• 이거만 체크하고 나머지는 spt로 확인해도 될듯

mmap한 데이터 dirty해지면 swap out시 디스크에 변경사항을 저장해야 함

write하면 dirty해짐. write 요청이 들어왔을 시 바로 디스크에 적는게 아니라 이렇게 쓰겠다 하는 정보가 있어야 함?

페이지 단위로 dirty 체크. dirty bit 활성화.

궁금증: 지금은 write하면 버퍼에 있는게 바로 파일에 써져서 디스크에 저장되는건가? -> 확인

write할 때 set_dirty 써서 dirty 1 해주기

munmap할 때 get_dirty 써서 1이면 디스크에 변경사항 write

 

10/17 수

현재, dst = mmap의 시작지점.

memcpy할 때,dst에 접근해서 쓰기 연산 수행

이때, page fault 발생 → 해당 페이지에 대해 진짜 데이터를 받아서 적재함

이후 다시 memcpy 수행

memcpy는 매핑된 자리에 복사하는 것임

→ munmap시 dirty bit 확인 후 디스크에 쓸지 결정

 

디버그 돌리기

dirty bit가 1로 안되는 현상

pml4_set_dirty()에서

 

pte에 접근해서 값을 채워주는건데, 아직 물리메모리 매핑이 일어나지 않았음

• page_fault_handle()에서 do_claim_page() 이후에 set_dirty() 추가
• 그래도 안됨
• 일단 munmap 확인

 

spt_find_page(spt, temp_addr) 결과가 0x0임

 

해결 완료: 맨 처음에 코드 작성시에는 mmap 첫 페이지 이후부터 보면서 확인하려고 해서 저렇게 addr + PGSIZE만큼 더해준 주소부터 확인했는데, 이후 설계가 변경되어서 처음 페이지부터 확인해줘야 했는데 이걸 반영하지 않았다.

PGSIZE를 지움으로써 해결 완료

• pml4_is_dirty에서 1인지 확인

FAIL tests/vm/page-merge-stk

FAIL tests/vm/page-merge-mm

 

FAIL tests/vm/mmap-ro

• 테스트 코드 과정
  1. large.txt 파일 open
  2. large 파일에 대해 mmap 수행하는데, 이번엔 writable = false다.
  3. 이후, mmap에 쓰기 연산 수행하려고 한다.
     • 일단은 물리메모리 매핑되지 않았으므로, page_fault → page_fault_handler() 될 것이다.
     • writable은 pte에 있고, handler의 인자로 write가 들어오므로, 이 두개를 비교해서 해결하기

FAIL tests/vm/mmap-exit 설명

/* Executes child-mm-wrt and verifies that the writes that should
   have occurred really did. */

1. 자식 하나 만든다
2. 자식은 sample.txt 파일을 만들고(create, 사이즈: 795), open하고, mmap해서 매핑해준다.
3. 이후, 매핑영역에 sample데이터를 memcpy해준다.
4. 부모는 wait(child) == 0에서 자식을 기다리다가, 자식이 작업을 마치면 check_file(”sample”, sample, sizeof(sample))을 호출한다.
5. check_file 함수에서는 check_file_handle() 호출하는데, 인자로 fd, file_name, buf, size를 넣는다

spt_remove_page()는 해시테이블에서 page 제거하고 page에 맡는 destroy 수행

 

supplemental_page_table_kill()은 해시테이블의 각각의 원소에 대해,

 

근데 destroy_page()에서 vm_dealloc_page(page) 수행하는데, 여기서 결국 file_backed_destroy()가 호출되면 더티체크된 file은 디스크에 써져야 하는데 안써진다.

일단 795 바이트가 써져야 하는데, 512바이트만 써짐.

 

*pte = 0b101000110000000001100111

PTE_D = 0b1000000

 

문제 원인: process_exit()에서 wait_sema를 up 해주는 부분의 위치 문제

• process_cleanup() 이후에 sema_up(wait_sema)를 해줘야 했다.

 

FAIL tests/vm/mmap-clean

/* Verifies that mmap'd regions are only written back on munmap
   if the data was actually modified in memory. */

1. 문제상황: mmap 하고 나서 memcmp 해서 매핑 영역에 접근하는데, page_fault 안뜸
   • 확인결과, vm_try_handle_fault()에서 주소값 유효성 체크할 때, addr > USER_STACK이면 false 리턴하도록 했는데, 테스트코드에서 저 USER_STACK보다 큰 주소값이 들어와서 바로 exit(-1) 되었었다.

FAIL tests/vm/mmap-inherit

부모에서 sample 파일을 open한 후, sample 파일에 대해 actual주소부터 mmap을 수행한다.

이후, memcmp를 수행해서 파일을 actual에 로딩시킨다.

그리고 자식을 fork해서 생성하고 자식이 exit code -1을 리턴하는걸 wait해서 블락되어있다.

자식은 actual 주소부터 한페이지만큼 다 0으로 초기화해주는데 여기서 오류가 발생해서 exit(-1)을 해준다.

그럼 부모는 wait에서 탈출해서 반환값이 -1인지 확인하고, 매핑된 영역과 sample데이터가 같은지 확인해서, 같으면 “same data라고 출력”

 

spt_copy할 때, page 타입이 VM_FILE인 경우 duplicate 제외하기

→ 그래도 memcmp에서 exit 안됨

→ page fault handler()에서 spt_find 했을 때 일단 못찾았기 때문.

page == NULL이 되면서 스택 키워야 하는지 여부 따지는 코드로 가는데, 이전 코드에는 addr < USER_STACK이 없어서 추가해주니까 return false로 가면서 exit(-1)됨

FAIL tests/vm/mmap-off

FAIL tests/vm/mmap-bad-off

FAIL tests/vm/mmap-kernel

FAIL tests/vm/swap-file

FAIL tests/vm/swap-anon

FAIL tests/vm/swap-iter

FAIL tests/vm/swap-fork

FAIL tests/vm/cow/cow-simple

 

10/19 목

일단, mmap 구현 이상하게 했음.

수정 사항

1. process.c/lazy_load_segment

1. mmap의 인자로 들어온 length만큼 매핑영역 확보
2. destroy할 때, pte clear하고, 프레임에 매핑된 물리메모리 할당 해제
3. destroy시 파일맵드된 것들은 페이지 다 파괴된 후에 닫히도록 했음.

 

10/20 금

일정

• 씻고 밥먹고, 파일 닫는거 수정 + 스왑디스크 file 끝내고 anon 하기
• 비트맵 익히기

일단, file_backed 부터 하기

• swap out : 더티비트 체크해서 파일에 쓰고 더티비트 0 만들고 해당 물리메모리 영역 0으로 초기화 후 페이지테이블 매핑 삭제
• swap in: file backed page에 대해 swap in이 호출되는 경우: 해당 페이지 영역에 접근할 시 매핑 안되어 있어서 page_fault 발생 → page fault handler() 호출 →
• 근데, evict되는 페이지가 anon인 경우, anon에 대한 swap out을 구현해야 함 → 스왑 디스크 구현해야 함.

따라서, swap dist부터 구현

디스크에 쓰기 코드 참고

• disk read
• disk write

비트맵 참고

1. 비트맵 생성(bitmap_create_in_buf())
2. 비트맵 초기화(bitmap_set_all(bitmap, true))

1. 페이지 개수를 구하기(pgcnt)
2. round up 해서 비트맵 페이지 개수 구하기?(bm_pages)
3. 스왑테이블(스왑디스크) 접근용 락 초기화
4. 스왑테이블 내 비트맵 생성(bitmap_create_in_buf(페이지 개수, 비트맵 베이스?, 비트맵 페이지 개수)
5. 스왑테이블의 베이스 설정
6. 비트맵 0으로 초기화
7. bm_base에 bmpages 더하기?

bit_cnt: 비트맵에서 비트의 개수

elem_type = unsigned long. → unsigned long* bits;

bits → unsigned long을 요소로 가지는 배열로 이해

bit 인덱스를 인자로 집어넣으면, 이 bit 인덱스가 몇번째 elem에 속하는지를 구해주는 함수

bitmap 생성: bitmap_create()

bitmap 마킹: bitmap_set(비트맵, 비트 인덱스, 체크여부(true=체크(사용중), false=미사용)

bitmap_test(비트맵, 비트 인덱스): 해당 비트 인덱스가 사용중인지 확인함

• 해당 bit에 대해 bit_mask를 만든 후, bit가 속한 bits 배열 내의 elem을 찾아서 둘 간에 & 연산결과 1이면 true, 0이면 false 반환.
• true면 지금 사용중
• false면 지금 미사용중

bitmap_contains(비트맵, 출발 비트인덱스, 비트개수, 미사용중인거 찾으려면 false)

• 출발 비트인덱스 ~ 끝 비트인덱스 영역에서 bitmap_test() 수행한 후, 해당 영역이 모두 미사용중이면 false 리턴

bitmap_scan(비트맵, 시작인덱스, 필요 비트개수, 미사용중인거 찾으려면 false)

• 전체 비트맵 구간에서, 필요 비트개수를 채울 수 있는 연속된 비트공간을 찾으려는 함수
• for문 돌면서 bitmap_contains()를 계속 호출하면서 만족하는 영역을 발견한 경우 해당 영역의 시작 비트인덱스를 반환함

bitmap_scan_and_flip(비트맵, 시작 비트인덱스, 비트 개수, 미사용중인거 찾으려면 false)

• bitmap_scan() 해서 조건을 만족하는 비트 인덱스 찾은 후, bitmap_set_multiple() 해주는데, 이때는 true를 인자로 넣어서 모두 사용중임을 체크함

이제 할것: 하나의 비트가 디스크의 뭐에 매핑되는지 디스크 파일 보기

스왑디스크의 섹터 수 = 20160개

anon_swap_in() 호출 과정

1. anon타입 페이지가 swap out된다.
   • swap out 되면서 anon_page의 bit_cnt에 시작 비트 인덱스를 넣는다.
2. 이후, 다시 해당 페이지에 접근할 시 page_fault_handler() 호출되어

anon_swap_in(page, kva)

• for문 돌면서 disk_read(디스크, 섹터넘버, 버퍼주소)
  • 여기서 버퍼주소에 유저의 가상페이지 주소를 넣을지(page,va), 물리메모리와 매핑된 커널쪽 주소를 넣을지(kva)
    • lazy_load_segment()에서 file_read()할 때 인자에 kpage를 넣어주는데 이게 kva다.
    • 그리고 이 kva가 이런식으로 디스크에서 읽어서 buffer(kva)에 담기기 때문에, kva가 맞다.

 

frame evict 테스트시 500번째에서 터짐 → 확인해보니 file_backed 타입 페이지 evict할 때 였음.

→ anon에는 page.frame.page = NULL, page.frame = NULL 해줬는데 file에서는 안해줘서 해줌

비트맵 만들 때 bitmap_create()의 인자에 비트의 개수를 넣어야 하는데, 나는 만들 수 있는페이지의 개수를 넣어줬던 실수 → disk_size(swap_disk)를 인자에 넣어줬음.

 

비트맵 구조체 구조

 

엘리먼트 인덱스 구하는 함수

 

테스트 실행시 표시되는 디스크 파티션별 섹터 개수

 

10/21 토

13:11 시작

할일

• page merge par, stk, mm 하기 → 완료
• cow 구현

read only 페이지

• 공유해서 사용 가능. write작업 하려고 할 시 page_fault → exit. 추가 작업 불필요?

read and write 페이지

• 공유해서 사용 가능. write하려고 할 시 물리메모리 공간 확보 → 부모페이지 정보를 복붙 → 쓰기작업 수행
• 0x3 비트를 PTE_WP 비트로 삼고, 맨 처음에 부모가 물리페이지 설정할 때 추가해주기

10/22 일

할일

• cow 마무리

anon타입 페이지 스왑 아웃 → 다시 필요해서 page fault → hander → anon 스왑 인 → 스왑디스크에서 꺼내 옴.

현재, 프레임에는 share_cnt 필드가 있고, 프레임을 공유하고 있는 페이지의 개수를 표현한다.