[DevLog][PintOS] PRJ3 Virtual Memory/Memory Mapped Files to Copy-on-write

04) Memory Mapped Files

시스템 콜 mmap과 munmap을 구현한다. 현재까지는 모든 페이지가 anonymous, 즉 스택 페이지였지만 mmap을 통해 파일과 매핑된 페이지는 file-backed page가 된다. 따라서 매핑이 해제될 때 변경사항을 파일에 다시 기록해주어야 한다. 디스크에 파일을 쓰는 작업은 RAM대비 속도가 매우 느리기 때문에, 변경사항이 있는 페이지만 디스크에 기록해줄 수 있도록 한다. 페이지가 변경될 경우, mmu는 알아서 pml4 테이블에 dirty bit를 세팅해준다.

/* Write back a single page to file. Called when unmap. */
static bool file_write_back(struct page *page, struct page *head) {
  ASSERT(page->operations->type == VM_FILE)
  struct thread *curr = thread_current();

  if (!pml4_is_dirty(curr->pml4, page->va)) {
    /* If page is present and
     * not dirty, return. */
    return true;
  }

  /* Write back to file. */
  if (!do_file_io(page, head, filesys_write)) {
    printf("Fail to write back file.\n");
    return false;
  }
  return true;
}

// filesys.c
off_t filesys_write(struct file *file, const void *buf, off_t size) {
  int bytes;
  lock_acquire(&filesys_lock);
  bytes = file_write(file, buf, size);
  lock_release(&filesys_lock);
  return bytes;
}

위 함수는 하나의 페이지가 변경사항이 있는지를 확인하고, 있을 경우 파일에 다시 쓰는 작업을 수행한다. 핀토스의 프로젝트 3까지는 파일시스템에 접근할 때 lock을 걸어주는 것이 좋으므로, 별도로 filesys_write이라는 file_write wrapper function을 구현하여 사용했다. do_file_io는 page에 대해 해당 페이지의 head-page*를 찾아서 세 번째 인자로 전달된 함수를 수행한다. disk에 접근하므로 여기서도 락을 한번 더 건다.

/* Calculate page offset in mapped area
 * and execute func handed by argument. */
static bool do_file_io(struct page *page, struct page *head, file_io func) {
  struct file *file = head->file.file;
  off_t offset = page->file.offset;
  size_t length = page->file.length;
  void *map_addr = page->file.map_addr;
  void *kva = page->frame->kva;

  ASSERT(page->frame && kva)

  /* Calculate page offset. Starts from 1. */
  off_t page_offset = (page->va - map_addr) / PGSIZE;

  /* Calculate read-write-start point. */
  off_t start = offset + page_offset * PGSIZE;

  /* Calculate read-write-bytes. */
  filesys_seek(file, start);

  /*
     offset                                   len  page-aligned
       +----------+----------+----------+------+---+
       |          |          |          |      |   |
       |          |          |          |      |   |
       |   page   |   page   |   page   |   page   |
       |          |          |          |      |   |
       |          |          |          |      |   |
       +----------+----------+----------+------+---+

       +----------+-------+
       |                  |
       |       file       |
       |                  |
       +----------+-------+

       Take min(PGSIZE, (off+len)-rw_start, file_left) as rw_bytes of this page.
       Page 0 takes PGSIZE,
       Page 1 takes file_left, and so on.
  */

  off_t file_left = filesys_length(file) - file->pos;
  size_t bytes = (offset + length) - start;
  bytes = bytes < PGSIZE ? bytes : PGSIZE;
  bytes = bytes < file_left ? bytes : file_left;

  /* Do func. */
  if (func(file, kva, bytes) != (int)bytes) {
    return false;
  }
  return true;
}

filesys_write 또는 filesys_read의 반환값인 byte를 기준으로 의도하는 만큼 파일 읽기/쓰기가 잘 수행되었는지 확인하기 위해 정확한 바이트수를 계산해주었다. 핀토스 프로젝트 3까지는 파일이 grow 할 수 없기 때문에 파일 길이, 페이지 사이즈, length 중에서 가장 작은 값을 택해 io function에 전달한다.

mmap을 구현하면서 가장 까다로웠던 점 중 하나는 여러 페이지에 걸쳐 매핑된 파일을 다루는 일이었다. 이로 인해 매핑이 시작되는 페이지인 head-page와 이에 딸린 페이지들인 sub-pages 개념이 생겼다. 구현 방향은 다음과 같다.

1. file-backed page가 매핑이 해제되는 경우, 해당 페이지의 head-page를 spt에서 찾는다.
2. head-page에서 매핑된 파일 정보를 읽어온다.
3. 파일에 writeback을 수행한 다음 페이지를 swap-out하거나 destroy한다.

이렇게 구현한 이유는, 하나의 매핑에 속한 여러 페이지들이 모두 파일의 사본 (같은 inode지만 file pointer가 다른)을 가지지 않게 하면서도, 하나의 file pointer에 대해 filesys_close를 두 번 이상 호출하는 것을 막기 위해서이다. sub-pages는 file pointer를 갖지 않고, head-page의 가상주소 정보를 갖는다.

// 페이지 구조체 내 파일 페이지
struct file_page {
  size_t slot;
  off_t offset;
  size_t length;
  void *map_addr;
  struct file *file;
};


/* Get head page of this mapping. */
static struct page *spt_get_head(struct page *page) {
  struct thread *curr = thread_current();

  /* Get file page struct. */
  struct file_page *file_page = get_file_page(page);

  if (is_file_head(page, file_page)) {
    return page;
  }
  return spt_find_page(&curr->spt, file_page->map_addr);
}

/* Hash action function which write all file-backed pages
 * back to disk if page is dirty.
 * See supplemental_page_table_kill in vm.c */
void spt_file_writeback(struct hash_elem *e, void *aux) {
  struct page *page = hash_entry(e, struct page, table_elem);
  if (page_get_type(page) != VM_FILE) return;
  if (!is_file_head(page, get_file_page(page))) return;

  /* If page is head-page of
   * file-backed pages, write back. */
  file_write_back_all(page);
}


/* Write back all file-backed pages starting from head-page. */
static void file_write_back_all(struct page *head) {
  struct thread *curr = thread_current();

  void *p = head->va;
  void *map_addr = head->va;
  struct page *page = head;

  while (page && get_file_page(page)->map_addr == map_addr) {
    if (!pg_present(page)) {
      /* Clearing uninit page will be handled by uninit_destroy.
       * If swap-out page, no need to write back.
       * Just go to next loop. */
      p += PGSIZE;
      page = spt_find_page(&curr->spt, p);
      continue;
    }

    /* Write back to file. */
    file_write_back(page, head);

    p += PGSIZE;
    page = spt_find_page(&curr->spt, p);
  }

  /* Close file. */
  filesys_close(get_file_page(head)->file);
}

munmap시스템 콜이 호출될 때는 인자로 받는 가상주소가 head-page의 가상주소여야 한다는 제약이 있기 때문에 해당 주소에 대해 file_write_back_all만 호출해준 후, spt_remove_page로 페이지를 destroy해주면 된다. 다만 해시 테이블을 돌면서 spt 전체를 kill하는 경우에는 spt를 삭제하기 전에 먼저 각 file-backed page의 head-page를 골라 file_write_back_all을 한번씩 호출해야 한다. (위의 spt_file_writeback함수가 해시의 각 엔트리에 대해 수행된다.)

mmap, munmap 에서 tricky한 부분은 이정도였던 것 같다. 처음에는 destroy function 안에서 file writeback을 수행하려고 했으나 spt 테이블을 조작하면서 head-page를 찾다 보니 중간에 head가 날아가버리는 불상사가 생겼다. 따라서 writeback은 writeback대로, remove는 remove대로 수행하도록 로직을 변경했다.

/* Free the resource hold by the supplemental page table. */
void supplemental_page_table_kill(struct supplemental_page_table *spt) {
  if (!spt) return;

  /* Write back file_backed_pages first, */
  hash_apply(&spt->hash, spt_file_writeback);

  /* Destroy hash. */
  hash_destroy(&spt->hash, spt_free_page);
  return;
}

한가지 더 신경 썼던(?) 부분은 함수 포인터의 사용으로, filesys_read, filesys_write의 인터페이스가 동일하다는 점을 활용해 함수를 인자로 받아 수행하는 do_file_io 함수를 구현해 중복되는 로직을 줄일 수 있었다. 유사하게, anon page swap in/out에서 swap disk io쪽도 동일한 방식을 사용했다. 변경하는 김에 syscall 쪽도 모두 함수 포인터를 사용한 syscall table로 수정해두었다. 이런 식으로 로직을 따로 빼 두면, 일단 1. 수정하기 편하고 2. 공유 자원인 경우 lock이나 semaphore를 걸기 수월해지는 것 같다.

👀 완성된 mmap & munmap

/* Do the mmap */
void *do_mmap(void *addr, size_t length, int writable, struct file *file,
              off_t offset) {
  struct thread *curr = thread_current();

  /* If addr or offset is not page-aligned. */
  if ((uint64_t)addr % PGSIZE || offset % PGSIZE) {
    return NULL;
  }

  /* If addr is in spt. */
  for (void *p = addr; p < addr + length; p += PGSIZE) {
    if (spt_find_page(&curr->spt, p)) {
      return NULL;
    }
  }

  /* If addr in stack area. */
  if (addr + length > STACK_LIMIT && addr < USER_STACK) {
    return NULL;
  }

  /* Allocate page with lazy loading. */
  struct file *mmap_file = file_duplicate(file);
  long left = (long)length;
  int cnt = 0;

  while (left > 0) {
    /* Save infos for initializing file-backed page. */
    struct file_page *aux = calloc(1, sizeof(struct file_page));

    /* Only head page holds mmap_file address. */
    aux->file = cnt == 0 ? mmap_file : NULL; /* map file from */
    aux->offset = offset;                    /* offset, */
    aux->length = length;                    /* to length bytes. */
    aux->map_addr = addr;                    /* va where mapping starts. */

    if (!vm_alloc_page_with_initializer(VM_FILE, addr + (cnt * PGSIZE),
                                        writable, lazy_load_file, aux)) {
      return NULL;
    }

    left -= PGSIZE;
    cnt++;
  }
  return addr;
}


/* Do the munmap. Unmap can be called when
 * head or sub pages are not initialized. */
void do_munmap(void *addr) {
  struct thread *curr = thread_current();
  struct page *page = spt_find_page(&curr->spt, addr);

  /* If page is not found, return. */
  if (page == NULL) return;

  /* Virtual address must be the map_addr. */
  struct file_page *file_page = get_file_page(page);
  if (file_page->map_addr != addr) return;

  size_t length = file_page->length;

  /* Write back all pages starting from head. */
  file_write_back_all(page);

  /* Remove head-page and all sub-pages from spt and pml4. */
  for (void *p = addr; p < addr + length; p += PGSIZE) {
    page = spt_find_page(&curr->spt, p);
    spt_remove_page(&curr->spt, page);
  }
}


/* Initialize file-backed frame. */
static bool lazy_load_file(struct page *page, void *aux) {
  ASSERT(page->operations->type == VM_FILE)
  ASSERT(page->frame)

  /* Get head-page. */
  struct thread *curr = thread_current();
  struct page *head = spt_get_head(page);
  ASSERT(head != NULL)

  /* Read file to page. */
  bool succ;
  lock_acquire(&load_lock);
  succ = do_file_io(page, head, file_read);
  lock_release(&load_lock);

  return succ;
}

05) Swap in/out

유저 풀에서 프레임을 할당받아오는 현재의 vm_get_frame함수는 메모리 공간이 바닥난 경우 프레임을 반환하지 못한다는 문제가 있다. 프로세스는 컴퓨터를 추상화하므로, 메모리 역시 독립적인 가상주소공간처럼 사용할 수 있어야 한다. 메모리가 웬만해선 바닥나지 못하도록 swap disk를 사용해보자.

• 메모리상의 프레임을 스왑 디스크로 내리는 것을 swap-out이라고 한다.
• 스왑 디스크에 있는 프레임을 다시 메모리로 읽어 오는 것을 swap-in이라고 한다.

static struct frame *vm_get_frame(void) {
  struct frame *frame = NULL;
  frame = calloc(1, sizeof(struct frame));
  if (frame == NULL) {
    printf("Frame allocation failed.\n");
    return NULL;
  }

  /* Get anonymous frame. */
  frame->kva = palloc_get_page(PAL_USER | PAL_ZERO);
  if (frame->kva == NULL) {
    free(frame);
    /* If out of memory,
     * evict frame from frame table.*/
    frame = vm_evict_frame();
  }

  /* Init page list, push into frame table. */
  list_init(&frame->pages);
  list_push_back(&frame_table, &frame->elem);

  ASSERT(frame != NULL);
  ASSERT(list_empty(&frame->pages));
  return frame;
}

수정된 vm_get_frame함수는 palloc_get_page(PAL_USER | PAL_ZERO);가 실패할 경우, 프레임 테이블에서 프레임을 하나 swap-out하고 가져온다. 즉 남이 쓰던 중고인 것이다.. 따라서 evict_frame을 할 때 다음과 같이 프레임을 깨끗이 0으로 밀어줘야 한다.

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

  ASSERT(!list_empty(&victim->pages));

  struct list_elem *front = list_front(&victim->pages);
  struct page *page = list_entry(front, struct page, frame_elem);

  /* Remove all pages from frame and
   * push into swap table. */
  if (swap_out(page)) {
    /* After, initialize victim. */
    ASSERT(list_empty(&victim->pages));
    memset(victim->kva, 0, PGSIZE); // 🔥 0으로 리셋
    return victim;
  }
  return NULL;
}

이를 구현하기 위해서는 각 프로세스들에 할당된 프레임의 주소를 엮어 놓은 전역적인 frame table이 필요하다. 프레임 테이블의 자료구조는 스왑 아웃할 프레임을 고르는 방법, 즉 evict policy에 의해 결정될 수 있다. 우리 조는 단순 FIFO로 한번, 그리고 원형 큐를 활용한 Clock Algorithm으로 한번 구현해보았다.

// 전역변수
static struct list_elem *clock_hand;
static struct list frame_table;
static struct lock frame_lock;

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. */

  /* Used when each process access frame table. */ 
  lock_init(&frame_lock);

  /* Create frame table as CLL. */
  list_init(&frame_table);
  clock_hand = &frame_table.head;
  frame_table.head.prev = &frame_table.tail;
  frame_table.tail.next = &frame_table.head;
}

핀토스의 <list.h>라이브러리에서 제공되는 리스트는 기본적으로 이중 연결 리스트이기 때문에 head와 tail만 연결해주면 원형 큐로 사용할 수 있다. Clock 알고리즘의 기본 아이디어는 다음과 같다.

1. Clock hand가 원형 큐를 돌면서 프레임과 연결된 페이지의 접근 비트 access bit를 검사한다.
2. 접근 비트가 1로 설정된 경우, 0으로 설정하고 다음으로 넘어간다.
3. 접근 비트가 0으로 설정된 경우, 해당 프레임을 victim으로 선정하고 즉시 반환한다.

Clock은 LRU (Least Recently Used)를 근사한 방식으로 여겨지는데, Clock hand가 리스트를 한 바퀴 도는 동안 접근 비트가 0인, 즉 접근되지 않은 페이지를 '최근에 사용되지 않은' 것으로 간주한다는 점에서 그렇다. 만약 접근 비트가 1인 경우 0으로 세팅하고 다음으로 넘어가므로 Second-chance를 주는 알고리즘이라고 볼 수도 있다. 이는 가장 최근에 참조되었던 페이지가 앞으로도 가장 빨리 다시 참조될 가능성이 높다는 참조지역성 개념에 기반한다. (반복문 같은 경우를 생각해보자.)

Test에서는 보통 여러 페이지를 순차적으로 단 한번씩만 접근하는 경우가 많아 FIFO와 Clock의 성능이 유의미한 차이를 보이지 않았던 것 같지만, 매핑된 일부 페이지만 반복적으로 접근하거나 랜덤한 순서로 접근할 경우 Clock의 성능이 높아지는 모습을 볼 수 있었다.

/* Get the struct frame, that will be evicted. */
static struct frame *vm_get_victim(void) {
  struct list_elem *head = &frame_table.head;
  struct list_elem *tail = &frame_table.tail;

  if (list_empty(&frame_table)) {
    PANIC("No entry in frame table.");
  }

  lock_acquire(&frame_lock);

  struct list_elem *curr = clock_hand;
  size_t frame_access = SIZE_MAX;
  size_t least_access = SIZE_MAX;

  struct frame *frame = NULL;
  struct frame *victim = NULL;

  /* Clock algorithm with CLL */
  while (frame_access != 0) {
    if (curr == head || curr == tail) {
      curr = list_next(curr);
      continue;
    }

    frame = list_entry(curr, struct frame, elem);
    frame_access = get_access_pages(frame);
    clear_access_pages(frame);

    if (frame_access < least_access) {
      least_access = frame_access;
      victim = frame;
    }

    curr = list_next(curr);
  }

  clock_hand = curr;
  list_remove(&victim->elem);

  lock_release(&frame_lock);
  return victim;
}

다음은 커스텀 테스트로 Clock과 FIFO를 돌린 결과이다. Tick수와 hd1:1(swap disk) io횟수가 유의미한 차이를 보이는 것을 알 수 있다.

👀 그러면 FIFO가 Clock보다 항상 나쁜 건 아니네?

만약 운영체제가 프로그램의 메모리 접근 패턴을 미리 알고 있다면 이에 최적화된 교체 알고리즘을 택할 수 있을 것이다. 접근 패턴이 반복적이지 않고 순차적이라면, clock에 필요한 여러 루틴들 (pml4에서 접근 비트 읽어오기, 리스트 순회하기..) 은 오버헤드로 남게 된다. 리눅스에서 사용되는 방법이라고 해서 clock이 항상 빠른 게 아닌지 생각했었는데, 막상 테스트를 돌려보고 결과를 관찰하다보니 메모리가 어떤 식으로 접근되는지에 따라 각 교체 정책이 유리하거나 불리할 때가 있는 것 같다. 만약 프로그램의 접근 패턴을 예측할 수 없거나, FIFO 대비 복잡한 Clock의 루틴이 FIFO의 단점을 커버할 경우, Clock 알고리즘을 사용할 수 있겠다.

// CLOCK.
Executing 'swap-iter':
(swap-iter) begin
(swap-iter) open "large.txt"
(swap-iter) mmap "large.txt"
(swap-iter) end
swap-iter: exit(0)
Execution of 'swap-iter' complete.
Timer: 9237 ticks
Thread: 30 idle ticks, 216 kernel ticks, 8992 user ticks
hd0:0: 0 reads, 0 writes
hd0:1: 43158 reads, 15934 writes
hd1:0: 7948 reads, 0 writes
hd1:1: 281224 reads, 320328 writes

// FIFO
Executing 'swap-iter':
(swap-iter) begin
(swap-iter) open "large.txt"
(swap-iter) mmap "large.txt"
(swap-iter) end
swap-iter: exit(0)
Execution of 'swap-iter' complete.
Timer: 9398 ticks
Thread: 30 idle ticks, 212 kernel ticks, 9156 user ticks
hd0:0: 0 reads, 0 writes
hd0:1: 43158 reads, 15934 writes
hd1:0: 7948 reads, 0 writes
hd1:1: 281800 reads, 320904 writes

페이지 교체 정책을 선정했으면 이제 swap in/out을 구현해야 한다. anon page와 file-backed page 모두 루틴은 동일하며, 각각 스왑 디스크와 파일에 써준다는 것만 다르다. anon의 경우 스왑 디스크의 어떤 섹터에 기록했는지를 알아야 나중에 다시 swap in할 수 있으므로, anon_page 구조체 안에 슬롯 넘버를 기록해둔다. 디스크 섹터의 가용 상태만 관리하면 되므로, bitmap을 사용할 수 있다.

/* Swap table. */
#define DISK_SEC 512
#define SEC_PER_PAGE 8
#define MAX_SLOTS 32768
#define SLOT_INIT (size_t)(-1)

static struct bitmap *swap_slot;
static struct page **swap_table; // used for copy-on-write.

/* Semaphore for sector allocation. */
static struct lock slot_lock;
static struct lock disk_lock;

/* Initialize the data for anonymous pages */
void vm_anon_init(void) {
  /* Set up the swap_disk. */
  swap_disk = disk_get(1, 1);

  /* Calculate disk size. */
  size_t slots = disk_size(swap_disk) / SEC_PER_PAGE;
  slots = MAX_SLOTS < slots ? MAX_SLOTS : slots;

  /* Create swap slot table. */
  swap_slot = bitmap_create(slots);

  /* Create swap page table: copy-on-write. */
  size_t page_cnt = (slots * sizeof(struct page *)) / 0x1000;
  swap_table = palloc_get_multiple(PAL_ZERO, page_cnt);

  /* Initialize locks. */
  lock_init(&slot_lock);
  lock_init(&disk_lock);
}

/* Find free disk slot. */
static size_t allocate_slot() {
  lock_acquire(&slot_lock);
  size_t slot = bitmap_scan_and_flip(swap_slot, 0, 1, false);
  lock_release(&slot_lock);
  return slot;
}

/* Mark as free slot. */
static void free_slot(size_t slot) {
  lock_acquire(&slot_lock);
  bitmap_set(swap_slot, slot, false);
  lock_release(&slot_lock);
}

여러 프로세스가 스왑 테이블을 공유하므로 락을 걸어 빈 슬롯을 할당/해제하는 식으로 구현해주었다. swap_table은 copy-on-write을 구현하지 않는다면 당장은 필요없다.

/* Swap out the page by writing contents to the swap disk. */
static bool anon_swap_out(struct page *page) {
  struct frame *frame = page->frame;
  void *kva = page->frame->kva;
  ASSERT(frame && kva)


  /* Find free disk sector */
  size_t slot = allocate_slot();
  if (slot == BITMAP_ERROR) {
    printf("Swap disk out of memory.\n");
    return false;
  }

  /* Write to swap disk. */
  disk_sector_t sec = slot * SEC_PER_PAGE;
  do_disk_io(sec, SEC_PER_PAGE, kva, disk_write);

  /* Clear all linked pages. */
  struct thread *t;
  struct page *prev;
  struct list_elem *front;
  while (!list_empty(&frame->pages)) {
    front = list_pop_front(&frame->pages);
    page = list_entry(front, struct page, frame_elem);
    t = page->thread;

    /* Unlink with frame. */
    page->frame = NULL;
    page->flags = page->flags & ~PTE_P;
    pml4_set_accessed(t->pml4, page->va, false);
    pml4_clear_page(t->pml4, page->va);

    /* Link with disk slot. */
    page->anon.slot = slot;
    swap_table_push(slot, page);
    ASSERT(!swap_table_empty(slot));
  }

  return true;
}

/* Swap in the page by read contents from the swap disk. */
static bool anon_swap_in(struct page *page, void *kva) {
  ASSERT(page_get_type(page) == VM_ANON)

  struct frame *frame = page->frame;
  ASSERT(frame && kva)

  size_t slot = page->anon.slot;
  if (slot == SLOT_INIT) {
    /* If page was never swapped out, just install. */
    list_push_back(&frame->pages, &page->frame_elem);
    return vm_install_page(page, page->thread);
  }

  /* Read from disk_sec */
  disk_sector_t sec = slot * SEC_PER_PAGE;
  do_disk_io(sec, SEC_PER_PAGE, kva, disk_read);

  /* Set this page's access bit. */
  pml4_set_accessed(page->thread->pml4, page->va, true);

  /* Set all linked pages present. */
  while (!swap_table_empty(slot)) {
    page = swap_table_pop(slot);
    ASSERT(page != NULL);

    /* Link with frame. */
    page->frame = frame;
    page->flags = page->flags | PTE_P;
    vm_map_frame(page, frame);
    vm_install_page(page, page->thread);

    /* Unlink with disk slot. */
    page->anon.slot = SLOT_INIT;
  }

  /* Mark as free sector. */
  free_slot(slot);
  return true;
}

구현된 anon page의 swap in/out 은 다음과 같다. 프레임 안에 pages 리스트가 있는 부분이 의아할 수 있는데 이는 copy-on-write로 부모와 자식의 페이지가 동일한 프레임에 연결되어 있는 경우 프레임:페이지가 일대다 관계가 되기 때문이다. 따라서 frame은 page의 리스트를 갖고 page는 frame의 주소를 참조한다. 그러므로 swap out되면, 프레임의 pages 리스트를 돌면서 해당 페이지를 각각의 thread->pml4에서 클리어해주고, 접근 비트를 false로 설정해준다. 그리고 해당 페이지들을 swap_table에 백업해둔다.

SLOT_INIT 매크로는 초기 anon page의 슬롯을 초기화해줄 때 넣는 값인데, 이는 특히 spt table을 복사하는 fork 과정 (copy-on-write라면 vm_handle_wp)에서 중요하다. 부모의 page가 이미 anon으로 초기화된 경우, 자식의 page에서 vm_do_claim_page의 swap_in 에서 불리는 함수는 uninit_swap_in이 아니라 anon_swap_in이다. 이때의 로직을 분리해주기 위해 slot이 SLOT_INIT인 상태인지를 확인한다.

👀 이 코드에서 swap_table의 자료구조?

단방향 연결 리스트로 구현했다. 처음에는 <list.h>의 리스트를 사용해 list의 배열로 구현하려고 했는데, 리스트 구조체 하나당 주소값이 4개가 들어가므로 32바이트가 된다. 그런데 어차피 중간 삭제가 많지 않고, stack 처럼 한방향으로 push, pop을 수행할 것이라면 단방향 연결 리스트로 구현해도 괜찮지 않을까 싶었다. (swap-out에서는 frame->pages 에 속한 모든 페이지를 다 뽑아서 swap_table[slot]으로 보내고, swap-in에서는 그 반대로 하므로..) 그래서 struct page 안에 struct page* 타입의 next_swap 멤버를 넣어 놓고, 단방향 연결리스트의 링크로 활용한다. 결과적으로 슬롯 하나당 32바이트 대신 8바이트만 쓰고, 대신 페이지 구조체 안에 struct page* 주소를 넣어 두므로 총 16바이트로.. 약 두 배 정도 공간을 절약했다.

+) 그런데 사실 페이지의 상태별로 동시에 존재할 수 있는 테이블을 생각해보면, swap-in 된 페이지는 프레임의 리스트에 엮여 있고, swap-out된 페이지는 스왑 테이블에 엮여 있다. 따라서 프레임 구조체 안의 struct list pages도 단방향 연결리스트로 구현해서 주소값 하나만 가지고 있도록 개선할 수 있을 것 같다.

페이지 상태	테이블
uninitialized	spt
swap-in	spt, frame->pages
swap-out	spt, swap_table[slot]

struct page {
  const struct page_operations *operations;
  void *va;            /* Address in terms of user space */
  struct frame *frame; /* Back reference for frame */

  struct hash_elem table_elem; /* Hash elem for spt. */
  struct list_elem frame_elem; /* List elem for frame-mapping. */

  struct page* next_swap;      /* 🔥 Singly lisked list for swap-table. */
  struct thread* thread;       /* Thread info. */
  uint16_t flags;              /* Flags. */
  ...
}


/* Push front into swap table. */
static void swap_table_push(size_t slot, struct page *page) {
  ASSERT(slot < MAX_SLOTS)
  lock_acquire(&slot_lock);
  struct page *curr = swap_table[slot];
  page->next_swap = curr;
  swap_table[slot] = page;
  lock_release(&slot_lock);
}

/* Pop front from swap table. */
static struct page *swap_table_pop(size_t slot) {
  ASSERT(slot < MAX_SLOTS)
  lock_acquire(&slot_lock);
  /* Returns NULL if table is empty. */
  struct page *top = swap_table[slot];
  if (top != NULL) {
    swap_table[slot] = top->next_swap;
    top->next_swap = NULL;
  }
  lock_release(&slot_lock);
  return top;
}

/* Returns if swap table is empty. */
static bool swap_table_empty(size_t slot) {
  ASSERT(slot < MAX_SLOTS)
  bool rtn;
  lock_acquire(&slot_lock);
  rtn = (swap_table[slot] == NULL);
  lock_release(&slot_lock);
  return rtn;
}

/* Remove page from swap table. */
static struct page *swap_table_remove(size_t slot, struct page *page) {
  ASSERT(slot != SLOT_INIT);

  lock_acquire(&slot_lock);
  struct page *before = swap_table[slot];
  if (before == page) {
    lock_release(&slot_lock);
    return swap_table_pop(slot);
  }

  while (before->next_swap != page) {
    before = before->next_swap;
    if (before == NULL) {
      /* Page is not found. */
      lock_release(&slot_lock);
      return NULL;
    }
  }
  before->next_swap = page->next_swap;
  lock_release(&slot_lock);
  return page;
}

단점이라면, swap out된 페이지가 destroy 되는 경우가 생긴다. 그러면 swap_table[slot] 리스트에서도 삭제해 주어야 하는데.. SLL이라 중간 삭제의 경우 리스트를 한번 검색해 주어야 한다. 이때 $O(n)$의 시간이 걸린다. 여기서 n은 하나의 프레임을 공유하고 있는 페이지의 수이다.

06) Copy-on-write

어렵다.. 어려운데? .. 어렵네..

아이디어는 부모와 자식의 페이지 복사 역시 lazy하게 하겠다는 거다. fork 콜로 인해 처음 페이지 테이블을 복사할 때, 부모와 자식의 페이지는 같은 프레임과 매핑된다. 그리고 어느 한쪽이 프레임을 수정하려고 할 때 비로소 새로운 프레임이 할당되어 복제된다. 이를 구현하기 위해 write-protect page의 fault를 활용할 수 있다.

1. spt copy에서 부모와 자식의 페이지를 read-only로 설정한다.
2. 만약 read-only 페이지에 대한 write fault가 발생하면, 복제한다.

🚨 주의: 아직 개선해야 할 점이 많은 오류코드임

/* Hash action function which copies a single page. */
static void spt_copy_page(struct hash_elem *e, void *aux) {
  struct supplemental_page_table *dsc_spt =
      (struct supplemental_page_table *)aux;
  struct hash *dsc_hash = &dsc_spt->hash;
  struct page *src_page = hash_entry(e, struct page, table_elem);

  struct page *dsc_page = calloc(1, sizeof(struct page));
  if (dsc_page == NULL) {
    printf("Child page allocation failed\n");
    return;
  }

  /* Copy spt entries. */
  memcpy(dsc_page, src_page, sizeof(struct page));

  /* Disconnect from parent's hash table. */
  memset(&dsc_page->table_elem, 0, sizeof(struct hash_elem));
  memset(&dsc_page->frame_elem, 0, sizeof(struct list_elem));
  hash_insert(dsc_hash, &dsc_page->table_elem);

  /* Set new values. */
  dsc_page->next_swap = NULL;
  dsc_page->thread = thread_current();

  switch (page_get_type(src_page)) {
    case VM_ANON:
      if (!pg_present(src_page)) {
        if (!pg_init(src_page)) {
          /* Uninitialized anon pages are segment pages. */
          struct file_info *src_aux = src_page->uninit.aux;
          struct file_info *dsc_aux = calloc(1, sizeof(struct file_info));
          if (dsc_aux == NULL) {
            printf("Child uninit page aux allocation failed\n");
            return;
          }
          memcpy(dsc_aux, src_aux, sizeof(struct file_info));
          dsc_page->uninit.aux = dsc_aux;
          return;
        }

        /* Swapped out anon page. */
        size_t slot = dsc_page->anon.slot;
        anon_swap_table_push(slot, dsc_page);

      } else {
        /* Present anon page. */
        vm_map_frame(dsc_page, src_page->frame);
      }
      break;

    case VM_FILE:
      if (!pg_present(src_page)) {
        /* Uninitialized file-backed page. */
        if (!pg_init(src_page)) {
          struct file_page *src_aux = src_page->uninit.aux;
          struct file_page *dsc_aux = calloc(1, sizeof(struct file_page));
          if (dsc_aux == NULL) {
            printf("Child uninit page aux allocation failed\n");
            return;
          }

          memcpy(dsc_aux, src_aux, sizeof(struct file_page));
          dsc_page->uninit.aux = dsc_aux;
          spt_copy_file(src_page, dsc_page);

          /* Return immediately. */
          return;
        }

        /* Swapped out file-backed page. */
        size_t slot = dsc_page->file.slot;
        file_swap_table_push(slot, dsc_page);

      } else {
        /* Present file-backed page. */
        vm_map_frame(dsc_page, src_page->frame);
      }

      /* Copy file if the page is head-page. */
      spt_copy_file(src_page, dsc_page);
      break;

    default:
      break;
  }

  /* Set write-protect. */
  src_page->flags = src_page->flags & ~PTE_W;
  dsc_page->flags = dsc_page->flags & ~PTE_W;

  /* Set copy-on-write flag. */
  src_page->flags = src_page->flags | PG_COW;
  dsc_page->flags = dsc_page->flags | PG_COW;

  /* Install in pml4 if swap-in pages. */
  if (pg_present(src_page)) {
    vm_install_page(src_page, src_page->thread);
    vm_install_page(dsc_page, dsc_page->thread);
  }
}

길다.. case문 2개는 프로젝트 3의 주요 두 개 메모리 타입인 anon과 file로 나누어져 있고, 각각의 case안에서 1. uninit인 경우, 2. swap-out인 경우, 3. swap-in 인 경우로 나뉜다. in되어 있는 페이지의 경우에는 install하면서 비트를 & ~PTE_W으로 설정해 준다.

/* Page Fault Handler: Return true on success */
bool vm_try_handle_fault(struct intr_frame *f, void *addr, bool user,
                         bool write, bool not_present) {

  ...

  /* If page is write-protect, return handle_wp. */
  if (write && !pg_writable(page)) {
    return vm_handle_wp(page);
  }

  ...
}

/* Handle the fault on write_protected page */
// TODO: uninit page도 handle하게 ?
bool vm_handle_wp(struct page *page) {
  if (!pg_copy_on_write(page)) {
    /* If cow-flag is not on,
     * this page is write-protect page. */
    return false;
  }

  /* Unlink from old frame. */
  struct frame *old_frame = page->frame;
  vm_unmap_frame(page);

  /* If this page was the last,
   * Re-link with frame and return. */
  if (list_empty(&old_frame->pages)) {
    page->flags = page->flags | PTE_W;
    page->flags = page->flags & ~PG_COW;

    vm_map_frame(page, old_frame);
    return vm_install_page(page, page->thread);
  }

  /* Link with new frame. */
  struct frame *new_frame;
  /* Copy-on-write pages are all present. */
  if (pg_present(page)) {
    /* Mark as no copy-on-write page. */
    page->flags = page->flags | PTE_W;
    page->flags = page->flags & ~PG_COW;

    if (!vm_do_claim_page(page)) {
      /* If swap-in fails, return false.*/
      return false;
    }

    /* Page is now swapped-in. Copy old frame. */
    new_frame = page->frame;
    memcpy(new_frame->kva, old_frame->kva, PGSIZE);
    return true;
  }
  return false;
}

PG_COW로 설정된 페이지는 위와 같이 vm_try_handle_fault 처리 중 별도로 핸들링한다. 그런데 지금 보니 swap-out된 페이지도 비트 설정을 해 주어야 할 것 같다.. copy-on-write의 경우 extra 최강자답게 난이도가 높은 것 같다. 그리고 지금까지의 자료구조를 바꿔야 해서 막바지에 코드를 완성하기가 어려웠다. (물론 이것까지 안 해도 대충 cow-simple 테스트만 통과하게끔 처리해둘 수는 있다.) 한 가지 더 어려웠던 부분은: read-only 설정으로 인해 fault수가 증가하면서 이곳저곳에 걸어 두었던 락과 세마포어로 인한 동기화 문제가 터지기 시작했다는 점이다. 코드의 흐름을 정확하게 알고 있어야 가급적 좁은 범위에서, 필요한 만큼만 락을 걸어 자원 접근을 제어할 수 있을 것 같다. 기회가 된다면 힘 닿는 데까지 조금 더 보완하고 싶은 점이다.