[PintOS] Virtual Memory - Mid Check (Project 3, WIL)

2024.05.19 - [🧭 KAIST JUNGLE/⭐ Pintos] - [PintOS] Virtual Memory - 들어가기(Project 3, TIL)

[PintOS] Virtual Memory - 들어가기(Project 3, TIL)

---

진행 상황

✅ Memory Management

✅ Anonymous Page

✅ Stack Growth

❎ Memory Mapped Files

❎ Swap In/Out

 

Project3의 Virtual Memory를 모두 구현한 후의 동작 mechanism

Reference to 물리 메모리 할당(좌), Pintos에서 reference가 발생하는 과정(우)

Project2까지 구현된 현재 Pintos의 모습은 어떨까?

구현 전, 후 이미지를 비교해 봤을 때 구현해야 할 것이 직접적으로 보인다. Page table의 확장과 hash, bucket의 추가이다.

Implement Supplemental Page Table

구현

현재 Pintos에서 VA를 PA로 매핑하는 것을 관리하는 pml4로는 부족하다. Page fault가 발생했을 때 처리할 page에 대한 보충적인 설명이 필요하기에 Supplemental Page Table(SPT)을 추가해주어야 한다. Pintos Instruction을 참고하면, SPT 설계 후 이를 토대로 함수 세 개를 구현해야 한다.

void supplemental_page_table_init (struct supplemental_page_table *spt);
struct page *spt_find_page (struct supplemental_page_table *spt, void *va);
bool spt_insert_page (struct supplemental_page_table *spt, struct page *page);

• supplemental_page_table_init : spt 구성 요소를 초기화하는 함수로 initd(), __do_fork() 함수에서 호출됨
• *spt_find_page : 인자의 spt에서 va에 대응되는 'page 구조체'를 찾아서 반환함
• spt_insert_page : 인자로의 spt에 page 구조체를 삽입함

/* Initialize new supplemental page table */
void supplemental_page_table_init(struct supplemental_page_table *spt UNUSED) {
    hash_init(spt, page_hash, page_less, NULL);
}

struct page 
*spt_find_page(struct supplemental_page_table *spt UNUSED, void *va UNUSED) {
    struct page *page = NULL;
    page = malloc(sizeof(struct page));
    struct hash_elem *hash_element;
    page->va = pg_round_down(va);  // 페이지를 찾을때는 rounddown  -> up은 할당크기 맞출때
    hash_element = hash_find(spt, &page->hash_elem);
    free(page);  // 할당된 메모리 해제
    if (hash_element) {
        return hash_entry(hash_element, struct page, hash_elem);  // hash_entry로 hash_elem을 page로 변환
    }
    return NULL;
}

/* Insert PAGE into spt with validation. */
bool spt_insert_page(struct supplemental_page_table *spt UNUSED,
                     struct page *page UNUSED) {
    int succ = false;
    // REVIEW INSERT_PAGE
    if (hash_insert(&spt->hash_page, &page->hash_elem) == NULL) {  // 잘 추가되었으면 NULL반환
        succ = true;
    }
    return succ;
}

함수 내의 hash가 뜬금없어 보일 수 있지만, 위의 구현 후 메커니즘 설명 이미지를 자세히 보면 hash를 통해서 vm_entry까지 관리되는 것을 알 수 있다. 더불어 Pintos에서는 chaining hash table을 제공한다(lib/kernel/hash.* 참고). 여담으로 리눅스에서는 Red-Black tree 구조로 vm_entry를 관리한다.

Frame Management

이제 Physical Memory에도 Frame이라는 단위로 구분되어 관리된다. frame 적용을 위해 struct frame에 kva(Kernel Virtual Address), page 구조체를 담을 수 있도록 구현한다. Instruction에는 없지만 frame도 page와 마찬가지 구조로 관리하기 위해 frame_elem도 추가할 필요가 있다.

/* The representation of "frame" */
struct frame {
    void *kva;
    struct page *page;
    struct list_elem *frame_elem;
};

frame 관련한 구현해야 하는 함수

static struct frame *vm_get_frame (void);
bool vm_do_claim_page (struct page *page);
bool vm_claim_page (void *va);

위 세 함수(사실 두 개에 가깝다 ㅎ)를 구현할 때 우리 조는 vm_do_claim_page()에서 에러가 발생했다.

static bool
vm_do_claim_page(struct page *page) {  // va 페이지를만들고 프레임에 할당한 페이지
    struct frame *frame = vm_get_frame();

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

    struct thread *current = thread_current();
    // bool writable = is_writable(current->pml4); <- 기존
    // pml4_set_page(current->pml4, page->va, frame->kva, writable); <- 기존, 아래가 수정
    pml4_set_page(current->pml4, page->va, frame->kva, page->writable);

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

주석 처리된 기존 코드를 보면, is_writable() 함수를 사용해서 현재 thread의 pml4가 가리키는 PA의 writable 유무를 확인해 준다. 얼핏 보면 합당한 것처럼 보이지만 이는 말도 안 되는 것이다(ㅜㅜ). 함수명대로 '요청한 페이지'의 write 여부를 봐야 하는데 현재 thread 정보를 보기 때문이다. 지금 생각해 보면 매우 쉬운 오답인데, 에러를 유발한 코드에서 매우 멀리 떨어진 데서 KERNEL PANIC이 발생했기에 디버깅에 어려움이 컸다.

수정한 코드를 보면 할당하고자 하는 page의 writable field로 write 여부를 확인한다. 함수명과도 정확히 일치하는 것을 알 수 있다.

수정 전, 후 writable 여부(1 or 0) 비교

절대 의심해, race condition 😈

make check 후 결과를 볼 때마다 PASS/FAIL이 오락가락하는 테스트 케이스가 있었다(우리 팀의 경우 syn-read....). 오락가락할 때 가장 쉽게 의심할 수 있는 게 race condition이다. 아래 코드와 같이 file_write(file ,..., size) 함수가 실행될 때, 두 개의 thread에서 동시에 같은 파일에 write를 시도할 경우를 대비해 filesys_lock을 사용한다.

이렇게 lock을 건다고 한들 lock을 걸기 전 다른 코드에서 write 부분을 잘못 수정한다면, 이렇게 lock을 걸어줘도 의미가 없다(!..). 그래서 race condition 잡기가 엄청 어려웠다.

int write(int fd, const void *buffer, unsigned size)
{
	check_address(buffer);
	int bytes_write = 0;
	if (fd == STDOUT_FILENO)
	{
		putbuf(buffer, size);
		bytes_write = size;
	}
	else
	{
		if (fd < 2)
			return -1;
		struct file *file = process_get_file(fd);
		if (file == NULL)
			return -1;
		lock_acquire(&filesys_lock); // race condition 방지
		bytes_write = file_write(file, buffer, size);
		lock_release(&filesys_lock); // race condition 방지
	}
	return bytes_write;
}

이 외에도 무수히 많은 race condition 발생 가능 위치에 lock_acquire(), lock_release()를 해주었다.

Pintos demand paging 일부 구현 과정

Pintos 상의 함수 흐름은 아래의 Proj3 중간발표(WIL) 자료를 통해 확인할 수 있다.