본문 바로가기
카테고리 없음

[pintOS] 보조 페이지 테이블 (SPT) 구현

@정소민fan2025. 5. 31. 22:22

pintOS project3 구현의 시작점인 SPT 구현을 포스팅하겠다

SPT가 무엇인지는 이전에 다 포스팅했으니까 잘 모르겠으면 보고 오자

 

우리는 보조 페이지 테이블 구현을 위해 자료구조를 선택해서 결정해야 한다

나는 해시 테이블을 사용해셔 구현하기로 결정했다

해시 테이블 자료구조는 hash.h에 정의되고 hash.c에 구현되어있다

https://github.com/Week12-13-GOAT/pintos-vm/wiki/hash-%EC%82%AC%EC%9A%A9-%EB%B0%A9%EB%B2%95

 

hash 사용 방법

미니준혁이에게 짬때리는 레포. Contribute to Week12-13-GOAT/pintos-vm development by creating an account on GitHub.

github.com

여기에 정리해두었으니 구현하기 전에 먼저 읽어보자. 나중에 기회가 되면 hash 사용법도 따로 포스팅하겠다

 

함수 구현하기

우리가 SPT를 위해 구현해야 할 함수는 총 6가지이다

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);

void spt_remove_page(struct supplemental_page_table *spt, struct page *page)

bool supplemental_page_table_copy (struct supplemental_page_table *dst,
                                   struct supplemental_page_table *src);
                                   
void supplemental_page_table_kill (struct supplemental_page_table *spt);

 

먼저 SPT에 해시 구조체를 만들어주어야 한다. SPT 자체는 해시 구조체가 아니기 때문이다.

그러면 SPT 내부의 해시 구조체에 들어갈 엔트리도 만들어줘야 한다. page 구조체 자체에 hash_elem을 추가해서 엔트리로 사용할 수도 있지만, 그렇게 하지 않고 래퍼 엔트리를 생성해두었다.

구조체 구현

struct supplemental_page_table
{
    struct hash SPT_hash_list;
};

struct SPT_entry
{
    /* 이 엔트리의 키 값이 될 가상 주소 */
    void *va;
    /* 페이지 */
    struct page *page;
    /* 해시 테이블 요소*/
    struct hash_elem elem;
};

SPT 내부에 만들어둔 SPT_hash_list를 초기화해주어야 한다. 이를 SPT 초기화 함수에 만들어두자

해시 구조체를 초기화하기 위해선 hash_init 함수가 필요하다

supplemental_page_table_init

bool hash_init(struct hash *h, hash_hash_func *hash, hash_less_func *less, void *aux)

여기에 넘겨줄 해시 함수와 비교 함수를 만들어주자

static uint64_t my_hash(const struct hash_elem *e, void *aux UNUSED)
{
    struct SPT_entry *entry = hash_entry(e, struct SPT_entry, elem);
    return hash_int((uint64_t)entry->va);
}

hash_int를 사용해서 엔트리의 va를 해싱하는 함수

이 함수를 hash_init에 넘기면 내부적으로 해싱을 할 때 항상 이 함수를 사용한다

static bool my_less(const struct hash_elem *a, const struct hash_elem *b, void *aux UNUSED)
{
    if (a == NULL)
        return true;
    if (b == NULL)
        return false;
    struct SPT_entry *a_entry = hash_entry(a, struct SPT_entry, elem);
    struct SPT_entry *b_entry = hash_entry(b, struct SPT_entry, elem);
    return a_entry->va < b_entry->va;
}

각 엔트리의 va를 비교하는 함수

위 해시 함수와 같이 내부적으로 비교를 할 때 항상 이 함수를 사용한다

주의할 점은 SPT는 맨 처음에 아무런 엔트리도 갖고 있지 않으므로 a나 b 둘 중에 하나가 null이 될 수 있다는 점이다

따라서 이를 방지하기 위해 null 체크를 해주고, null이라면 바로 true나 false를 리턴해주자

하지 않으면 무한으로 페이지 폴트가 발생하는 끔찍한 상황을 만날 수 있다

void supplemental_page_table_init(struct supplemental_page_table *spt UNUSED)
{
	if (!hash_init(&spt->SPT_hash_list, my_hash, my_less, NULL))
		return;
}

이렇게 만들어준 해시 함수와 해시 비교 함수를 hash_init에 넘겨서 초기화를 진행해주자

그럼 이 함수가 어디서 실행되느냐?

static void
initd(void *f_name)
{
#ifdef VM
	supplemental_page_table_init(&thread_current()->spt);
#endif
...
}

여기와

static void
__do_fork(void *aux)
{
...
#ifdef VM
    supplemental_page_table_init(&current->spt);
    if (!supplemental_page_table_copy(&current->spt, &parent->spt))
        goto error;
#else
...
}

여기에 이렇게 선언이 되어 있다

 

그런데 또 문제가 있다

process_exec 내부에서 process_cleanup을 호출하는데, process_cleanup 내부에선 supplemental_page_table_kill을 호출해줘서 내부의 모든 값들이 쓰레기가 되어버린다

그래서 process_cleanup 이후에 다시 supplemental_page_table_init을 호출해줘야 한다...

이럴거면 대체 왜 initd에서 초기화 코드를 넣어준건지 잘 모르겠다

spt_find_page

spt_find_page에서는 page를 찾아 반환해주면 된다. 없다면 NULL을 반환해주고.. 이건 뭐 당연하다

그럼 내부적으로 hash를 어떻게 사용하는걸까? 궁금하면 맨 위의 hash 사용법을 다시 보고오자

struct page *
spt_find_page(struct supplemental_page_table *spt UNUSED, void *va UNUSED)
{
    // 더미 SPT_entry를 생성하여 va 값 기반 hash 조회
    struct page *finding_page = NULL;
    struct SPT_entry lookup;
    lookup.va = pg_round_down(va);

    // 인자는 더미 SPT_entry, 반환된 finding_hash_elem은 실제 SPT_entry 소속 hash_elem
    struct hash_elem *finding_hash_elem = hash_find(&spt->SPT_hash_list, &lookup.elem);

    // 탐색 성공 시, hash_elem로 entry 조회, page 확보
    if (finding_hash_elem != NULL)
        finding_page = hash_entry(finding_hash_elem, struct SPT_entry, elem)->page;

    return finding_page;
}

hash_find를 사용할 땐 항상 위의 로직과 같이 더미 엔트리르 만들고 거기에 찾을 key를 넣어줘야 한다

여기서 항상 pg_round_down을 수행해줘야 하는데, 이 매크로는 4KB 단위로 내림을 해주는 매크로이다

우리가 SPT에 엔트리를 넣을 때 필드에 넣어줄 가상주소들은 항상 4KB 단위이다. 하지만 해당 페이지에서 유저 프로그램이 참조하는 영역은 4KB 경계가 아니라 그 범위 어디든 될 수 있다

 

예를 들어 0부터 4096까지가 페이지라면, SPT 엔트리는 va를 0으로 갖고 있을 것이다 유저 프로그램은 이 내부에서 2000을 참조할수도, 2를 참조할수도 있다는 것이다.

하지만 이러한 값을 그대로 lookup 더미 엔트리에 넣어버리면? 당연히 그 값 그대로를 해싱해버려서 0을 찾을수가 없다. 이를 방지하기 위해 pg_round_down을 사용해서 4KB 단위로 내림해주는 것이다

spt_insert_page

bool spt_insert_page(struct supplemental_page_table *spt UNUSED,
					 struct page *page UNUSED)
{
    /* TODO: Fill this function. */

    // 예외 처리
    if (spt == NULL || page == NULL)
    {
        return false;
    }

    // 메모리 할당
    struct SPT_entry *entry = malloc(sizeof(struct SPT_entry));
    // 예외 처리
    if (entry == NULL)
    {
        return false;
    }

    entry->va = page->va; // 가상 주소 : page 구조체의 va 필드 -> SPT_entry의 va 필드
    entry->page = page;	  // 페이지 참조 : page 구조체의 주소 -> SPT_entry의 page 포인터

    if (hash_insert(&spt->SPT_hash_list, &entry->elem) != NULL)
    {
        // 삽입 실패시 메모리 정리
        free(entry);
        return false; // 삽입 실패
    }

    return true; // SPT 페이지 삽입 성공
}

여긴 뭐 딱히 별게 없다. SPT 해시 구조체에 들어갈 래퍼 구조체를 만들어주고 그 내부에 key 값인 va와 우리가 참조할 page를 넣어준다

그리고 hash_insert를 통해 SPT 해시 구조체에 삽입한다

spt_remove_page

SPT 내부에서 인자로 받은 page를 삭제한다

void spt_remove_page(struct supplemental_page_table *spt, struct page *page)
{
    struct SPT_entry lookup;
    /* 내가 찾을 페이지의 가상 주소를 넣습니다 */
    lookup.va = page->va;
    /* SPT_hash_list에서 해당 가상 주소를 가진 엔트리를 제거합니다 */
    struct hash_elem *delete_elem = hash_delete(&spt->SPT_hash_list, &lookup.elem);
    if (delete_elem == NULL)
        return;
    struct SPT_entry *deleted = hash_entry(delete_elem, struct SPT_entry, elem);

    /* 페이지 테이블에서 해당 가상 페이지 삭제 */
    pml4_clear_page(thread_current()->pml4, page->va);
    vm_dealloc_page(page);

    /* 내부 페이지의 요소가 모두 free 된 이후 SPT_entry free */
    free(deleted);
    return true;
}

hash_find를 사용할 때와 같이 더미 엔트리를 만들어서 찾을 값을 넣어줘야 한다

hash_delete를 사용해서 찾은 hash_elem이 null이라면 애초에 SPT에 존재하지 않았다는 뜻이므로 바로 리턴해준다

SPT에 존재한다면 hash_entry를 사용해서 실제 엔트리를 찾고, 이를 이용해서 페이지 테이블에서 그 가상 페이지를 삭제해준다

이후 vm_delloc_page를 이용해서 해당 페이지의 operation에 있는 destroy를 호출한다

이후에는 페이지의 타입에 따라 다른 destory 함수를 호출할 것이다

마지막으로 SPT_entry는 어디에선가 동적으로 할당받은 구조체이므로 free를 진행해줘 누수를 막는다

supplemental_page_table_copy

spt 페이지 자체를 모두 카피하는 함수. __do_fork 함수 내부에서 호출된다. fork 시에 자식 프로세스에게 부모 프로세스의 모든 정보를 넘겨야 하기에 만들어둔듯 하다

bool supplemental_page_table_copy(struct supplemental_page_table *dst UNUSED, struct supplemental_page_table *src UNUSED)
{
   struct hash_iterator i;
   hash_first(&i, &src->SPT_hash_list);
   struct thread *cur = thread_current();

   while (hash_next(&i))
   {
      // src_page 정보
      struct SPT_entry *src_entry = hash_entry(hash_cur(&i), struct SPT_entry, elem);
      struct page *src_page = src_entry->page;
      enum vm_type type = src_page->operations->type;
      void *upage = src_page->va;
      bool writable = src_page->writable;

      /* 1) type이 uninit이면 */
      if (type == VM_UNINIT)
      { // uninit page 생성 & 초기화
         vm_initializer *init = src_page->uninit.init;
         void *aux = duplicate_aux(src_page);
         vm_alloc_page_with_initializer(VM_ANON, upage, writable, init, aux);
         continue;
      }

      /* 2) type이 file-backed이면 */
      if (type == VM_FILE)
      {
         struct file_page *src_info = &src_page->file;
         struct lazy_load_info *info = make_info(file_reopen(src_info->file), src_info->offset, src_info->read_byte);
         struct mmap_info *mmap_info = make_mmap_info(info, src_info->mapping_count);
         void *aux = mmap_info;

         if (!vm_alloc_page_with_initializer(type, upage, writable, lazy_load_segment, aux))
            return false;

         if (!vm_claim_page(upage))
            return false;

         continue;
      }

      /* 3) type이 anon이면 */
      if (!vm_alloc_page_with_initializer(type, upage, writable, NULL, NULL)) // uninit page 생성 & 초기화
         return false;

      // vm_claim_page으로 요청해서 매핑 & 페이지 타입에 맞게 초기화
      if (!vm_page(upage))
         return false;

      // 매핑된 프레임에 내용 로딩
      struct page *dst_page = spt_find_page(dst, upage);
      memcpy(dst_page->frame->kva, src_page->frame->kva, PGSIZE);
   }
   return true;
}

복사를 할 때는 SPT에 있는 모든 엔트리를 복사해와야 한다. SPT에 있는 엔트리들은 미초기화 페이지, 파일 페이지, 익명 페이지 셋 중 하나다. 따라서 세 페이지에 맞는 로직을 작성해주어야 한다.

 

먼저, 미초기화 페이지는 aux에 이 페이지가 초기화될 때 로드될 정보들이 있다. 절대 이 aux의 주소만 넘겨주어선 안된다 !!

그러면 자식 프로세스가 죽으면서 부모와 같이 공유하는 aux를 free 해버리는 대참사가 생길 수 있다.

나는 duplicate_aux 라는 함수를 만들어서 내부의 내용을 전부 복사하여 넘겨주도록 하였다.

코드 내용은 더보기에

더보기 
static void *duplicate_aux(struct page *src_page)
{
   if (src_page->uninit.type == VM_MMAP)
   {
      struct mmap_info *src_mmap_info = (struct mmap_info *)src_page->uninit.aux;
      struct lazy_load_info *src_info = (struct lazy_load_info *)src_mmap_info->info;

      struct mmap_info *dst_mmap_info = malloc(sizeof(struct mmap_info));
      struct lazy_load_info *dst_info = malloc(sizeof(struct lazy_load_info));

      dst_info->file = file_reopen(src_info->file);
      dst_info->offset = src_info->offset;
      dst_info->readbyte = src_info->readbyte;
      dst_info->zerobyte = src_info->zerobyte;

      dst_mmap_info->mapping_count = src_mmap_info->mapping_count;
      dst_mmap_info->info = dst_info;

      return dst_mmap_info;
   }
   else
   {
      struct lazy_load_info *src_info = (struct lazy_load_info *)src_page->uninit.aux;
      struct lazy_load_info *dst_info = malloc(sizeof(struct lazy_load_info));

      dst_info->file = file_reopen(src_info->file);
      dst_info->offset = src_info->offset;
      dst_info->readbyte = src_info->readbyte;
      dst_info->zerobyte = src_info->zerobyte;

      return dst_info;
   }
}

타입이 VM_MMAP 일 때와 아닐 때로 구분했는데, mmap의 경우 mmaping_count라는 특수한 필드가 필요하기 떄문이다. 사실 처음에는 mmap시에 생기는 페이지는 VM_FILE과 다른 타입으로 만들어질 것이라 생각했는데, 알고보니 mmap시에는 파일 페이지가 만들어지는 것이었다...

그리고 이미 파일 페이지나 익명 페이지로 초기화되었을 경우 두 가지로 나뉠 수 있는데, 파일 페이지를 복사할 경우에는 이 페이지가 초기화될 때 어느 파일에서 어느 오프셋부터 얼마만큼의 길이까지 복사해야하는지를 담은 메타데이터가 필요하므로 이 또한 복사해서 넘겨주어야 한다.

나는 make_info와 make_mmap_info 함수를 따로 만들어 사용하였다.

코드는 더보기에

더보기 
struct lazy_load_info *make_info(
	struct file *file, off_t offset, size_t read_byte)
{
	struct lazy_load_info *info = malloc(sizeof(struct lazy_load_info));
	info->file = file;
	info->offset = offset;
	info->readbyte = read_byte;
	info->zerobyte = PGSIZE - read_byte;
	return info;
}

struct mmap_info *make_mmap_info(struct lazy_load_info *info, int mapping_count)
{
	struct mmap_info *mmap_info = malloc(sizeof(struct mmap_info));
	mmap_info->info = info;
	mmap_info->mapping_count = mapping_count;
	return mmap_info;
}

사실 위에서 본 dulicate_aux와 역할이 살짝 겹치는것 같지만... 설계할때부터 이렇게 만들어버렸기 때문에 어쩔 수 없다... 여러분은 설계를 처음부터 잘 짜서 불필요한 함수가 없도록 만들어주자

이후 바로 초기화를 시켜주기 위해 vm_claim_page를 호출해 주었다.

 

그리고 마지막으로 익명 페이지의 경우는 초기화 될 때 uninit_page에 있는 aux를 통해 초기화되는데, 복사 시점에는 이미 초기화가 진행된 이후이므로 복사해올 aux가 존재하지 않는다. 그냥 VM_ANON타입으로 미초기화 페이지를 만들어주고 바로 vm_claim_page를 호출한 다음, memcpy로 부모의 미초기화 페이지에 있는 내용을 자식의 미초기화 페이지에 복사해주도록 하자.

 

upplemental_page_table_kill

SPT의 모든 엔트리를 제거하는 함수. process_cleanup에서 호출된다

void supplemental_page_table_kill(struct supplemental_page_table *spt UNUSED)
{
    /* TODO: 스레드가 보유한 모든 supplemental_page_table을 제거하고,
     * TODO: 수정된 내용을 스토리지에 기록(writeback)하세요. */
    struct thread *cur = thread_current();
    hash_destroy(&spt->SPT_hash_list, hash_spt_entry_kill);
}

이 함수 자체는 별게 없다. hash_destory는 SPT_hash_list의 모든 엔트리에 hash_spt_entry_kill 함수를 적용해준다. 이후 hash 내부의 버킷에도 free를 진행해주어 더이상 재사용을 못하게 해준다

그럼 hash_spt_entry_kill 함수를 보자. 이 함수는 우리가 직접 구현해주어야 하는 함수다

static void hash_spt_entry_kill(struct hash_elem *e, void *aux)
{
    struct SPT_entry *entry = hash_entry(e, struct SPT_entry, elem);
    /** spt_remove_page는 내부적으로 vm_delloc_page를 호출하고,
     * vm_delloc_page는 내부적으로 destroy 매크로를 호출한 다음
     * free(page)를 진행합니다.
     * 따라서 페이지의 타입에 따라 다른 destory 함수가 호출될 것으로 기대됩니다.
     */
    spt_remove_page(&thread_current()->spt, entry->page);
}

이 함수도 뭐... e를 통해 찾은 엔트리의 페이지를 spt_remove_page를 통해 모두 삭제해준다. 주석에 설명을 꼼꼼히 적어두었으니 참고 바란다.

 

이것만으로 설명이 부족하다면 우리의 팀 레포 링크를 올려둘테니 참고하고 도움이 되었다면 스타 하나만 달아다오...

https://github.com/Week12-13-GOAT/pintos-vm

 

GitHub - Week12-13-GOAT/pintos-vm: 미니준혁이에게 짬때리는 레포

미니준혁이에게 짬때리는 레포. Contribute to Week12-13-GOAT/pintos-vm development by creating an account on GitHub.

github.com

 

정소민fan
@정소민fan :: 코딩은 관성이야

코딩은 관성적으로 해야합니다 즐거운 코딩 되세요

목차

    티스토리툴바