This week's keywords are Virtual Memory, Page Table, Swap in/out, and Page Replacement.
The hardest part of this assignment was that the functions were heavily fragmented, making it difficult to figure out and distinguish the exact responsibility of each function. For example, when process_cleanup() is called to reclaim the spatial resources used by a process, the flow of involved functions looks like this:
Similar words like destroy and kill are mixed up across various functions, but they actually take on distinct roles.
The first thing I looked at here was supplemental_page_table_kill(). True to its name, it simply handles deleting the spt.
1void 2supplemental_page_table_kill (struct supplemental_page_table *spt UNUSED) { 3 RETURN_IF (spt == NULL); 4 hash_destroy(&spt->hash_table, spt_page_destroy); 5}
hash_destroy() internally calls hash_clear() and passes every hash_elem in the list to the helper function one by one. In other words, the helper function only needs to contain the logic for handling a single incoming hash_elem (a single page). Therefore, I created spt_page_destroy() to safely remove the pages inside the spt.
1static void 2spt_page_destroy (struct hash_elem *e, void *aux UNUSED) { 3 struct page *page = hash_entry (e, struct page, hash_elem); 4 vm_dealloc_page(page); 5}
I deliberated a lot here. Originally, the structure of vm_dealloc_page() looked like this:
1void 2vm_dealloc_page (struct page *page) { 3 destroy (page); 4 free (page); 5}
However, looking at the overall flow of deallocating a page, it feels more natural to clean up the frame along with it. There was a warning in the comments not to modify it, but there weren't many places calling this function anyway. And the real intent of that warning seemed to be to preserve the overarching flow of calling destroy and then free. So I directly modified the function itself to make the flow cleaner.
1void 2vm_dealloc_page (struct page *page) { 3 destroy (page); 4 vm_destroy_page_frame(page); 5 free (page); 6}
I then extracted the logic for handling the frame into a separate function, vm_destroy_page_frame().
1static void 2vm_destroy_page_frame (struct page *page) { 3 RETURN_IF (page == NULL || page->frame == NULL); 4 5 struct frame *frame = page->frame; 6 7 lock_acquire (&frame_lock); 8 if (clock_ptr == &frame->elem) 9 clock_ptr = list_next(&frame_table); 10 list_remove (&frame->elem); 11 lock_release (&frame_lock); 12 13 if (frame->kva != NULL) 14 palloc_free_page (frame->kva); 15 16 pml4_clear_page(frame->owner_thread->pml4, page->va); 17 frame->page = NULL; 18 frame->owner_thread = NULL; 19 free (frame); 20 21}
Since the clock algorithm is used inside vm_get_victim(), if the frame being deleted is what the clock ptr is currently pointing to, I made sure to shift the pointer over by one. This is a necessary step to consistently remove a frame from the frame table without things getting tangled when it's removed from the spt.
Pintos simulates object-oriented programming using unions, and I also took an object-oriented approach by extracting the copy function when implementing supplemental_page_table_copy(). Ultimately, since the necessary actions for copying are different for each page type, I figured it would be more natural and keep the code much cleaner if each object held its own copy function. I proceeded as follows:
1bool 2supplemental_page_table_copy (struct supplemental_page_table *dst UNUSED, 3 struct supplemental_page_table *src UNUSED) { 4 5 struct hash_iterator i; 6 hash_first (&i, &src->hash_table); 7 while (hash_next (&i)) 8 { 9 struct page *src_page = hash_entry (hash_cur (&i), struct page, hash_elem); 10 RETURN_FALSE_IF(!copy(dst, src_page)); 11 } 12 return true; 13}
When writing OS code, there are so many cases where exception handling is required, so I also created and used macro functions like the following:
1#define RETURN_IF(CONDITION) \ 2 do { if (CONDITION) return; } while (0) 3#define RETURN_VALUE_IF(CONDITION, VALUE) \ 4 do { if (CONDITION) return (VALUE); } while (0) 5#define RETURN_NULL_IF(CONDITION) \ 6 do { if (CONDITION) return NULL; } while (0) 7#define RETURN_FALSE_IF(CONDITION) \ 8 do { if (CONDITION) return false; } while (0)
Thus, I structured it in a way that registers the appropriate copy function for each page type.
1static const struct page_operations uninit_ops = { 2 .swap_in = uninit_initialize, 3 .swap_out = NULL, 4 .destroy = uninit_destroy, 5 .copy = uninit_copy, 6 .type = VM_UNINIT, 7};
After registering the functions like this, I wrote the detailed logic corresponding to the page types.
1static bool 2uninit_copy (struct supplemental_page_table *dst, struct page *src_page){ 3 RETURN_FALSE_IF (src_page == NULL); 4 void *aux = src_page->uninit.aux; 5 if (aux) 6 { 7 struct lazy_load_arg *temp_aux 8 = (struct lazy_load_arg *)malloc (sizeof (struct lazy_load_arg)); 9 memcpy (temp_aux, src_page->uninit.aux, sizeof (struct lazy_load_arg)); 10 if (temp_aux->file) 11 { 12 temp_aux->file = file_reopen (temp_aux->file); 13 if (temp_aux->file == NULL) 14 { 15 free (temp_aux); 16 return false; 17 } 18 } 19 aux = temp_aux; 20 } 21 22 if (!vm_alloc_page_with_initializer ( 23 src_page->uninit.type, src_page->va, src_page->writable, 24 src_page->uninit.init, aux)) 25 return false; 26 return true; 27}
1static bool 2anon_copy (struct supplemental_page_table *dst, struct page *src_page){ 3 RETURN_FALSE_IF (src_page == NULL); 4 5 RETURN_FALSE_IF(!vm_alloc_page (page_get_type(src_page), src_page->va, src_page->writable)); 6 RETURN_FALSE_IF(!vm_claim_page (src_page->va)); 7 8 struct page *dst_page = spt_find_page (dst, src_page->va); 9 if (src_page->anon.swapped){ 10 lock_acquire(&swap_lock); 11 for (int i = 0; i < SWAP_SLOT; i++){ 12 disk_read(swap_disk, src_page->anon.swap_idx * 8 + i, (uint8_t *)dst_page->frame->kva + i * 512); 13 } 14 lock_release(&swap_lock); 15 }else{ 16 memcpy(dst_page->frame->kva, src_page->frame->kva, PGSIZE); 17 } 18 return true; 19}
1static bool 2file_copy (struct supplemental_page_table *dst, struct page *src_page){ 3 RETURN_FALSE_IF (src_page == NULL); 4 5 RETURN_FALSE_IF(!vm_alloc_page (page_get_type(src_page), src_page->va, src_page->writable)); 6 RETURN_FALSE_IF(!vm_claim_page (src_page->va)); 7 8 struct page *dst_page = spt_find_page (dst, src_page->va); 9 if (src_page->file.swapped){ 10 RETURN_FALSE_IF (file_read_at(src_page->file.file, src_page->frame->kva, src_page->file.page_read_bytes, src_page->file.ofs) != src_page->file.page_read_bytes); 11 }else{ 12 memcpy(dst_page->frame->kva, src_page->frame->kva, PGSIZE); 13 } 14 return true; 15}
Another big takeaway while coding was the importance of thoroughly understanding exactly what the parameters passed into a function mean, and what their valid scope of values can be. I felt this most painfully while implementing mmap; I had a hard time passing the tests because I misunderstood what length meant among do_mmap's parameters.
1void * 2do_mmap (void *addr, size_t length, int writable, 3 struct file *file, off_t offset) { 4 void *start_addr = addr; 5 struct file *reopened_file = file_reopen(file); 6 off_t file_size = file_length(reopened_file); 7 8 size_t f_read_bytes = length < file_size - offset ? length : file_size - offset; 9 while (f_read_bytes > 0){ 10 struct lazy_load_file_arg* aux = malloc(sizeof(struct lazy_load_file_arg)); 11 RETURN_VALUE_IF (aux == NULL, false); 12 13 size_t page_read_bytes = f_read_bytes < PGSIZE ? f_read_bytes : PGSIZE; 14 size_t page_zero_bytes = PGSIZE - page_read_bytes; 15 16 aux->file = reopened_file; 17 if (aux->file == NULL) { 18 free (aux); 19 return false; 20 } 21 aux->ofs = offset; 22 aux->page_read_bytes = page_read_bytes; 23 aux->page_zero_bytes = page_zero_bytes; 24 25 if (!vm_alloc_page_with_initializer (VM_FILE, addr, writable, 26 lazy_load_file, aux)) { 27 free(aux); 28 return false; 29 } 30 /* 31 * 다음 페이지로 진행한다. 32 */ 33 addr += PGSIZE; 34 offset += page_read_bytes; 35 f_read_bytes -= page_read_bytes; 36 } 37 38 return start_addr; 39}
Ultimately, length means the length the user wants to read. So the core logic was comparing this against the actual filesize to limit it, and then zeroing out the remaining page space.