Swap In/Out

swap in/out...

이 코드는 나는 에러때문에 돌아가지 않지만,
돌아가는 다른 사람의 코드도 에러가 뜨기 때문에,
나의 코드의 다른 곳에서 문제인 것같다...

또 정말 안 되어 완전히 다른 사람 코드로 바꾸었기때문에
내가 어떻게 구현했는지 말은 하겠지만...
.....
그렇다.

아무튼 swap의 골자는 이렇다.

내가 용량 부족해 -> 아무 페이지를 다른 곳에 데이터를 그대로 옮겨놓는다(swap out)-> 걔가 자리 차지하던 공간을 쓴다

아까 걔 어디갔어? -> 표시해놓은 곳에 데이터를 가져온다(swap in) -> 내가 찾던 애와 백년해로한다.

그래서 swap in, swap out에 빠지는 부분은 동일하지만
page 타입에 따라 데이터를 어디에다 적재했다가 다시 가져올지가 갈린다.

anon은 디스크 내 swap disk라는 공간에,
file backed은 디스크 내 본래 있던 file을 이용한다.

anon, file 순서로 보되
일단 swap in, out 자체가 언제 일어나는지 확인해보자.

swap out이 일어나는 지점

swap out은
내가 더 이상 기존 메모리에서 공간을 할당받을 수 없을 때 일어난다.

즉, palloc을 했지만 NULL이 반환되는 상황 이라고 할수 있다.

언제 palloc을 하는지 기억 나는가?
맞다, page에서 get frame 당시,
frame 안의 kva를 배정할때 썼었다.

그때 아마 PANIC으로 설정했을 것이다.
이제는, 거기에 새로운 frame을 배정해주는 함수를 넣어준다.

vm get frame

본래는 palloc으로
frame을 Init 시켜 frame을 return 해주는 함수다.

그러나, 넣을 kva가 null이라면
vm evict frame으로 빠지게 해준다.
(vm에서 희생자가 될 frame을 가져오는 함수다!)

static struct frame *
vm_get_frame (void) {
	struct frame *frame = NULL;
	void *pg_ptr = palloc_get_page(PAL_USER);
	if (pg_ptr == NULL)
	{
		return vm_evict_frame();
	}

	frame = (struct frame *)malloc(sizeof(struct frame));
	frame->kva = pg_ptr;
	frame->page = NULL;

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

vm evict frame

이 단계에서는
희생자가 될 fraem을 이미 vm get victim으로 가져왔다고 가정하고

swap out 시켜, 원래의 데이터는
해당 페이지의 방식대로 다른 곳에 저장해둔뒤,

여기서는 추가로 kva 안의 공간이 오염되었을 가능성을 염려해
0으로 모조리 memset을 해주고있다...

(근데 아마 다른 사람의 코드니 단순히 그런 이유보단
혹시? 여러 프로세스가? 다른 frame의 접근할수 있다면?
memset 해주는게 맞긴 한데(Protection목적으로)
자기 process면 정말 혹시 모를 오염...정도일듯.)

(일단 내 생각엔 필수는 아님.)

static struct frame *
vm_evict_frame (void) {

	struct frame *victim = vm_get_victim();
  if (!swap_out(victim->page)){
    return NULL;
  }

  	victim->page = NULL;
  	memset(victim->kva, 0, PGSIZE);

	return victim;
}

vm get victim

이곳에선 LRU 방식으로 구현하고 있다.
내 방식이 안 되어 복붙했었고

확실히 이 부분 복붙하니까
모든 코드가 안되는 에러지점에 도달했던거같다
(즉 코드 자체가 돌아가긴했다는 뜻...내 코드적 문제가 있을뿐.)

최대한 흉내내어 내가 썼던 코드는 안되고
복붙되니 되었던건 정말 아직까지 봐도 차이점을 모르겠지만
뭐 오타가 있었나보지...

아무튼...

처음 쓸 당시에는 확실히 몰랐지만
지금은 대강 안다.

관리를 어떻게 하냐면...

• 모든 frame을 frame list에 관리한다.
• 그래서 희생자 frame을 고를 때, 이 frame list를 순회한다.
  여기서는 LRU, 마지막으로 사용된 frame으로,
  pml4 accessed로 접근한 것을 판단하고 있다.
  (fifo로 하고 싶다면 그냥 어디서부터 넣고 뽑냐 정도 겠지.)
• 세부적으로는
  1.accessed 된 거라면 -> 안되었다고 리셋, 뽑아서 맨 뒤에 다시 넣음.
  2.accessed 안 되었고 희생자가 아직 없다면 -> 희생자로 선택. 뽑음.
  그렇게 list 맨 끝까지 accessed 여부는 쭉 리셋.
  3.만약 전부 accessed라 희생자를 못 골랐다면 -> 맨 앞애를 희생자로.

어차피 2번에서 list move해서
헉!! 영원히 포함 안되는건가요 하고 걱정할 수 있지만
claim page 등 단계를 타면서 list에 포함되는 부분을...

그러니까 frame 자체가 어차피 frame list 에 관리되기 위해
포함되는 부분에서 다시 포함되므로 괜찮다!

static struct frame *
vm_get_victim (void) {
 struct frame *victim = NULL;

  lock_acquire(&swap_lock);
  size_t swap_len = list_size(&swap);
  struct list_elem *tmp = list_begin(&swap);
  struct frame *tmp_frame;
  struct list_elem *next_tmp;
  for (size_t i = 0; i < swap_len; i++)
  {
    tmp_frame = list_entry(tmp, struct frame, frame_elem);
    if (pml4_is_accessed(thread_current()->pml4, tmp_frame->page->va))
    {
      pml4_set_accessed(thread_current()->pml4, tmp_frame->page->va, false);
      next_tmp = list_next(tmp);
      list_remove(tmp);
      list_push_back(&swap, tmp);
      tmp = next_tmp;
      continue;
    }
    if (victim == NULL)
    { 
      victim = tmp_frame;
      next_tmp = list_next(tmp);
      list_remove(tmp);
      tmp = next_tmp;
      continue;
    }
    tmp = list_next(tmp);
  }
  if (victim == NULL)
    victim = list_entry(list_pop_front(&swap), struct frame, frame_elem);
  lock_release(&swap_lock);
  return victim;
}

VM_ANON 타입 swap

그렇게.... anon 타입의 page를 다루게 된다.

anon 타입은 swap disk에 데이터를 저장했다가 가져오기 때문에,
swap disk를 써야하고, disk 관련 함수를 쓰게 된다.

disk.c 파일을 전반적으로 확인하는게 좋으며,
여기서 확인하게 되는건...

• sector 마다 크기는 512 바이트
  PGSIZE의 8분의 1이기때문에, sector 8개를 쓰면 page 1개분을 관리 가능.
• disk의 총 바이트는 60480? 인가 아무튼 어떤 것이든 disk_size 함수로 측정 가능. 512로 나누면 sector의 갯수를, 4096으로 나누면 page 갯수를 얻을 수 있음.

대개 방법은 두 가지인데

• 8개의 sector를 하나로 보고 bit 1개로 책정
• sector 하나당 1개의 bit로 책정

하여 disk size를 구해,
disk size와 잘 협의해서 bit의 갯수를 정해
그 크기에 맞는 bitmap을 create한다면,

bitmap scan이라는 함수 자체가
원하는 갯수만큼 연속적인 비트를 찾아서
맨 앞 인덱스를 주기때문에

bitmap을 8개 찾든, 1개 찾든,
아무튼...
(그러니까 sector별로 bit를 설정한다면 8개씩 찾아야할거고)
(page 별로 bit를 설정한다면 1개씩 찾아야할 거다.)
(용량은 일정하니 sector 별이 page 별보다 bit 갯수가 많겠지.)

그래서 anon init 시 그에 따라 이렇게 설정한다.

vm anon init

void
vm_anon_init (void) {
    swap_disk = disk_get(1,1); // swap disk 
	swap_bit =  bitmap_create((size_t)disk_size(swap_disk));
	lock_init(&swap_lock);
}

swap disk를 왜 1, 1로 get하냐면
disk 가 00 01 10 11이 있는데 11이 swap disk라고 하고 있다.
여기서는 swap disk의 size 만큼 swap bit를 만들고 있다.

anon swap out

...

깃북에서는 swap out이 일어난 직후에야 swap in이 일어나니
swap out을 먼저 짤 것을 권유하고 있다.

swap out의 순서는 이렇다.

• bitmap에서 free된 부분을 찾는다.
• 그 sector에 disk write을 한다.
• 기존 매핑을 해제하고, dirty bit를 초기화한다.

다시 찾을수 있게 기존 page 구조체에 어느 sector에 썼는지 잘 기재하는게 중요하다.

아래에서는 아예 page의 anon page에
swap idx에 시작 idx를 저장하고 있다. (그래서 아래의 anon initializer도 이를 고려해야한다.)

static bool
anon_swap_out (struct page *page) {
    struct anon_page *anon_page = &page->anon;

    lock_acquire(&swap_lock);
    disk_sector_t sec_no = (disk_sector_t)bitmap_scan_and_flip(swap_bit, 0, 8, false);
    lock_release(&swap_lock);
    if (sec_no == BITMAP_ERROR)
        return false;

    anon_page->swap_idx = sec_no;

    for (int i = 0; i < 8; i++)
    {
        disk_write(swap_disk, sec_no + i, page->frame->kva + i * DISK_SECTOR_SIZE);
    }

    pml4_clear_page(anon_page->thread->pml4, page->va);
    pml4_set_dirty(anon_page->thread->pml4, page->va, false);
    page->frame = NULL;

    return true;
    }

disk write 시
disk는 반드시 sector 만큼 분리되어있으니

다음 sector로 넘어가는 것,
kva에서 주소를 write한 만큼 이동하는 것을

계산이 잘 되도록 유의하자.

나의 경우는

• lock 까지 고려하진 않았음.
• dirty bit를 초기화해주지 않았음.
• pml4를 clear 해주는 것을 고려하지 않았음.

흠
dirty bit는 아직 고려하지 못했었고
pml4도... 애초에 나는 첫 구현에서는
swe라고 frame을 list로 관리하지 않고
frame 안에 swe 라고 swap table entry라며
구조체 선언해서 frame 가리키는 포인터...로

아예 새로운 노드로 썼었는데

이 과정에서 해봤던게

• frame을 그냥 희생자로 선정해서 새로 Init해서 넘기지 않고, kva부분만 palloc free 해서 냅두고 frame을 새로 malloc 시키고 kva를 새로 palloc 할 경우 뭔가 안됨.
• swe라고 swap table entry 라고 구조체 만들어서 page, frame을 둘다 저장하여, 1. swap slot 가능한 갯수만큼 malloc 해서 그때 그때 swap 된 애만 기록. 2. swap 이 일어났을때만 swap slot을 만들어서 추가.
  라는 방식으로 frame table이 아니라 swap list로 swap table entry를 넣어 관리하려고 했는데 당연히 그렇기때문에 list 관련 함수나 list entry함수등을 쓰면서 할때 주소가 잘못 나올때가 많아서 때려치고 frame 안에 elem 구조체 추가해서 관리하기 시작함.....ㅠ

슬프다..
나에게도 열정이 있던 시기가 있었지...

근데 아직도 전자와 후자가 안 되는 이유를 잘 모르겠지만
복합적인 이유가 있긴 하겠지 git에는 commit으로 남아있겠지만.

anon initializer

swap index를 초기화해주는 모습.
또 어느 thread인지 알아야 pml4자체를 조정할수 있기때문에 추가해줘야한다.
(thread 단위로 pml4가 있으니까.)

bool
anon_initializer (struct page *page, enum vm_type type, void *kva) {
	/* Set up the handler */
	struct uninit_page *uninit = &page->uninit;
	memset(uninit, 0, sizeof(struct uninit_page));

	page->operations = &anon_ops;

	struct anon_page *anon_page = &page->anon;
	anon_page->swap_idx = UINT32_MAX;
	anon_page->thread = thread_current();

	return true;
}

anon swap in

이후 swap in을 한다.
anon page에 index가 잘 있는지 확인하고

disk에서 그 시작 index부터 8번 읽어
disk read를 전개하고

bitmap을 다시 원래로 돌려준다.

static bool
anon_swap_in (struct page *page, void *kva) {
    struct anon_page *anon_page = &page->anon;

    if (anon_page->swap_idx == SIZE_MAX)
        return false;

    lock_acquire(&swap_lock);
    bool check = bitmap_contains(swap_bit, anon_page->swap_idx, 8, false);
    lock_release(&swap_lock);
    if (check)
    {
        return false;
    }

    for (int i = 0; i < 8; i++)
    {
        disk_read(swap_disk, anon_page->swap_idx + i, kva + i * DISK_SECTOR_SIZE);
    }

    lock_acquire(&swap_lock);
    bitmap_set_multiple(swap_bit, anon_page->swap_idx, 8, false);
    lock_release(&swap_lock);

    return true;

}

anon destroy

이후 destroy도
frame 도 list에서 제해주고
bitmap도 리셋 시켜준다.

static void
anon_destroy (struct page *page) {
	struct anon_page *anon_page = &page->anon;

if (page->frame != NULL)
    {
        lock_acquire(&swap_lock);
        list_remove(&page->frame->frame_elem);
        lock_release(&swap_lock);
 
        free(page->frame);
    }
    if (anon_page->swap_idx != SIZE_MAX)
        bitmap_set_multiple(swap_bit, anon_page->swap_idx, 8, false);
}

...

file backed swap

file swap in, out은
거의 mmap, munmap과 유사하다.

VM_FILE은 애초에 page에 aux로 관련 구조체를 할당받았으므로
거기서 가져와 하기만 하면 된다.

file back swap out 시에는 file에 쓰고,
swap int시에는 file read를 하면 된다.

destroy는 애초에 mmap 시 구현하였을 것이므로 생략.

file backed initilaizer

bool
file_backed_initializer (struct page *page, enum vm_type type, void *kva) {
	/* Set up the handler */
	page->operations = &file_ops;

	struct file_page *file_page = &page->file;
	struct page_load_data *aux = (struct page_load_data *) page->uninit.aux;
	file_page->file = aux->file;
	file_page->ofs = aux->ofs;
	file_page->read_bytes = aux->read_bytes;
	file_page->zero_bytes = aux->zero_bytes;
}

file backed swap in

static bool
file_backed_swap_in (struct page *page, void *kva) {
	struct file_page *file_page UNUSED = &page->file;

	struct page_load_data *aux_d = (struct page_load_data *)(page->uninit.aux);

	file_seek(aux_d->file, aux_d->ofs);

	if(file_read(aux_d->file, kva, aux_d->read_bytes) != (int)aux_d->read_bytes){
		palloc_free_page(page->frame->kva);
	return false;
	}
	memset((page->frame->kva)+(aux_d->read_bytes), 0, aux_d->zero_bytes);

	return true;

}

file backed swap out

static bool
file_backed_swap_out (struct page *page) {
	struct file_page *file_page UNUSED = &page->file;
	
	if(page == NULL){
		return false;
	}

	struct page_load_data *aux_d = (struct page_load_data *)page->uninit.aux;

	if(pml4_is_dirty(thread_current()->pml4, page->va)){
		file_write_at(aux_d->file, page->va, aux_d->read_bytes, aux_d->ofs);
		pml4_set_dirty(thread_current()->pml4, page->va, 0);
	}

	pml4_clear_page(thread_current()->pml4, page->va);

}

file backed destroy

static void
file_backed_destroy (struct page *page) {
	struct file_page *file_page UNUSED = &page->file;

	if(pml4_is_dirty(thread_current()->pml4, page->va)){
		file_write_at(file_page->file, page->va, file_page->read_bytes, file_page->ofs);
		pml4_set_dirty(thread_current()->pml4, page->va, 0);
	}
	pml4_clear_page(thread_current()->pml4, page->va);
}

....

내 코드는 어디서부터가 문제인걸까
흠.....

아무튼 끝.