[pintos] Project 3_Virtual Memory(가상 메모리)

[pintos] Project 3_Virtual Memory(가상 메모리)

 

 Introduction 

 

 

 

 Memory Management 

 

Implement Supplemental Page Table

 

void supplemental_page_table_init (struct supplemental_page_table *spt);

 

supplemental page table을 initialization 한다.

new process start (initd of process.c)할 때나 process가 fork(__do_fork of process.c)할 때 실행된다.

 

//vm.c

void
supplemental_page_table_init (struct supplemental_page_table *spt) {
	struct hash* page_table = malloc(sizeof (struct hash));
	hash_init (page_table, page_hash, page_less, NULL);
	spt -> page_table = page_table;
}

// Functions for hash table
// page_hash = vm_hash_func
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.
// page_less = vm_less_func
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;
}


//vm.h

struct supplemental_page_table {
	struct hash pages;
};

unsigned
page_hash (const struct hash_elem *p_, void *aux UNUSED);
bool
page_less (const struct hash_elem *a_,
           const struct hash_elem *b_, void *aux UNUSED);

 

 

struct page *spt_find_page (struct supplemental_page_table *spt, void *va);

 

// vm.c

/* 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;
	// malloc을 해야 스레드 이름이 안없어진다.
	// Project 3.1_memory management
	struct page* page = (struct page)malloc(sizeof(struct page));
	/* TODO: Fill this function. */
	struct hash_elem *e;

	page->va = pg_round_down(va);
	e = hash(&spt->page_table, &page->hash_elem);
	free(page);
	return e != NULL ? hash_entry (e, struct page, hash_elem) : NULL;
	// return page;
	// Project 3.1_end
}

// vm.h

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

	/* Your implementation */

	// Project 3.1_memory management
	struct hash_elem hash_elem;	// 해시 테이블 element

	...
    ...
}

// vm.c
#include "vaddr.h" // pg_round_down()

 

 

bool spt_insert_page (struct supplemental_page_table *spt, struct page *page);

 

// vm.c

/* 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. */

	return insert_page(&spt->pages, page);
}

bool insert_page(struct hash *pages, struct page *p)
{
	if (!hash_insert(pages, &p->hash_elem))
		return true;
	else
		return false;
}

// vm.h

bool insert_page(struct hash *pages, struct page *p);

 

 

Frame Management

 

static struct frame *vm_get_frame (void);

 

//vm.c

struct list frame_table;

static struct frame *
vm_get_frame (void) {
	// struct frame *frame = NULL;
	// projec 3.1_memory management
	struct frame *frame = (struct frame*)malloc(sizeof(struct frame));
	/* TODO: Fill this function. */
	frame->kva = palloc_get_page(PAL_USER);
	if(frame->kva == NULL)
	{
		frame = vm_evict_frame();
		frame->page = NULL;
		return frame;
	}
	list_push_back(&frame_table, &frame->frame_elem);

	frame->page = NULL;

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

// vm.h

struct frame {
	void *kva;
	struct page *page;
	struct list_elem frame_elem;
};

 

bool vm_do_claim_page (struct page *page);

 

// vm.c

/* 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. */

	if(install_page(page->va, frame->kva, page->writable))
	{
		return swap_in(page, frame->kva);
	}
	return false;
}

// vm.h

struct page {
	...
	/* Your implementation */

	bool writable;	/* True일경우해당주소에write 가능 False일경우해당주소에write 불가능*/
	struct hash_elem hash_elem;	// 해시 테이블 element
    ...
}

 

bool vm_claim_page (void *va);

 

// vm.c

bool
vm_claim_page (void *va UNUSED) {
	// struct page *page = NULL;
	struct page *page;
	/* TODO: Fill this function */

	page = spt_find_page(&thread_current()->spt, va);
	if (page == NULL)
		return false;
	return vm_do_claim_page (page);
}

// process.c

#ifdef VM
	...
#else
/* From here, codes will be used after project 3.
 * If you want to implement the function for only project 2, implement it on the
 * upper block. */

bool
install_page (void *upage, void *kpage, bool writable){
	struct thread *t = thread_current ();

	return (pml4_get_page (t->pml4, upage)== NULL
			&& pml4_set_page (t->pml4, upage, kpage, writable));
}

// process.h
bool install_page (void *upage, void *kpage, bool writable);

 

기타

 

// vm.c

/* Handle the fault on write_protected page */
static bool
vm_handle_wp (struct page *page UNUSED) {
}

/* Return true on success */
// page fault 발생시 핸들링을 위해 호출 되는 함수
bool
vm_try_handle_fault (struct intr_frame *f UNUSED, void *addr UNUSED,
		bool user UNUSED, bool write UNUSED, bool not_present UNUSED) {
	struct supplemental_page_table *spt UNUSED = &thread_current ()->spt;
	struct page *page = NULL;
	/* TODO: Validate the fault */
	/* TODO: Your code goes here */

	if(is_kernel_vaddr(addr))
	{
		return false;
	}

	if (not_present){
		if(!vm_claim_page(addr))
		{
			return false;
		}
		else
			return true;
	}
	return false

	// return vm_do_claim_page (page);
}

// thread.h

struct thread
{
...
#ifdef VM
	/* Table for whole virtual memory owned by thread. */
	struct supplemental_page_table spt; // vm is in spt
	void* rsp_stack; // stack grow 할 때 사용
	void* stack_bottom;
#endif
...
}

// process.c

int
process_exec (void *f_name) {
	...
	process_cleanup();
    #ifdef VM
    supplemental_page_table_init(&thread_current()->spt);
    #endif
	...
}

 

 Anonymous Page 

 

Lazy Loading for Excutable

 

void vm_init(void)

 

// vm.c

struct list_elem* start;

/* Initializes the virtual memory subsystem by invoking each subsystem's
 * intialize codes. */
void
vm_init (void) {
	vm_anon_init ();
	vm_file_init ();
#ifdef EFILESYS  /* For project 4 */
	pagecache_init ();
#endif
	register_inspect_intr ();
	/* DO NOT MODIFY UPPER LINES. */
	/* TODO: Your code goes here. */
	list_init(&frame_table);
	start = list_begin(&frame_table);
}

 

bool vm_alloc_page_with_initializer (enum vm_type type, void *va, bool writable, vm_initializer *init, void *aux);

 

/* Create the pending page object with initializer. If you want to create a
 * page, do not create it directly and make it through this function or
 * `vm_alloc_page`. */
bool
vm_alloc_page_with_initializer (enum vm_type type, void *upage, bool writable,
		vm_initializer *init, void *aux) {

	ASSERT (VM_TYPE(type) != VM_UNINIT)

	struct supplemental_page_table *spt = &thread_current ()->spt;

	/* Check wheter the upage is already occupied or not. */
	if (spt_find_page (spt, upage) == NULL) {
		/* TODO: Create the page, fetch the initialier according to the VM type,
		 * TODO: and then create "uninit" page struct by calling uninit_new. You
		 * TODO: should modify the field after calling the uninit_new. */
		/* TODO: Insert the page into the spt. */
		
		struct page* page = (struct page*)malloc(sizeof(struct page));

		typedef bool (*initializerFunc)(struct page *, enum vm_type, void *);
		initializerFunc initializer = NULL;
		
		switch(VM_TPYE(type)){
			case VM_ANON:
				initializer = anon_initializer;
				break;
			case VM_FILE:
				initializer = file_backed_initializer;
				break;
		}

		uninit_new(page, upage, init, type, aux, initializer);

		// page member 초기화
		page->writable = writable;

		// hex_dump(page->va, page->va, PGSIZE, true);
		return spt_insert_page(spt,page);
	}
err:
	return false;
}

 

static bool uninit_initialize (struct page *page, void *kva);

- 변경 x

 

void vm_anon_init (void);

 

// anon.c

#include "threads/vaddr.h"

struct bitmap *swap_table;
const size_t SECTORS_PER_PAGE = PGSIZE / DISK_SECTOR_SIZE;

/* Initialize the data for anonymous pages */
void
vm_anon_init (void) {
	/* TODO: Set up the swap_disk. */

	// swap_disk = NULL;
	swap_disk = disk_get(1,1);
	size_t swap_size = disk_size(swap_disk) / SECTORS_PER_PAGE;
	swap_table = bitmap_create(swap_size);
}

 

bool anon_initializer (struct page *page,enum vm_type type, void *kva);

- 변경 x

 

static bool load_segment (struct file *file, off_t ofs, uint8_t *upage, uint32_t read_bytes, uint32_t zero_bytes, bool writable);

 

 

// process.c

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

	while (read_bytes > 0 || zero_bytes > 0) {
		/* Do calculate how to fill this page.
		 * We will read PAGE_READ_BYTES bytes from FILE
		 * and zero the final PAGE_ZERO_BYTES bytes. */
		size_t page_read_bytes = read_bytes < PGSIZE ? read_bytes : PGSIZE;
		size_t page_zero_bytes = PGSIZE - page_read_bytes;
	
		/* TODO: Set up aux to pass information to the lazy_load_segment. */
		// Project 3.2_anonymous page
		struct box *box = (struct box*)malloc(sizeof(struct box));

		box->file = file;
		box->ofs = ofs;
		box->page_read_bytes = page_read_bytes;
		// Project 3.2_end
		// void *aux = NULL;
		if (!vm_alloc_page_with_initializer (VM_ANON, upage,
					writable, lazy_load_segment, aux))
			return false;

		/* Advance. */
		read_bytes -= page_read_bytes;
		zero_bytes -= page_zero_bytes;
		upage += PGSIZE;
		// Project 3.2_anonymous page
		ofs += page_read_bytes;
		// Project 3.2_end
	}
	return true;
}

 

static bool lazy_load_segment (struct page *page, void *aux);

 

// process.c

#ifndef VN
	load_segment
    ...
#else // VM 있을 때

static bool
lazy_load_segment (struct page *page, void *aux) {
	/* TODO: Load the segment from the file */
	/* TODO: This called when the first page fault occurs on address VA. */
	/* TODO: VA is available when calling this function. */
	//! 이게 맞나?; aux[0]을 *file로 casting하고 싶어서, 참조 가능한 이중 void 포인터로((void **)aux) 먼저 캐스팅

	struct file *file = ((struct box *)aux)->file;
	off_t ofs = ((struct box*)aux)->ofs;
	size_t page_read_bytes = ((struct box*)aux)->page_read_bytes;
	size_t page_zero_bytes = PGSIZE - page_read_bytes;

	// Get a page of memory
	// Load this page
	file seek (file, ofs);

	if (file_read(file, page->frame->kva, page_read_bytes) != (int) page_read_bytes){
		palloc_free_page(page->frame->kva);
		return false;
	}
	memset(page->frame->kva + page_read_bytes, 0, page_zero_bytes);
	return true;
}

// process.h

static bool lazy_load_segment (struct page *page, void *aux);

struct box {
    struct file *file;
    // uint8_t* upage;
    off_t ofs;
    size_t page_read_bytes;
    // bool writable;
};

 

Supplemental Page Table - Revisit

 

bool supplemental_page_table_copy (struct supplemental_page_table *dst, struct supplemental_page_table *src);

 

// vm.c

/* 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) {
	// Project 3.2_anonymous page
	struct hash_iterator i;
	hash_first(&i, &src->page_table);
	while(hash_next(&i))
	{
		
		struct page *parent_page = hash_entry(hash_cur(&i), struct page, hash_elem);

		enum vm_type type = page_get_type(parent_page);
		void *upage = parent_page->va;
		bool writable = parent_page->writable;
		vm_initializer *init = parent_page->uninit.init;
		void* aux = parent_page->uninit.aux;

		if(parent_page->uninit.type & VM_MARKER_0)
		{
			setup_stack(&thread_current()->tf);
		}
		else if(parent_page->operations->type == VM_UNINIT)
		{
			if(!vm_alloc_page_with_initializer(type, upage, writable, init, aux))
				return false;
		}
		else
		{ // UNIT이 아니면 spt 추가만
			if(!vm_alloc_page(type,upage, writable))
				return false;
			if(!vm_claim_page(upage))
				return false;
		}
		if(parent_page->operations->type != VM_UNINIT)
		{
			struct page* child_page = spt_find_page(dst,upage);
			memcpy(child_page->frame->kva, parent_page->frame->kva, PGSIZE);
		}
	}
	return true;
}

// process.c

#ifndef VM
	...
#else

/* Create a PAGE of stack at the USER_STACK. Return true on success. */
static bool
setup_stack (struct intr_frame *if_) {
	bool success = false;
	void *stack_bottom = (void *) (((uint8_t *) USER_STACK) - PGSIZE);

	...
	/* TODO: Your code goes here */
	// Project 3.2_anonymous page
	if(vm_alloc_page(VM_ANON | VM_MARKER_0, stack_bottom, 1))
	{
		sucess = vm_claim_page(stack_bottom);

		if(success){
			if_->rsp = USER_STACK;
			thread_current()->stack_bottom = stack_bottom;
		}
	}
	//project 3.2_end

	return success;
    
// process.h

bool setup_stack (struct intr_frame *if_);

 

void supplemental_page_table_kill (struct supplemental_page_table *spt);

 

// vm.c

/* 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. */

	struct hash_iterator i;
	hash_first(&i, &spt->page_table);
	while(hash_next(&i))
	{
		struct page *page = hash_entry(hash_cur(&i), struct page, hash_elem);
		if(page->operations->type == VM_FILE)
		{
			do_munmap(page->va);
			//destroy(page);
		}
		//free(page);
	}
	hash_destroy(&spt->page_table, spt_destructor);
}
    

static void
spt_destroy (struct hash_elem *e, void *aux UNUSED){
	struct page *page = hash_entry (e, struct page, hash_elem);
	ASSERT (page != NULL);
	destroy (page);
	free (page);
}

 

Page Cleanup

 

static void uninit_destroy (struct page *page);

- 변경 x

 

static void anon_destroy (struct page *page);

- 변경 x

 

여기까지 하면 argument passing부터 anonymous까지 통과가 된다.

 

 

gyojin -> starm

 

// process.c

tatic bool
load_segment (struct file *file, off_t ofs, uint8_t *upage,
		uint32_t read_bytes, uint32_t zero_bytes, bool writable) {
		...
        off_t read_ofs = ofs;
        while (read_bytes > 0 || zero_bytes > 0) {
          ...
          struct load_info *aux = malloc (sizeof(struct load_info));
          aux->file = file_reopen(file);
          aux->ofs = read_ofs;
          aux->page_read_bytes = page_read_bytes;
          aux->page_zero_bytes = page_zero_bytes;
          if (!vm_alloc_page_with_initializer (VM_ANON, upage,
                      writable, lazy_load_segment, (void*)aux)){
              free(aux);
              return false;
          }
          ...
          read_ofs += PGSIZE;
		}
}


bool
lazy_load_segment (struct page *page, void *aux) {
	/* TODO: Load the segment from the file */
	/* TODO: This called when the first page fault occurs on address VA. */
	/* TODO: VA is available when calling this function. */
    //! 이게 맞나?; aux[0]을 *file로 casting하고 싶어서, 참조 가능한 이중 void 포인터로((void **)aux) 먼저 캐스팅
	// TODO : page 구조체 member로 넣어놓은 것들 불러오기

    // struct file *file = ((struct box *)aux)->file;
	// off_t ofs = ((struct box*)aux)->ofs;
    // size_t page_read_bytes = ((struct box *)aux)->page_read_bytes;
    // size_t page_zero_bytes = PGSIZE - page_read_bytes;
	struct load_info* li = (struct load_info *) aux;
	if (page == NULL) return false;

    
    // if (file_read (file, page->frame->kva, page_read_bytes) != (int) page_read_bytes) {
    //     palloc_free_page (page->frame->kva);
    //     return false;
    // }
	/* Load this page. */
	if(li->page_read_bytes > 0){
		file_seek (li->file, li->ofs);
		if (file_read (li->file, page->frame->kva, li->page_read_bytes) != (int) li->page_read_bytes) {
			vm_dealloc_page (page);
			free(li);
			return false;
			}
	}
    // memset (page->frame->kva + page_read_bytes, 0, page_zero_bytes);
	memset (page->va + li->page_read_bytes, 0, li->page_zero_bytes);
    // hex_dump(page->va, page->va, PGSIZE, true);
    file_close(li->file);
	free(li);
    return true;
}

 

 

 Stack Growth 

 

bool vm_try_handle_fault (struct intr_frame *f, void *addr, bool user, bool write, bool not_present);

 

// vm.c

/* Return true on success */
// page fault 발생시 핸들링을 위해 호출 되는 함수. starmcc 참조
bool
vm_try_handle_fault (struct intr_frame *f UNUSED, void *fault_addr,
		bool user, bool write, bool not_present) {
	struct supplemental_page_table *spt UNUSED = &thread_current ()->spt;
	// Project 3.3_Stack growth
	// struct page *page = NULL;
	/* TODO: Validate the fault */
	if(is_kernel_vaddr (fault_addr) && user) return false;
	/* TODO: Your code goes here */
	void *stack_bottom = pg_round_down (curr->saved_sp);
	if(write && (stack_bottom - PGSIZE <= fault_addr &&
		(uintptr_t) fault_addr < USER_STACK)){
		vm_stack_growth (addr);
		return true;
	}
	struct page* page = spt_find_page(spt, fault_addr);
	if (page=NULL) return false;
	if (write && !not_present) return vm_handle_wp (page);
	return vm_do_claim_page (page);
	// Project 3.3_end

// thread.h

#ifdef VM
	/* Table for whole virtual memory owned by thread. */
	struct supplemental_page_table spt; // vm is in spt
	
	/* Svaing rsp into struct thread on the initial transition
	 * from user to kernel mode */
	uintptr_t saved_sp;
#endif

 

void vm_stack_growth (void *addr);

 

// vm.c

/* Growing the stack. */
static void
vm_stack_growth (void *addr UNUSED) {
	// Project 3.3_stack growth
	void *stack_bottom = pg_round_down (addr);
	size_t req_stack_size = USER_STACK - (uintptr_t)stack_bottom;
	if (req_stack_size > (1 << 20)) PANIC("Stack limit exceeded!\n"); // 1MB

	//Alloc page from tested region to previous claimed stack page.
	void *growing_stack_bottom = stack_bottom;
	while ((uintptr_t) growing_stack_bottom < USER_STACK &&
		vm_alloc_page (VM_ANON | VM_MARKER_0, growing_stack_bottom, true)) { // VM_MARKER_0 스탐은 STACK으로 함
		growing_stack_bottom += PGSIZE;
	};
	vm_claim_page(stack_bottom); // Lazy load requested stack page only

	// Project 3.3_end
}