주요 struct 구조

page, frame, supplemental_page_table

last update: 1220	additional property
`page`	`struct hash_elem hash_elem` , `bool writable`
`frame`	x
`supplemental_page_table`	`struct hash spt_hash`

why hash table?

type	pro	con
array 배열	구현이 간단함, 시간복잡도가 낮음	공간복잡도가 높음(메모리 용량을 많이 차지)
(doubly) linked list 연결리스트	구현이 간단함	탐색시 최악의 경우 O(n)의 시간복잡도로 전부 찾아야 한다.
hash table 해시테이블	탐색시 시간복잡도가 O(1), 연결된 공간을 사용하는 것이 아닌 분리되어있는 공간을 사용하므로 공간복잡도도 좋다.
hash map 비트맵	비트에 정보를 매핑시켜 공간복잡도는 최상	index화하여 구분해야 하는 자료가 많아진다면 복잡하여 구현이 어려워진다.

pintOS는 hash 관련 tool 함수를 제공한다.

struct supplemental_page_table {
    struct hash spt_hash; /* hash table : should not access directly */
};

`hash_elem` & `writable` in `struct page`

struct page {

    /* ... */

    /* project 3 */
    struct hash_elem hash_elem; /* Hash table element. */
    bool writable;

};

page 구조체, 즉 페이지가 속해 있는 hash table과 연결해주는 요소가 바로 hash_elem이다. page구조체에 hash_elem을 추가해 줌으로써 다음과 같은 key - value 쌍이 성립된다.

	key	index?	value
type	array		linked_list
	`page->va`	`hash_func(page->va)`	`struct page`

Implemented functions

Memory Management

구현해야 하는 함수는 총 3개!

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

Implement Supplemental Page Table

void supplemental_page_table_init (struct supplemental_page_table *spt);

SPT를 초기화하는 함수로 이 함수 내에서 초기화를 해야 하므로 SPT의 데이터 구조와 밀접한 관련이 있다. 이 함수는 userprog/process.c의 initd에서 새 프로세스가 시작될 때, 그리고 userprog/process.c의 __do_fork 에서 프로세스가 새로 forked될 때 호출된다.

우리의 프로젝트에서는 spt를 hash table로 하기로 결정했으므로 이곳에서는 spt 내부의 hash table만 초기화해준다. hash_init() 의 인자로는 hash_hash_func *hash, hash_less_func *less 가 필요한데 page_hash와 page_less가 들어간다. 두 함수는 gitbook의 hash table 부록에 수록되어 있었다.

hash 분석

/* Hash table. */
struct hash {
    size_t elem_cnt;            /* Number of elements in table. */
    size_t bucket_cnt;          /* Number of buckets, a power of 2. */
    struct list *buckets;       /* Array of `bucket_cnt' lists. */
    hash_hash_func *hash;       /* Hash function. */
    hash_less_func *less;       /* Comparison function. */
    void *aux;                  /* Auxiliary data for `hash' and `less'. */
};

/* Initializes hash table H to compute hash values using HASH and
   compare hash elements using LESS, given auxiliary data AUX. */
bool
hash_init (struct hash *h,
        hash_hash_func *hash, hash_less_func *less, void *aux) {
    h->elem_cnt = 0;
    h->bucket_cnt = 4;
    h->buckets = malloc (sizeof *h->buckets * h->bucket_cnt);
    h->hash = hash;
    h->less = less;
    h->aux = aux;

    if (h->buckets != NULL) {
        hash_clear (h, NULL);
        return true;
    } else
        return false;
}

의문 1. hash.h의 주석에서는 chain list에서 동적 할당을 받지 않는다 적혀 있는데 h->buckets에 malloc을 사용 하고 있다.

page_hash()

/* project 3 */
/* hash table functions */
/* 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);
}

page_hash()는 page->va를 hash화 해주는 함수로, hash_entry를 통해 hash_elem이 속한 struct page를 가져와 그 page의 va를 hash_byte함수를 통해 해시값을 반환한다. hash_byte()함수는 아래와 같다. (Returns a hash of the SIZE bytes in BUF.) Flower-Noll-Vo 해시 함수를 통해 buf_메모리 공간에 있는 정수를 size만큼 암호화시켜 리턴한다.
hash_entry()는 hash_elem을 받아 그 elem을 갖고 있는 page 구조체를 반환한다. 그전 프로젝트에서 pintos가 제공한 list_entry()와 동일한 원리였다.

/* Fowler-Noll-Vo hash constants, for 32-bit word sizes. */
#define FNV_64_PRIME 0x00000100000001B3UL
#define FNV_64_BASIS 0xcbf29ce484222325UL

/* Returns a hash of the SIZE bytes in BUF. */
uint64_t
hash_bytes (const void *buf_, size_t size) {
    /* Fowler-Noll-Vo 32-bit hash, for bytes. */
    const unsigned char *buf = buf_;
    uint64_t hash;

    ASSERT (buf != NULL);

    hash = FNV_64_BASIS;
    while (size-- > 0)
        hash = (hash * FNV_64_PRIME) ^ *buf++;

    return hash;
}

page_less()

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

hash_entry()로 받아온 두 page a, b의 주소값을 비교하여 a가 b보다 선행하면 true를 리턴한다.
이 page_less()를 사용하여 결과가 false라면 가능한 경우는 b가 a보다 선행하거나(b의 va 주소 값이 작다) a와 b의 주소가 같다는 경우가 나온다. 이것과 관련하여 hash쪽에서 ><의 개념을 사용하여 일치 불일치를 찾는 경우가 있다고 다른 팀의 토의 청강 시 들었는데, 정확히 어디인지 모르겠으나 참고해 두면 좋을 것 같아 기록해둔다.

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 *va, struct supplemental_page_table *spt) {
  struct page p;
  struct hash_elem *e;

  p.va = va;
  e = hash_find (&spt->spt_hash, &p.hash_elem);
  return e != NULL ? hash_entry (e, struct page, hash_elem) : NULL;
}

find and insert to SPT

spt_find_page :: find 'the va'

spt와 va를 받아 spt에서 page구조체를 찾아 해당 page가 spt의 해시 테이블 안에 있다면 반환한다. 존재하지 않다면 NULL을 리턴한다.

/* Find VA from spt and return page. On error, return NULL. */
struct page *
spt_find_page (struct supplemental_page_table *spt UNUSED, void *va UNUSED) {
    struct page *page = NULL;
    /* TODO: Fill this function. */
    uint8_t* upage_va = pg_round_down(va);
    page = page_lookup(upage_va, spt);

    return page;
}

여기서 중요한 건 va를 찾는 것이었다. va는 이미 주었는데 이걸 찾다니? va는 4kb의 페이지 단위로 조각조각 난 va 중의 어딘가에 있으므로, 그 va가 속한 page를 찾으려면 page의 align을 맞추어야 한다.(앞서 했던 malloc lab에서의 그 align과 같은 원리였다!) 이것을 위해 pg_round_down(va)를 통해 가장 가까운 page의 boundary 를 찾아 바로 그 va를 얻어야 한다. 그래야 spt에서 그 페이지를 얻어낼 수 있다. 이 개념은 va에서 page를 얻어낼 때마다 반드시 처리해야하는 전처리에 해당된다 볼 수 있다.

/* Round down to nearest page boundary. */
#define pg_round_down(va) (void *) ((uint64_t) (va) & ~PGMASK)

spt_insert_page

spt와 page를 받아 그 page를 spt에 끼워 넣는 함수. 해당 페이지가 spt 안에 존재하는지 아닌지 확인 해야 한다. hash table을 사용했으므로 넣는 건 hash_insert를 사용하면 된다.

/* Insert PAGE into spt with validation. */
bool
spt_insert_page (struct supplemental_page_table *spt UNUSED,
        struct page *page UNUSED) {
    int succ = false;
    /* TODO: Fill this function. */
    struct hash_elem* inserted = hash_insert(&spt->spt_hash, &page->hash_elem);

    if(! inserted) { //when failed(?)
        succ = false;
    }

    return succ;
}

Frame Management

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

Anonymous Page

Lazy Loading for Executable

bool vm_alloc_page_with_initializer (enum vm_type type, void *va, bool writable, vm_initializer *init, void *aux);
static bool uninit_initialize (struct page *page, void *kva);
void vm_anon_init (void);
bool anon_initializer (struct page *page,enum vm_type type, void *kva);

J-dbd / PintOS_lab

[VM] Implementation Recordings #23

struct 구조

Implemented functions

Memory Management

Implement Supplemental Page Table

Frame Management

Anonymous Page

Lazy Loading for Executable

주요 struct 구조

why hash table?

`hash_elem` & `writable` in `struct page`

Implemented functions

Memory Management

Implement Supplemental Page Table

hash 분석

page_hash()

page_less()

page_lookup()

find and insert to SPT

spt_find_page :: find 'the va'

spt_insert_page

Frame Management

Anonymous Page

Lazy Loading for Executable

J-dbd / PintOS_lab

[VM] Implementation Recordings #23

struct 구조

Implemented functions

Memory Management

Implement Supplemental Page Table

Frame Management

Anonymous Page

Lazy Loading for Executable

주요 struct 구조

why hash table?

hash_elem & writable in struct page

Implemented functions

Memory Management

Implement Supplemental Page Table

hash 분석

page_hash()

page_less()

page_lookup()

find and insert to SPT

spt_find_page :: find 'the va'

spt_insert_page

Frame Management

Anonymous Page

Lazy Loading for Executable

`hash_elem` & `writable` in `struct page`