[SW정글] Week 10 개발일지

Week10 PintOS Virtual Memory

[ELF] ELF Header

[ELF] Segment와 Program Header

ELF

Executable and Linking Format

ELF header

• ELF file의 metadata를 가진 header

Segment

• segment마다 segment에 대한 metadata를 가진 program header를 가진다
  • LOAD Segment
    • pysical memory에 load할 수 있는 segment 
    • memory 속성에 따라 한 file 내에 다수의 LOAD segment가 있을 수 있다
    • (LOAD 이외의 다른 type의 segment는 참조 확인)
• 동일한 memory 속성(read-only, writable, …)을 가진 하나 또는 그 이상의 section의 집합

Section

• 특정 정보(machine instruction, symbol table, …)를 포함하고 있는 ELF file의 작은 조각

(이외의 다른 ELF 구성 요소는 참조 확인)

 

Lazy Load

disk의 내용을 pysical memory에 한번에 모두 올려두는 것이 아니라 실질적으로 실행될 때 pysical memory에 upload하는 방법

static bool
lazy_load_segment(struct page *page, void *aux)
{
	// aux로 전달 받은 file data
	struct file_info *file_info = (struct file_info *)aux;
	int page_read_bytes = file_info->page_read_bytes;

	// load해야할 부분으로 file ofs 변경
	file_seek(file_info->file, file_info->ofs);

	// laod segment
	if (file_read(file_info->file, page->frame->kva, page_read_bytes) != page_read_bytes)
		return false;

	// setup zero bytes space
	memset(page->frame->kva + page_read_bytes, 0, file_info->page_zero_bytes);

	return true;
}

static bool
load_segment(struct file *file, off_t ofs, uint8_t *upage,
			 uint32_t read_bytes, uint32_t zero_bytes, bool writable)
{
	ASSERT((read_bytes + zero_bytes) % PGSIZE == 0);
	ASSERT(pg_ofs(upage) == 0);
	ASSERT(ofs % PGSIZE == 0);

	// read_bytes와 zero_bytes가 모두 0일 때 = 현재 laod segment에 모두 page 할당을 했을 때
	while (read_bytes > 0 || zero_bytes > 0)
	{
		size_t page_read_bytes = read_bytes < PGSIZE ? read_bytes : PGSIZE;
		size_t page_zero_bytes = PGSIZE - page_read_bytes;

		/* aux를 통해 file data 전달을 위해 만든 struct file_info */
		struct file_info *file_info = (struct file_info *)malloc(sizeof(struct file_info));

		file_info->file = file;
		file_info->ofs = ofs;
		file_info->page_read_bytes = page_read_bytes;
		file_info->page_zero_bytes = page_zero_bytes;

		/*
		해당 virtual memory(=upage)에 struct page를 할당해줌
		load 되기 전에는 uninit page

		page fault로 pysical memory로 load될 때 할당될 때 입력 받은 page type으로 변환하고
		lazy_load_segment 함수를 실행시켜서 upload함
		*/
		if (!vm_alloc_page_with_initializer(VM_ANON, upage, writable, lazy_load_segment, file_info))
			return false
		read_bytes -= page_read_bytes; // 남은 read_bytes 갱신
		zero_bytes -= page_zero_bytes; // 남은 zero_bytes 갱신
		upage += PGSIZE;			   // virtual address를 옮겨서 다음 page space를 가리키게 함
		ofs += PGSIZE;				   // 다음 page에 mapping시킬 file 위치 갱신
	}
	return true;
}

NULL address 접근이 들어와서 종료되었다

해결

• read_bytes와 zero_bytes와 upage는 계속 갱신이 되서는 와중에 file ofs을 옮겨주지 않아서 page space와 struct page는 제대로 mapping이 됬지만 모든 page가 segment의 처음 PGSIZE 부분을 mapping 했다 마지막 page는 zero_bytes가 있어서 segment의 첫 부분을 일부만 읽어오고 뒷부분을 0으로 초기화 한다
• 그 초기화한 부분에 접근하려고 보니 NULL address 접근이 일어났다
• ofs += PGSIZE 추가해서 file ofs을 갱신시켜 주니 해결

static bool
setup_stack(struct intr_frame *if_)
{
	struct thread *curr = thread_current();

	/*
	stack은 위에서 아래로 커진다
	stack의 시작 위치는 USER_STACK
	PGSIZE만큼 빼서 page space 확보 -> 해당 page 시작 virtual address = stack_botton
	*/
	void *stack_bottom = (void *)(((uint8_t *)USER_STACK) - PGSIZE);

	// 확보한 page space에 struct page 할당
	if (!vm_alloc_page_with_initializer(VM_ANON, stack_bottom, true, NULL, NULL))
		return false;

	// page를 pysical memory에 바로 올림 -> 바로 argument들을 stack에 쌓아야하기 때문에
	//lazy load할 필요 없음
	if (!vm_claim_page(stack_bottom))
		return false;

	// stack pointer 설정
	if_->rsp = USER_STACK;

	return true;
}

 

SPT copy, kill

spt copy

새로운 struct page를 만들어서 자식의 spt에 추가

 

vm_alloc_page with initializer()

anon, file page는 struct page 복사한 후에 바로 pysical memory에 mapping

→ 부모 page의 pysical memory 내용을 복사한 자식 page의 pysical memory에 memcpy()

 

vm_alloc_page()

만들어진 uninit page가 바로 anon or file page로 변경

uninit page는 lazy load를 위해 lazy_load_segment function pointer와 aux를 전달

 

fork 실행할 때 부모의 spt를 자식에게로 복사

 

spt kill

내부에서 destroy를 실행해서 page type에 따라 member들 free

-> hash table 자체도 없애기 때문에 exec의 경우에는 spt_init을 다시 해줘야한다

 

spt에 있는 모든 struct page를 free하고 hash table도 삭제

→ hash_destroy()

 

process를 exit하거나 exec를 하기 전에 실행

 

Stack growth

user stack이 1mb의 크기까지 커질 수 있게 만들어야 함

user stack의 첫 page(0x4747f000 ~ 0x47480000)는 argument들을 넣어주기 위해 바로 pysical memory에 올린다

스택이 현재 page보다 커지면 다음 page에 대한 struct page를 만들고 spt에 넣어준다

/* user stack의 첫 page setting */
static bool
setup_stack(struct intr_frame *if_)
{
	struct thread *curr = thread_current();

	/*
	stack은 위에서 아래로 커진다
	stack의 시작 위치는 USER_STACK
	PGSIZE만큼 빼서 page space 확보 -> 해당 page 시작 virtual address = stack_botton
	*/
	void *stack_bottom = (void *)(((uint8_t *)USER_STACK) - PGSIZE);

	// 확보한 page space에 struct page 할당
	if (!vm_alloc_page_with_initializer(VM_ANON, stack_bottom, true, NULL, NULL))
		return false;

	// page를 pysical memory에 바로 올림 -> 바로 argument들을 stack에 쌓아야하기 때문에 lazy load할 필요 없음
	if (!vm_claim_page(stack_bottom))
		return false;

	// stack pointer 설정
	if_->rsp = USER_STACK;

	return true;
}

/* Growing the stack. */
static void
vm_stack_growth(void *addr)
{
	/* 이미 struct page가 있다면 skip */
	if (spt_find_page(&thread_current()->spt, addr))
		return;

	/* 새로운 space에 struct page를 만들어서 mapping */
	uintptr_t stack_bottom = pg_round_down(addr);
	vm_alloc_page(VM_ANON, stack_bottom, true);
}

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

	...

	/* stack growth */
	/*
	rsp는 user stack의 rsp이어야 한다
	user 영역에서의 page fault는 전달받은 if의 rsp를 사용하면 된다
	kernel 영역에서의 page fault는 전달받은 if의 rsp가 kernel stack의 rsp이기 때문에 사용할 수 없다
	이것을 대비하기 위해 user 영역에서 kernel 영역으로 넘어갈때마다
	user stack의 rsp를 따로 저장해둔다(struct thread)
	*/
	uintptr_t stack_limit = USER_STACK - (1 << 20);
	uintptr_t rsp = user ? f->rsp : thread_current()->user_rsp;

	/* 
	page fault를 발생시킨 address가 유효한 stack 영역이라면 stack growth
	1. addr >= rsp - 8
		x86-64에서 stack에 push할 때 8bytes 단위로 실행
		address 유효성 검사 후에 rsp를 옮기기 때문에 rsp - 8을 범위로 한다
	2. addr <= USER_STACK && addr >= stack_limit
		pintos에서 정해진 user stack 주소 영역
	*/
	if (addr >= rsp - 8 && addr <= USER_STACK && addr >= stack_limit)
		vm_stack_growth(addr);

	/* find page */
	struct page *page = spt_find_page(spt, addr);
	if (page == NULL)
		return false;

	...

	/* upload to pysical memory */
	succ = vm_do_claim_page(page);
	return succ;
}

Memory mapped files

static bool lazy_load_file(struct page *page, void *aux)
{
	// aux로 전달 받은 file data
	struct file_info *file_info = (struct file_info *)aux;

	page->file.file = file_info->file;
	page->file.length = file_info->page_read_bytes;
	page->file.offset = file_info->ofs;

	// struct file *file = file_info->file;
	// off_t ofs = file_info->ofs;
	// int page_read_bytes = file_info->page_read_bytes;
	int page_zero_bytes = file_info->page_zero_bytes;

	// load해야할 부분으로 file ofs 변경
	file_seek(page->file.file, page->file.offset);

	int temp;
	// laod segment
	if ((temp = file_read(page->file.file, page->frame->kva, page->file.length)) != page->file.length)
	{
		free(file_info);
		return false;
	}

	// setup zero bytes space
	memset(page->frame->kva + page->file.length, 0, page_zero_bytes);

	return true;
}

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

	struct mmap_file *mmap_file = (struct mmap_file *)malloc(sizeof(struct mmap_file));
	mmap_file->addr = addr;
	list_init(&mmap_file->page_list);
	list_push_back(&curr->mmap_list, &mmap_file->elem);

	mmap_file->file = file_reopen(file);
	if (mmap_file->file == NULL)
		return NULL;

	size_t read_bytes = length > file_length(mmap_file->file) ? file_length(mmap_file->file) : length;
	size_t zero_bytes = pg_round_up(read_bytes) - read_bytes;
	uintptr_t upage = addr;
	off_t ofs = offset;

	while (read_bytes > 0 || zero_bytes > 0)
	{
		size_t page_read_bytes = read_bytes < PGSIZE ? read_bytes : PGSIZE;
		size_t page_zero_bytes = PGSIZE - page_read_bytes;

		struct file_info *file_info = (struct file_info *)malloc(sizeof(struct file_info));

		file_info->file = mmap_file->file;
		file_info->ofs = ofs;
		file_info->page_read_bytes = page_read_bytes;
		file_info->page_zero_bytes = page_zero_bytes;

		if (!vm_alloc_page_with_initializer(VM_FILE, upage, writable, lazy_load_file, file_info))
			return false;

		struct page *page = spt_find_page(&curr->spt, upage);
		if (page == NULL)
			return false;

		list_push_back(&mmap_file->page_list, &page->mmap_elem);

		read_bytes -= page_read_bytes;
		zero_bytes -= page_zero_bytes;
		upage += PGSIZE;
		ofs += PGSIZE;
	}

	return addr;
}

static struct mmap_file *find_mmap_file(void *addr)
{
	struct thread *curr = thread_current();

	struct list_elem *temp_elem = list_begin(&curr->mmap_list);
	for (; temp_elem != list_tail(&curr->mmap_list); temp_elem = temp_elem->next)
	{
		struct mmap_file *temp_file = list_entry(temp_elem, struct mmap_file, elem);

		if (temp_file->addr == addr)
			return temp_file;
	}

	return NULL;
}

/* Do the munmap */
void do_munmap(void *addr)
{
	struct thread *curr = thread_current();
	struct mmap_file *mmap_file = find_mmap_file(addr);
	struct list_elem *temp_elem = list_begin(&mmap_file->page_list);

	for (; temp_elem != list_tail(&mmap_file->page_list);)
	{
		struct page *page = list_entry(temp_elem, struct page, mmap_elem);
		temp_elem = temp_elem->next;

		if (pml4_get_page(curr->pml4, page->va) == NULL)
			continue;

		if (pml4_is_dirty(curr->pml4, page->va))
		{
			file_write_at(mmap_file->file, page->va, page->file.length, page->file.offset);
			pml4_set_dirty(curr->pml4, page->va, 0);
		}

		pml4_clear_page(curr->pml4, page->va);
		spt_remove_page(&thread_current()->spt, page);
	}

	file_close(mmap_file->file);
	list_remove(&mmap_file->elem);
	free(mmap_file);

	return;
}

Swap in/out

 

void list_clock_next(struct list *l)
{
	clock_ptr = clock_ptr->next;
	if (list_tail(l) == clock_ptr)
		clock_ptr = list_begin(l);
}

/* Get the struct frame, that will be evicted. */
static struct frame *vm_get_victim(void)
{
	struct thread *curr = thread_current();
	struct frame *victim = NULL;
	/* TODO: The policy for eviction is up to you. */

	while (1)
	{
		list_clock_next(&frame_table);
		victim = list_entry(clock_ptr, struct frame, elem);

		if (pml4_is_accessed(victim->pml4, victim->page->va))
		{
			pml4_set_accessed(victim->pml4, victim->page->va, false);
			continue;
		}

		break;
	}

	return victim;
}

/* 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();

	swap_out(victim->page);

	struct page *page = victim->page;

	struct list_elem *temp_elem = list_begin(&victim->child_pages);
	for (; temp_elem != list_tail(&victim->child_pages); temp_elem = temp_elem->next)
	{
		struct page *temp_page = list_entry(temp_elem, struct page, cow_elem);

		temp_page->frame = NULL;
		pml4_clear_page(temp_page->pml4, temp_page->va);
	}

	return victim;
}

/* 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 = (struct frame *)malloc(sizeof(struct frame));
	if (frame == NULL)
		return NULL;

	frame->kva = palloc_get_page(PAL_USER);
	if (frame->kva)
		list_push_back(&frame_table, &frame->elem);
	else
		frame = vm_evict_frame();

	clock_ptr = &frame->elem;

	frame->page = NULL;
	frame->pml4 = NULL;
	frame->cow_cnt = 0;
	list_init(&frame->child_pages);

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

	return frame;
}

 

/* Swap in the page by read contents from the swap disk. */
static bool
anon_swap_in(struct page *page, void *kva)
{
	struct anon_page *anon_page = &page->anon;
	int page_no = anon_page->swap_idx;

	if (!bitmap_test(swap_table, page_no))
		return false;

	for (int i = 0; i < SECTORS_IN_PAGE; i++)
		disk_read(swap_disk, (page_no * SECTORS_IN_PAGE) + i, kva + (DISK_SECTOR_SIZE * i));

	bitmap_flip(swap_table, page_no);

	// printf("[DEBUG][anon][swap_in]%p\\n", page->va);
	return true;
}

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

	int page_no = bitmap_scan(swap_table, 0, 1, false);
	if (page_no == BITMAP_ERROR)
		return false;

	for (int i = 0; i < SECTORS_IN_PAGE; i++)
		disk_write(swap_disk, (page_no * SECTORS_IN_PAGE) + i, page->va + (DISK_SECTOR_SIZE * i));

	bitmap_flip(swap_table, page_no);

	anon_page->swap_idx = page_no;

	// printf("[DEBUG][anon][swap_out]%p\\n", page->va);
	return true;
}

 

/* Swap in the page by read contents from the file. */
static bool
file_backed_swap_in(struct page *page, void *kva)
{
	struct file_page *file_page = &page->file;

	if (file_read_at(file_page->file, kva, file_page->length, file_page->offset) != (int)file_page->length)
		return false;

	memset(kva + file_page->length, 0, PGSIZE - file_page->length);

	// printf("[DEBUG][file][swap _in]%p\\n", page->va);
	return true;
}

/* Swap out the page by writeback contents to the file. */
static bool
file_backed_swap_out(struct page *page)
{
	struct thread *curr = thread_current();
	struct file_page *file_page = &page->file;

	if (pml4_is_dirty(curr->pml4, page->va))
	{
		int check = file_write_at(file_page->file, page->frame->kva, file_page->length, file_page->offset);
		if (check != file_page->length)
			return false;

		pml4_set_dirty(curr->pml4, page->va, 0);
	}

	// printf("[DEBUG][file][swap_out]%p\\n", page->va);
	return true;
}

Copy on Write

/* Handle the fault on write_protected page */
static bool
vm_handle_wp(struct page *page UNUSED)
{
	struct thread *curr = thread_current();
	struct frame *old_frame = page->frame;

	/* unmap page-frame */
	page->frame = NULL;
	list_remove(&page->cow_elem);
	if (old_frame->page == page)
		old_frame->page = list_begin(&old_frame->child_pages);
	pml4_clear_page(curr->pml4, page->va);

	/* Set links */
	struct frame *new_frame = vm_get_frame();
	new_frame->page = page;
	page->frame = new_frame;

	if (!pml4_set_page(curr->pml4, page->va, new_frame->kva, page->writable))
		return false;

	/* initialize struct frame */
	new_frame->pml4 = curr->pml4;
	list_push_back(&new_frame->child_pages, &page->cow_elem);

	/* set pysical memory */
	memcpy(new_frame->kva, old_frame->kva, PGSIZE);

	/* manage cow */
	vm_down_cow_cnt(old_frame);

	return true;
}

/* Copy supplemental page table from src to dst */
bool supplemental_page_table_copy(struct supplemental_page_table *dst, struct supplemental_page_table *src)
{
	struct thread *curr = thread_current();
	struct hash_iterator i;
	struct hash *parent_hash = &src->table;

	hash_first(&i, parent_hash);
	while (hash_next(&i))
	{
		struct page *parent_page = hash_entry(hash_cur(&i), struct page, hash_elem);

		if (parent_page->operations->type == VM_UNINIT)
		{
			vm_initializer *init = parent_page->uninit.init;
			void *aux = parent_page->uninit.aux;

			vm_alloc_page_with_initializer(parent_page->uninit.type, parent_page->va, parent_page->writable, init, aux);
		}
		else
		{
			struct page *child_page = (struct page *)malloc(sizeof(struct page));
			memcpy(child_page, parent_page, sizeof(struct page));

			if (!spt_insert_page(dst, child_page))
				return false;

			if (!pml4_set_page(curr->pml4, child_page->va, child_page->frame->kva, false))
				return false;

			// pml4_clear_page(parent_page->pml4, parent_page->va);
			if (!pml4_set_page(parent_page->pml4, parent_page->va, parent_page->frame->kva, false))
				return false;

			list_push_back(&child_page->frame->child_pages, &child_page->cow_elem);

			child_page->frame->cow_cnt++;

			child_page->pml4 = curr->pml4;
		}
	}

	return true;
}

void hash_destructor(struct hash_elem *hash_elem, void *aux)
{
	struct page *page = hash_entry(hash_elem, struct page, hash_elem);
	struct frame *frame = page->frame;

	if (frame)
	{
		if (frame->cow_cnt == 0)
		{
			if (clock_ptr == &frame->elem)
				list_clock_next(&frame_table);
			list_remove(&frame->elem);

			palloc_free_page(frame->kva);
			free(frame);
		}
		else
		{
			list_remove(&page->cow_elem);
			vm_down_cow_cnt(frame);

			if (frame->page == page)
				frame->page = list_begin(&frame->child_pages);
		}
	}

	vm_dealloc_page(page);
}

void vm_down_cow_cnt(struct frame *frame)
{
	frame->cow_cnt--;

	if (frame->cow_cnt == 0)
	{
		struct list_elem *temp_elem = list_begin(&frame->child_pages);
		struct page *temp_page = list_entry(temp_elem, struct page, cow_elem);

		pml4_set_page(temp_page->pml4, temp_page->va, frame->kva, temp_page->writable);
	}
}