A. Frame Table (vm.c)

Frame Table 리스트 구현

• Frame Table은 연결리스트 형태로 구현 가능
  • struct frame의 연결 리스트
  • 그 뜻은 struct frame에 struct list_elem 필드를 추가해야 함
• struct frame에 필드 추가

// include/vm/vm.h
/* The representation of "frame" */
// kva : 커널 가상 메모리
struct frame {
    // 이미 있는 필드
    void *kva;              // 커널가상 주소
    struct page *page;      // 페이지 구조체
    // 추가할 필드
    struct list_elem (...); // frame table(리스트) 삽입용도
    struct *thread (...);	// 프레임을 참조하는 쓰레드
};

• 전역 변수로 Frame Table을 선언해 주어야 함
• vm.c에서 선언
• vm_init에서 list_init으로 초기화

// vm/vm.c
#include "vm/vm.h"
struct list frame_table;

void vm_init(void) {
    vm_anon_init();
    vm_file_init();
#ifdef EFILESYS /* For project 4 */
    pagecache_init();
#endif
    register_inspect_intr();
    /* DO NOT MODIFY UPPER LINES. */
    /* TODO: Your code goes here. */
    list_init(&frame_table);
}

• Clock Algorithm은 구현하기 쉬운 Page Replacement Algorithm의 일종.

Frame Table에 삽입

• vm_get_frame에서 struct frame을 만들어 줄 때마다, 프레임 테이블에 삽입해야 함.
• 기존엔 palloc_get_page로 프레임을 찾지 못했을 때 panic을 때렸는데, 이제 frame을 evict한 뒤 다시 palloc을 재시도하게끔 코드 변경.
• vm_evict_frame은 내쫓을 프레임을 정하고 swap out으로 스왑영역(anon) OR 파일(file-backed)에 저장. 이후 해당 프레임 반환.
• palloc_free_page로 해당 frame의 메모리 할당 해제.

static struct frame *vm_get_frame(void) {
    struct frame *frame = NULL;

    // 새로운 페이지 할당  -> palloc 은 kva 반환
    void * new_page = palloc_get_page(PAL_USER);

    // (A) 이걸 panic에서 vm_evict_frame으로 변경하고, palloc 재시도로 변경.
    if(new_page == NULL){
        //vm_evict_frame...
        //반환한 frame을, palloc_free_page로 메모리 할당해제...
    }

    // 프레임 구조체 할당
    frame = calloc(1,sizeof(struct frame));


    if(frame == NULL){
        // 이쪽은 프레임을 찾는 함수가 아니니, 계속 panic 처리해도 될듯.
        PANIC("to do\n");
    }

    list_push_back(&frame_table, &frame->elem); // (B) 이걸 변경

    // frame 구조체 멤버 변수 초기화
    // 실제 물리 메모리 page 할당
    frame->page = NULL;
    // 물리 메모리 주소 -> 가상 주소로 변환
    frame->kva = new_page;

    ASSERT(frame != NULL);
    ASSERT(frame->page == NULL);
    /* 실제 프레임의 Page는 매핑되기 전까지 빈 New_page를 만들기만 해두고,kva에 newpage에 대한 주소 정보를 담고있어서 나중에 매핑할 때 할당받은 newpage에 데이터를 넣는 느낌인가? */

    return frame;
}

Frame Table에서 제거 (Clock Algorithm)

• 이제 palloc이 실패할 때 단순히 에러 뜨고 핀토스 종료시키는 게 아니라, 기존 프레임 중 하나를 희생시켜야 함.
• 이론 공부를 할땐 LRU를 소개했지만, 좀 더 단순한 Clock Algorithm을 쓸 수 있음.
• Clock Algorithm은 참조 비트를 사용함. 대충 access된 경우 1, access 안된경우 0의 값을 가짐.
  • bool pml4_is_accessed (uint64_t *pml4, const void *vpage);로 참조
  • bool pml4_set_accessed (uint64_t *pml4, const void *vpage, bool accessed);로 값 변경
  • 커널 가상 주소가 아닌, 사용자 가상 주소를 vpage에 입력할 것. 즉 struct frame의 kva가 아니라, struct frame에 연결된 page의 va를 사용해야 한다. 왜냐하면 이쪽만 accessed 비트가 업데이트가 되거든.
• frame table의 모든 frame을 순회 (맨 끝까지 도달하면, 맨 앞으로 돌아감)
  • frame 대응 PTE의 참조 비트가 0인 경우, 1로 변경하고 다음 비트로 넘어간다.
  • 1인 경우, 해당 비트를 희생시키기로 결정하고 반복문 종료한다.

// vm/vm.c
/* Get the struct frame, that will be evicted. */
static struct frame *vm_get_victim(void) {
    struct frame *victim = NULL;
    /* TODO: The policy for eviction is up to you. */
    // 앞선 clock algorithm 이용해, frame table 순회하고, 희생시킬 프레임을 반환한다.
    return victim;
}

• 앞선 clock algorithm을 vm_get_victim에서 구현.

/* Evict one page and return the corresponding frame.
 * Return NULL on error.*/
static struct frame *vm_evict_frame(void) {
    struct frame *victim UNUSED = vm_get_victim();
    /* TODO: swap out the victim and return the evicted frame. */

    // swap_out(victim -> page) 호출
    // page와 frame 간 매핑을 page table에서 없애기

    return NULL;
}

• swap out은 페이지의 유형 (anon vs file-backed)에 따라 다름. (e.g., anon_swap_in)
• 유형에 따라 알맞은 함수 실행시키는 swap_out(page) 호출할 것. page에는 struct page *가 들어가는데, victim의 page 필드 확인하면 됨.
• 이후 물리프레임 victim과 가상페이지의 매핑을, 페이지 테이블에서 제거해야 함
  • void pml4_clear_page (uint64_t pml4, void upage);
  • pml4는 victim에서 현재 쓰레드를 가리키는 필드 확인하고, 거기서 가져오면 됨.
  • upage는 victim이 가리키는 page의 va...

B. Disk / Swap Table (anon.c)

디스크 불러오기

• vm_anon_init에서 디스크 구조체 static struct disk를 초기화해야 함.

// vm/anon.c
static struct disk *swap_disk;  // swap disk, global variable

/* Initialize the data for anonymous pages */
void vm_anon_init(void) {
    /* TODO: Set up the swap_disk. */
    swap_disk = NULL;
}

• 디스크는 devices/disk.c의 disk_get으로 초기화 가능. 우린 스왑 영역을 위한 디스크가 필요하니, DEV_NO=1, CHAN_NO=1로 해주면 될듯.

// devices/disk.c
/* Returns the disk numbered DEV_NO--either 0 or 1 for master or
   slave, respectively--within the channel numbered CHAN_NO.

   Pintos uses disks this way:
0:0 - boot loader, command line args, and operating system kernel
0:1 - file system
1:0 - scratch
1:1 - swap
*/
struct disk *disk_get(int chan_no, int dev_no) {
    // 생략
}

// vm/anon.c
void vm_anon_init(void) {
    swap_disk = disk_get(1, 1);
}

스왑 테이블 만들기

• PPT에선 비트맵을 통해 구현하는 것을 추천
• 디스크의 스왑 영역(=페이지 크기와 동일한 4096바이트)마다 비트 존재
  • 0: 현재 비어 있음
  • 1: 현재 사용 중
• 비트맵은 lib/kernel/bitmap.c의 bitmap_create로 생성 가능

/* Initializes B to be a bitmap of BIT_CNT bits
   and sets all of its bits to false.
   Returns true if success, false if memory allocation
   failed. */
struct bitmap *bitmap_create(size_t bit_cnt){
    // 생략
}

• bit_cnt는 스왑 영역의 개수. 스왑 영역의 개수는 디스크 크기 / 4096바이트
  • 디스크 크기는 disk_sector_t disk_size(struct disk *d)로 확인
  • 이게 섹터 수인데, 한 섹터는 512바이트임

// include/devices/disk.h
/* Size of a disk sector in bytes. */
#define DISK_SECTOR_SIZE 512

/* Index of a disk sector within a disk.
 * Good enough for disks up to 2 TB. */
typedef uint32_t disk_sector_t;

• 즉 bit_cnt에는 디스크 크기 / 4096 = disk_size(...) * 512 / 4096 = disk_size(...) / 8을 넣어주면 될 듯.

// vm/anon.c
static struct disk *swap_disk;  // swap disk, global variable
static struct bitmap *swap_table; // 새롭게 선언

/* Initialize the data for anonymous pages */
void vm_anon_init(void) {
    /* TODO: Set up the swap_disk. */
    swap_disk = disk_get(1, 1);
    swap_table = bitmap_create(disk_size(swap_disk) / 8);
}

Anon Page의 swap_in, swap_out (anon.c)

struct anon_page

• 우선 struct page 내 struct anon_page에, swap out된 페이지일 경우 몇 번째 swap slot에 위치해 있는지 저장할 필드를 만들어 두어야 함.
  • 그래야 나중에 다시 swap_in할 때 불러올 slot을 찾을 수 있음

// vm/anon.h
struct anon_page {
    disk_sector_t swap_slot;
};

• swap out되기 전까진 값이 있을 리가 없으므로, anon_initializer에서 별도의 값 설정을 하진 않아도 됨.
• 정 필요하다 싶음 -1 같은 초기값을 줘도 되긴 할듯.

anon_destroy

/* 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;
}

• 할 게 있나?

anon_swap_in

• 어떤 페이지를 swap in할지는 이미 정해 놨으니, 디스크에서 읽기만 하면 된다.

/* 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된 anonymous page가 swap in되는 경우 anon_swap_in이 호출됨.

  • 어디서? vm_do_claim_page의 swap_in 함수에서.
  • 한번도 로드되지 않은 경우, anon page로 아직 전직되지 않은 uninitialized page니 anon_swap_in이 아니라 uninit_initialize가 호출됨에 유의.

void disk_read(struct disk *d, disk_sector_t sec_no, void *buffer)

• (1) anon_page -> swap_slot으로 swap할 첫 sector 번호 확인
• (2) 디스크에서 읽기 8회 반복
  • 섹터 단위로 읽기 수행하는데, 섹터 8개가 스왑슬롯 1개니까 8회 반복하게 됨
  • sec_no: anon_page -> swap_slot * 8부터 시작해, 반복마다 1씩 증가.
    • *8 해주는 이유? 섹터 8개 == swap_slot 1개
  • buffer: 매개변수 kva부터 시작해, 반복마다 512씩 증가
• (2) 이후 swap table의 해당 비트를 1(사용중) -> 0(비었음)으로 변경
  • bitmap_set(struct bitmap *b, size_t idx, bool value)
  • idx는 swap_slot.

anon_swap_out

• 어떤 페이지를 swap out할진 이미 정해 놨으니, 디스크에 쓰기만 하면 된다.

/* 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;
}

void disk_write(struct disk *d, disk_sector_t sec_no, const void *buffer)

• (1) swap table에서 값이 0(비었음)인 첫 비트 찾기
  • size_t bitmap_scan(const struct bitmap *b, size_t start, size_t cnt, bool value). 값이 value인 첫 비트의 인덱스를 반환. start는 0, size_t는 1로 두면 됩니다.
• (2) anon_page -> swap_slot에 해당 비트 인덱스 저장
• (3) 디스크에 쓰기 -> 8회 반복
  • sec_no: anon_page -> swap_slot * 8부터 시작해, 반복마다 1씩 증가
    • *8 해주는 이유? 섹터 8개 == swap_slot 1개
  • buffer: page -> frame -> kva...하면 되지 않을려나?
• (4) swap table의 비트를 0(비었음) -> 1(사용중)으로 변경
  • bitmap_set(struct bitmap *b, size_t idx, bool value)
  • idx는 swap_slot.

C. File-backed Page의 swap_in, swap_out (file.c)

struct file_page

• swap_in, swap_out 시 파일을 읽고 쓰는데 필요한 함수를 필드로 저장. 얘네 4개가 필요한데 이젠 익숙하실 것.

// include/vm/file.h
struct file_page{
    struct file *file;      // 파일 주소
    size_t ofs;             // offset
    size_t page_read_bytes;   // 실제 데이터가 저장된 바이트 수
    size_t page_zero_bytes; // zero padding된 바이트 수
}

file_initializer

/* Initialize the file backed page */
bool file_backed_initializer(struct page *page, enum vm_type type, void *kva) {
    // page -> uninit -> aux를 별도 변수로 저장.

    /* Set up the handler */
    page->operations = &file_ops;

    struct file_page *file_page = &page->file;

    // file_page의 각 필드에, 저장해둔 값 복사.
    return true;
}

• 이 함수가 실행될 시점엔 아직 page는 uninitialized page임.
• file_backed page로 전직하기 전에, page -> uninit -> aux를 별도의 변수에 저장
  • 얘도 구조체였죠. 필드로 file, ofs, page_read_bytes, page_zero_bytes가 있었죠
• 이후 file_backed page로 전직 후, 각 필드에 값을 복사.

file_backed_destroy

/* 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;
}

• 뭘 해줘야 할지 모르겄다. 메모리 할당 해제할 만한 게 있나?

file_backed_swap_in

/* 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;
}

• file_read_at 함수를 이용.
• file_page -> file에 저장된 파일을 ofs부터 page_read_bytes만큼 읽고, page_zero_bytes만큼 memset.
• lazy_load_segment, mmap 구현했을 때와 비슷한 흐름으로 하면 될 듯함.

file_backed_swap_out

/* 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;
}

• file_write_at 함수를 이용.
• file_page -> file의 ofs 위치부터 page_read_bytes만큼 작성.
• munmap 구현했을 때와 비슷한 흐름으로 하면 될 듯함.