struct page

• supplemental page table에 삽입되는 각 페이지의 정보 (일 것 같음)

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

    /* Your implementation */

    /* Per-type data are binded into the union.
     * Each function automatically detects the current union */
    union {
        struct uninit_page uninit;
        struct anon_page anon;
        struct file_page file;
    };
};

• operations: 후술
• va: 해당 페이지가 매핑되어야 할, 사용자 공간의 가상 주소
  • offset에 해당하는 하위 12비트는 0
• frame: struct page와 실제로 연결된 물리 프레임 구조체
• uninit OR anon OR file
  • uninitialized / anonymous / file-backed page 중 하나
  • struct uninit_page, struct anon_page, struct file_page 차례로 채워야 할듯
  • struct uninit_page는 채워져 있음! 별도 구현 안해도됨.
  • struct anon_page, struct file_page는 비어 있음... 깃북 Anonymous Page, Memory Mapped Files에서 해야하는거 아닐까

// include/vm/uninit.h
struct uninit_page {
    /* Initiate the contets of the page */
    vm_initializer *init;
    enum vm_type type;          // 여기선 VM_UNINIT
    void *aux;
    /* Initiate the struct page and maps the pa to the va */
    bool (*page_initializer)(struct page *, enum vm_type, void *kva);
};

struct page_operations

• 함수 포인터를 이용해 객체지향 메서드 비슷하게 구현
• 페이지 대상으로 특정 동작 수행
  • 페이지의 VM_UNINIT, VM_ANON, VM_FILE 여부에 따라 적절한 함수를 별도로 호출

// include/vm/vm.h
struct page_operations {
    bool (*swap_in)(struct page *, void *);
    bool (*swap_out)(struct page *);
    void (*destroy)(struct page *);
    enum vm_type type;
};

#define destroy(page)                \
    if ((page)->operations->destroy) \
    (page)->operations->destroy(page)

// vm/file.c
// file_backed page의 struct page_operations
static const struct page_operations file_ops = {
    .swap_in = file_backed_swap_in,
    .swap_out = file_backed_swap_out,
    .destroy = file_backed_destroy,
    .type = VM_FILE,
};

// anonymous page의 struct page_operations
static const struct page_operations anon_ops = {
// 생략
};

// uninitialized page의 struct page_operations
static const struct page_operations uninit_ops = {
// 생략
};

• operations 필드가 file_ops인 page에서 destroy 호출 시
  • page -> operations -> destroy를 호출
  • 즉 file_ops.destroy인 file_backed_destroy 호출

Supplemental Page Table

• 가상 주소 va와, 페이지 정보가 저장된 struct page을 매핑하면 됨.
• 어떤 자료구조가 좋을까요? 해시 테이블?
  • 해시 사용 시 가장 주소 va를 키, struct page를 값으로 사용하게 됨

// include/threads/thread.h
// 이미 선언되어 있음
#ifdef VM
    /* Table for whole virtual memory owned by thread. */
    struct supplemental_page_table spt;
#endif

// userprog/process.c
//  initd, __do_fork에 위치
#ifdef VM
    supplemental_page_table_init(&thread_current()->spt);
#endif

// vm/vm.h
// 놀랍게도 진짜 저럼. 직접 구현해야 함.
struct supplemental_page_table {};

• 아래 세 함수는 vm/vm.c에서 구현해야 함
• void supplemental_page_table_init (struct supplemental_page_table *spt);
  • SPT 초기화
  • userprog/process.c의 initd 및 __do_fork에서 호출
• struct page *spt_find_page (struct supplemental_page_table *spt, void *va);
  • spt에서 va에 대응되는 struct page를 찾는다.
  • 실패 시 NULL을 반환
• bool spt_insert_page (struct supplemental_page_table *spt, struct page *page);
  • struct page를 supplemental page table에 삽입
  • va (struct page의 va)가 SPT에 존재하지 않을 때만 삽입.

/* Initialize new supplemental page table */
void supplemental_page_table_init(struct supplemental_page_table *spt UNUSED) {}

/* Copy supplemental page table from src to dst */
bool supplemental_page_table_copy(struct supplemental_page_table *dst UNUSED,
                                  struct supplemental_page_table *src UNUSED) {}

/* Free the resource hold by the supplemental page table */
void supplemental_page_table_kill(struct supplemental_page_table *spt UNUSED) {
    /* TODO: Destroy all the supplemental_page_table hold by thread and
     * TODO: writeback all the modified contents to the storage. */
}

해시 테이블로 Supplemental Page Table 구현하기?

• 깃북에서 놀랍게도 많은 힌트를 주고 있음
• include/lib/kernel/hash.h에 해시 함수 코드 있음. #include <hash.h> 필수
• 일단 아직 구현은 하지 않았고, 깃북에서 참고할만한 코드 위주로 긁어옴

(1) struct supplemental_page_table에 struct hash 추가하기

// include/vm/vm.h
struct supplemental_page_table {
    struct hash pages;   // 이름은 일단 걍 아무거나로 정함
}

(2) struct page에 struct hash_elem 추가하기

// include/vm/vm.h
struct page {
    struct hash_elem hash_elem; /* Hash table element. */
    void *va; /* 깃북에선 addr로 되어 있는데, 우리 코드에선 va로 되어 있는 듯 */
    // 나머지...
};

• 쓰레드를 연결 리스트로 관리했을 때도, struct thread에 struct list_elem 멤버를 두고,
• 연결 리스트엔 struct list_elem을 삽입하고 이걸 list_entry() 함수에 넣어 struct thread로 복원해야 했음.
• 해시도 마찬가지. struct page에 struct hash_elem을 두고, 테이블엔 struct hash_elem을 삽입.
• 그리고 struct hash_elem을 hash_entry()에 넣어 struct page로 복원할 수 있음.

(3) 해시 함수 및 비교 함수 정의

• 해시 함수는 page_hash()라는 이름으로, 비교 함수는 page_less()라는 이름으로 깃북에 이미 구현 예시가 있음
  • page_hash(p)는 페이지 p의 가상주소를, 해시 값으로 변환.
  • page_less(a, b)는 두 페이지 a, b를 매개변수로 받고, a가 b보다 주소가 더 낮으면 true를, 더 크면 false를 반환
• 아래에다 깃북에 써진 코드 그대로 적음.
  • 근데 깃북에선 가상주소 뜻하는 필드가 va 아니라 addr로 되어 있던데... va로 바꿔야 될듯 함.

/* Returns a hash value for page p. */
unsigned page_hash (const struct hash_elem *p_, void *aux UNUSED) {
  const struct page *p = hash_entry (p_, struct page, hash_elem);
  return hash_bytes (&p->va, sizeof p->va);
}

/* Returns true if page a precedes page b. */
bool page_less (const struct hash_elem *a_,
           const struct hash_elem *b_, void *aux UNUSED) {
  const struct page *a = hash_entry (a_, struct page, hash_elem);
  const struct page *b = hash_entry (b_, struct page, hash_elem);

  return a->va < b->va;
}

(4) supplemental_page_table_init()을 hash_init 사용해서 구현

• bool hash_init (struct hash *hash, hash_hash_func *hash_func, hash_less_func *less_func, void *aux)
  • 해시 테이블을 초기화함. 앞서 만든 해시 함수와 비교 함수가 필요할듯....

(5) spt_find를 hash_find 사용해서 구현

• struct hash_elem *hash_find (struct hash *hash, struct hash_elem *element)
  • 해시 테이블 hash에서 element를 찾음
  • 못 찾으면 NULL 반환
• 깃북에선 page_lookup 함수를 직접 만들어서 구현함. 이걸 응용하면 될 듯함.

/* Returns the page containing the given virtual address, or a null pointer if no such page exists. */
struct page * page_lookup (const void *address) {
  struct page p;
  struct hash_elem *e;

  p.addr = address;
  e = hash_find (&pages, &p.hash_elem);
  return e != NULL ? hash_entry (e, struct page, hash_elem) : NULL;
}

(6) spt_insert_page()를 hash_insert 사용해서 구현

• struct hash_elem *hash_insert (struct hash *hash, struct hash_elem *element);
  • hash에 element 삽입
  • 삽입 성공 시, NULL 반환. 삽입 실패 시(동일한 element 존재), 해당 struct hash_elem의 주소 반환

struct frame

• frame table에 삽입되는 각 프레임의 정보(일 것 같음)

// vm/vm.h
/* The representation of "frame" */
struct frame {
    void *kva;
    struct page *page;
};

• kva: 물리프레임의 주소(사실 커널가상주소), page: struct page의 포인터
  • 다른 필드들을 나중에 추가해야 할 수도 있다고 함
• static struct frame *vm_get_frame (void)
  • (1) palloc_get_page -> 사용자 풀(PAL_USER)에서 할당받은 물리 프레임의 (커널가상)주소 반환.
  • (2) struct frame *frame 공간 할당... malloc, calloc 쓰면 될려나
    • calloc으로 동적할당하면 될려나?
  • (3) frame의 필드초기화. kva에 (1)에서 얻은 프레임의 (커널가상)주소 저장. page는 NULL로 놔둬야 함.
  • (4) struct frame *frame의 주소 반환
• 아직은 가용 프레임이 없어 swap out하는 경우는 고려하지 않아도 됨. 공간할당 실패하면 PANIC("todo") 할것.

/* palloc() and get frame. If there is no available page, evict the page
 * and return it. This always return valid address. That is, if the user pool
 * memory is full, this function evicts the frame to get the available memory
 * space.*/
static struct frame *vm_get_frame(void) {
    struct frame *frame = NULL;
    /* TODO: Fill this function. */

    ASSERT(frame != NULL);
    ASSERT(frame->page == NULL);
    return frame;
}

• bool vm_do_claim_page (struct page *page);
  • claim, 즉 물리 프레임을 할당받음
  • (1) vm_get_frame으로 프레임 할당받고 struct frame * 주소 얻기 --> 이미 기존코드에서 해주고 있음
  • (2) struct page *page와 (1)에서 할당받은 struct frame을 page table에서 연결하기??
    • struct page의 va 멤버, struct frame의 kva 필드를 사용해서, pml4_set_page() 사용하면 될려나?
  • (3) 깃북에선 안 나왔는데, 이때 struct frame의 struct page *page 필드, struct page의 struct frame *frame도 갱신해야 할려나?? --> 이건 이미 기존코드에서 해주고 있음
  • 성공 시 true 실패 시 false

/* Claim the PAGE and set up the mmu. */
static bool vm_do_claim_page(struct page *page) {
    struct frame *frame = vm_get_frame();

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

    /* TODO: Insert page table entry to map page's VA to frame's PA. */

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

• bool vm_claim_page (void *va);
  • va에 해당하는 페이지의 struct page 찾고, 이를 vm_do_claim_page의 매개변수로 넣어서 호출
  • 앞서 구현한 spt_find_page(va)로 찾을 수 있지 않을까?

/* Claim the page that allocate on VA. */
bool vm_claim_page(void *va UNUSED) {
    struct page *page = NULL;
    /* TODO: Fill this function */

    return vm_do_claim_page(page);
}