Compare commits

...

10 Commits

Author SHA1 Message Date
Demetriades, Themis
96b350d623 Merge branch 'vm/mmap-write-back-on-eviction' into 'vm/virtual-memory/themis-synch'
Write back mmap file pages to file upon eviction

See merge request lab2425_autumn/pintos_22!59
2024-12-06 01:01:50 +00:00
Themis Demetriades
31403ac7cb fix: obtain correct page table entry when performing eviction 2024-12-06 00:56:03 +00:00
Demetriades, Themis
8220b931a9 Merge branch 'vm/virtual-memory/frame-synch/saleh' into 'vm/virtual-memory/themis-synch'
Merge frame pinning to themis-synch

See merge request lab2425_autumn/pintos_22!60
2024-12-06 00:21:02 +00:00
sBubshait
1efa1fef9a Merge frame pinning into themis-synch 2024-12-05 23:56:25 +00:00
sBubshait
fc088a19ac Merge remote-tracking branch 'origin/vm/frame-pinning' into vm/virtual-memory/frame-synch/saleh
# Conflicts:
#	src/userprog/syscall.c
2024-12-05 23:48:52 +00:00
sBubshait
a34bbbed08 Update frame: When evicting an mmapped file page, write it back to the file if it is dirty 2024-12-05 22:53:48 +00:00
Themis Demetriades
2811ea0eb3 fix: SPT never removes entries until process termination or special case 2024-12-05 22:05:02 +00:00
sBubshait
6da855fe47 Implement validation of pointers and strings in syscalls with pinning and unpinning to protect against eviction 2024-12-05 21:12:31 +00:00
sBubshait
e03273756d Update frame table to add a pinned flag and protect those from being evicted 2024-12-05 17:52:01 +00:00
EDiasAlberto
5cf79b5389 fix: add check to mmap to ensure file isn't mapped over stack segment 2024-12-05 16:05:08 +00:00
7 changed files with 280 additions and 93 deletions

View File

@@ -252,7 +252,7 @@ fetch_page (void *upage, bool write)
{
/* Check if the page is in the supplemental page table. That is, it is a page
that is expected to be in memory. */
struct page_entry *page = page_get (upage);
struct page_entry *page = page_get (thread_current (), upage);
if (page == NULL)
return false;
@@ -271,9 +271,7 @@ fetch_page (void *upage, bool write)
size_t swap_slot = page_get_swap (t, upage);
swap_in (kpage, swap_slot);
hash_delete (&thread_current ()->pages, &page->elem);
lock_release (&page->lock);
page_cleanup (&page->elem, NULL);
bool writeable = pagedir_is_writable (t->pagedir, upage);
@@ -293,11 +291,6 @@ fetch_page (void *upage, bool write)
case PAGE_MMAP:
case PAGE_FILE:
success = page_load_file (page, page->writable);
if (success && page->type == PAGE_FILE)
{
hash_delete (&thread_current ()->pages, &page->elem);
page_cleanup (&page->elem, NULL);
}
break;
default:
return false;

View File

@@ -10,6 +10,7 @@
#include "threads/synch.h"
#include "userprog/process.h"
#include "userprog/pagedir.h"
#include "vm/frame.h"
#include "vm/page.h"
#include "vm/mmap.h"
#include <stdio.h>
@@ -52,9 +53,14 @@ static mapid_t syscall_mmap (int fd, void *addr);
static void syscall_munmap (mapid_t mapping);
static struct open_file *fd_get_file (int fd);
static void validate_user_pointer (const void *ptr, size_t size,
bool check_write);
static void validate_user_string (const char *str, bool check_write);
static void validate_user_ptr (const void *start, size_t size,
bool write);
static void validate_and_pin_user_ptr (const void *start, size_t size,
bool write);
static void validate_and_pin_user_str (const char *ptr);
static void unpin_user_ptr (const void *start, size_t size);
static void unpin_user_str (const char *ptr);
static int get_user (const uint8_t *);
static bool put_user (uint8_t *, uint8_t);
@@ -107,7 +113,7 @@ static void
syscall_handler (struct intr_frame *f)
{
/* First, read the system call number from the stack. */
validate_user_pointer (f->esp, sizeof (uintptr_t), false);
validate_user_ptr (f->esp, sizeof (uintptr_t), false);
uintptr_t syscall_number = *(int *)f->esp;
thread_current ()->curr_esp = f->esp;
@@ -118,7 +124,7 @@ syscall_handler (struct intr_frame *f)
struct syscall_arguments syscall = syscall_lookup[syscall_number];
/* Next, read and copy the arguments from the stack pointer. */
validate_user_pointer (f->esp + sizeof (uintptr_t),
validate_user_ptr (f->esp + sizeof (uintptr_t),
syscall.arity * sizeof (uintptr_t), false);
uintptr_t args[MAX_SYSCALL_ARGS] = { 0 };
for (int i = 0; i < syscall.arity && i < MAX_SYSCALL_ARGS; i++)
@@ -151,9 +157,11 @@ syscall_exit (int status)
static pid_t
syscall_exec (const char *cmd_line)
{
validate_user_string (cmd_line, false);
validate_and_pin_user_str (cmd_line);
pid_t pid = process_execute (cmd_line);
unpin_user_str (cmd_line);
return process_execute (cmd_line); /* Returns the PID of the new process */
return pid;
}
/* Handles the syscall of wait. Effectively a wrapper for process_wait as the
@@ -170,13 +178,15 @@ syscall_wait (pid_t pid)
static bool
syscall_create (const char *file, unsigned initial_size)
{
validate_user_string (file, false);
validate_and_pin_user_str (file);
/* Acquire the file system lock to prevent race conditions. */
lock_acquire (&filesys_lock);
bool status = filesys_create (file, initial_size);
lock_release (&filesys_lock);
unpin_user_str (file);
/* Return the status of the file creation. */
return status;
}
@@ -187,13 +197,15 @@ syscall_create (const char *file, unsigned initial_size)
static bool
syscall_remove (const char *file)
{
validate_user_string (file, false);
validate_and_pin_user_str (file);
/* Acquire the file system lock to prevent race conditions. */
lock_acquire (&filesys_lock);
bool status = filesys_remove (file);
lock_release (&filesys_lock);
unpin_user_str (file);
/* Return the status of the file removal. */
return status;
}
@@ -205,13 +217,15 @@ syscall_remove (const char *file)
static int
syscall_open (const char *file)
{
validate_user_string (file, false);
validate_and_pin_user_str (file);
/* Acquire the file system lock to prevent race conditions. */
lock_acquire (&filesys_lock);
struct file *ptr = filesys_open (file);
lock_release (&filesys_lock);
unpin_user_str (file);
/* If the file could not be opened, return failure. */
if (ptr == NULL)
return EXIT_FAILURE;
@@ -271,10 +285,11 @@ syscall_read (int fd, void *buffer, unsigned size)
if (fd < STDIN_FILENO || fd == STDOUT_FILENO)
return EXIT_FAILURE;
validate_user_pointer (buffer, size, true);
if (fd == STDIN_FILENO)
{
/* Validate the user buffer. */
validate_user_ptr (buffer, size, true);
/* Reading from the console. */
char *write_buffer = buffer;
for (unsigned i = 0; i < size; i++)
@@ -292,13 +307,19 @@ syscall_read (int fd, void *buffer, unsigned size)
if (file_info == NULL)
return EXIT_FAILURE;
/* Validate the user buffer, and pin the pages to prevent eviction. */
validate_and_pin_user_ptr (buffer, size, true);
/* Acquire the file system lock to prevent race-conditions. */
lock_acquire (&filesys_lock);
int bytes_written = file_read (file_info->file, buffer, size);
int bytes_read = file_read (file_info->file, buffer, size);
lock_release (&filesys_lock);
/* Unpin the pages to allow eviction. */
unpin_user_ptr (buffer, size);
/* Return the number of bytes read. */
return bytes_written;
return bytes_read;
}
}
@@ -314,10 +335,11 @@ syscall_write (int fd, const void *buffer, unsigned size)
if (fd <= 0)
return 0;
validate_user_pointer (buffer, size, false);
if (fd == STDOUT_FILENO)
{
/* Validate the user buffer. */
validate_user_ptr (buffer, size, false);
/* Writing to the console. */
putbuf (buffer, size);
@@ -333,13 +355,19 @@ syscall_write (int fd, const void *buffer, unsigned size)
if (file_info == NULL)
return 0;
/* Validate the user buffer, and pin the pages to prevent eviction. */
validate_and_pin_user_ptr (buffer, size, false);
/* Acquire the file system lock to prevent race conditions. */
lock_acquire (&filesys_lock);
int bytes = file_write (file_info->file, buffer, size);
int bytes_written = file_write (file_info->file, buffer, size);
lock_release (&filesys_lock);
/* Unpin the pages to allow eviction. */
unpin_user_ptr (buffer, size);
/* Return the number of bytes written. */
return bytes;
return bytes_written;
}
}
@@ -426,15 +454,15 @@ syscall_mmap (int fd, void *addr)
if (file_size == 0)
return MMAP_FAILURE;
/* Ensure that the mmap page doesn't overlap with the stack. */
if (addr >= (thread_current ()->curr_esp) - PGSIZE)
/* ensures the page for mmap does not overlap with the stack */
if (addr >= (thread_current ()->curr_esp - PGSIZE))
return MMAP_FAILURE;
/* Check and ensure that there is enough space in the user virtual memory to
hold the entire file. */
for (off_t ofs = 0; ofs < file_size; ofs += PGSIZE)
{
if (page_get (addr + ofs) != NULL)
if (page_get (thread_current (), addr + ofs) != NULL)
return MMAP_FAILURE;
}
@@ -445,7 +473,7 @@ syscall_mmap (int fd, void *addr)
off_t zero_bytes = PGSIZE - read_bytes;
if (page_insert_file (file, ofs, addr + ofs, read_bytes, zero_bytes, true,
PAGE_MMAP) == NULL)
PAGE_FILE) == NULL)
return MMAP_FAILURE;
}
@@ -454,12 +482,13 @@ syscall_mmap (int fd, void *addr)
if (mmap == NULL)
return MMAP_FAILURE;
return mmap->mapping;
}
/* Handles the syscall for unmapping a memory mapped file.
Pre: mapping is a valid mapping identifier returned by mmap syscall. */
Pre: mapping is a valid mapping identifier returned by mmap syscall. */
static void
syscall_munmap (mapid_t mapping)
{
@@ -532,69 +561,171 @@ fd_get_file (int fd)
return hash_entry (e, struct open_file, elem);
}
/* Helper function that validates a block of memory and optionally pins frames.
thread_exit() if the memory is invalid. Used only by the two helper functions
validate_user_ptr and validate_and_pin_user_ptr. See the comments for those
functions for more details on each. */
static void
validate_user_ptr_helper (const void *start, size_t size, bool write, bool pin)
{
if (size == 0)
return;
/* ptr < ptr + size - 1, so sufficient to check that (ptr + size -1) is a
valid user virtual memory address. */
void *end = start + size - 1;
if (!is_user_vaddr (end))
syscall_exit (EXIT_FAILURE);
for (const void *ptr = pg_round_down (start); ptr <= end; ptr += PGSIZE)
{
int result;
/* Check read access to pointer. */
if ((result = get_user (ptr)) == -1)
syscall_exit (EXIT_FAILURE);
/* Check write access to pointer (if required). */
if (write && !put_user ((uint8_t *)ptr, result))
syscall_exit (EXIT_FAILURE);
/* If pin is set, pin the frame to prevent eviction. */
if (pin)
{
void *kpage = pagedir_get_page(thread_current()->pagedir, ptr);
if (kpage == NULL)
{
// If it was evicted, try to load it back in.
ptr -= PGSIZE;
continue;
}
frame_pin(kpage);
}
}
}
/* Validates if a block of memory starting at PTR and of size SIZE bytes is
fully contained within valid user virtual memory. thread_exit () if the
memory is invalid.
If the size is 0, the function does no checks and returns PTR. */
static void
validate_user_pointer (const void *ptr, size_t size, bool check_write)
validate_user_ptr (const void *start, size_t size, bool write)
{
if (size == 0)
return;
/* ptr < ptr + size - 1, so sufficient to check that (ptr + size -1) is a
valid user virtual memory address. */
void *last = ptr + size - 1;
if (!is_user_vaddr (last))
syscall_exit (EXIT_FAILURE);
ptr = pg_round_down (ptr);
while (ptr <= last)
{
int result;
/* Check read access to pointer. */
if ((result = get_user (ptr)) == -1)
syscall_exit (EXIT_FAILURE);
/* Check write access to pointer (if required). */
if (check_write && !put_user (ptr, result))
syscall_exit (EXIT_FAILURE);
ptr += PGSIZE;
}
validate_user_ptr_helper (start, size, write, false);
}
/* Validates if a block of memory starting at PTR and of size SIZE bytes is
fully contained within valid user virtual memory. thread_exit () if the
memory is invalid. The function also checks if the memory is writable if
WRITE flag is set.
The function attempts to preload the pages in case they are not in memory
yet (e.g., in a swap, lazy loading). If this is successful, the frame pages
are pinned to prevent eviction prior to access.
As such, a call to this function MUST be followed by a call to
unpin_user_ptr (START, SIZE) to unpin the pages and allow eviction.
If the size is 0, the function does no checks and returns PTR. */
static void
validate_and_pin_user_ptr (const void *start, size_t size, bool write)
{
validate_user_ptr_helper (start, size, write, true);
}
/* Unpins all the pages containing a block of memory starting at START and of
size SIZE bytes.
Pre: The pages were previously pinned by validate_and_pin_user_ptr (START,
SIZE). */
static void
unpin_user_ptr (const void *start, size_t size)
{
void *end = start + size - 1;
/* We don't need to do any checks as this function is always called after
validate_and_pin_user_ptr. */
/* Go through all pages in the block range, unpinning the frames. */
for (void *ptr = pg_round_down (start); ptr <= end; ptr += PGSIZE)
{
void *kpage = pagedir_get_page (thread_current ()->pagedir, ptr);
ASSERT (kpage != NULL);
frame_unpin (kpage);
}
}
/* Validates of a C-string starting at ptr is fully contained within valid
user virtual memory. thread_exit () if the memory is invalid. */
static void
validate_user_string (const char *ptr, bool check_write)
validate_and_pin_user_str (const char *ptr)
{
size_t offset = (uintptr_t) ptr % PGSIZE;
for (;;)
{
void *page = pg_round_down (ptr);
if (!is_user_vaddr (page))
syscall_exit (EXIT_FAILURE);
if (!is_user_vaddr (ptr))
syscall_exit (EXIT_FAILURE);
int result;
if ((result = get_user ((const uint8_t *)ptr)) == -1)
syscall_exit (EXIT_FAILURE);
if (check_write && !put_user ((uint8_t *)ptr, result))
if (get_user ((const uint8_t *)ptr) == -1)
syscall_exit (EXIT_FAILURE);
/* Pin the frame to prevent eviction. */
void *page = pg_round_down (ptr);
void *kpage = pagedir_get_page (thread_current ()->pagedir, page);
if (kpage == NULL)
{
// If it was evicted, attempt to reload.
ptr -= PGSIZE;
continue;
}
frame_pin (kpage);
while (offset < PGSIZE)
{
if (*ptr == '\0')
return; /* We reached the end of the string without issues. */
{
if (*ptr == '\0')
return; /* We reached the end of the string without issues. */
ptr++;
offset++;
}
ptr++;
offset++;
}
offset = 0;
}
}
/* Unpins all the pages containing a C-string starting at PTR.
Pre: The pages were previously pinned by validate_and_pin_user_str (PTR).
PTR points to a valid C string that ends with '\0'. */
static void
unpin_user_str (const char *ptr)
{
size_t offset = (uintptr_t)ptr % PGSIZE;
const char *str_ptr = ptr;
for (;;)
{
void *page = pg_round_down(str_ptr);
void *kpage = pagedir_get_page(thread_current()->pagedir, page);
ASSERT(kpage != NULL);
frame_unpin (kpage);
/* Scan until end of string or page */
while (offset < PGSIZE)
{
if (*str_ptr == '\0')
return; /* Found end of string */
str_ptr++;
offset++;
}
offset = 0;
}
}
/* PROVIDED BY SPEC.
Reads a byte at user virtual address UADDR.
UADDR must be below PHYS_BASE.

View File

@@ -2,12 +2,13 @@
#include <hash.h>
#include <list.h>
#include <string.h>
#include "frame.h"
#include "page.h"
#include "filesys/file.h"
#include "threads/malloc.h"
#include "threads/vaddr.h"
#include "userprog/pagedir.h"
#include "userprog/syscall.h"
#include "threads/synch.h"
/* Hash table that maps every active frame's kernel virtual address
@@ -36,6 +37,8 @@ struct frame_metadata
void *frame; /* The kernel virtual address holding the frame. */
void *upage; /* The user virtual address pointing to the frame. */
struct thread *owner; /* Pointer to the thread that owns the frame. */
bool pinned;
struct hash_elem hash_elem; /* Tracks the position of the frame metadata
within 'frame_table', whose key is the
kernel virtual address of the frame. */
@@ -49,6 +52,7 @@ hash_less_func frame_metadata_less;
static struct list_elem *lru_next (struct list_elem *e);
static struct list_elem *lru_prev (struct list_elem *e);
static struct frame_metadata *frame_metadata_get (void *frame);
static struct frame_metadata *get_victim (void);
/* Initialize the frame system by initializing the frame (hash) table with
@@ -91,8 +95,25 @@ frame_alloc (enum palloc_flags flags, void *upage, struct thread *owner)
struct frame_metadata *victim = get_victim ();
ASSERT (victim != NULL); /* get_victim () should never return null. */
/* 2. Swap out victim into disk. */
page_insert_swapped (victim->upage, victim->frame, victim->owner);
/* 2. Handle victim page writing based on its type. */
struct page_entry *victim_page = page_get (victim->upage);
if (victim_page != NULL && victim_page->type == PAGE_MMAP)
{
/* If it was a memory-mapped file page, we just write it back
to the file if it was dirty. */
if (pagedir_is_dirty(owner->pagedir, victim->upage))
{
lock_acquire (&filesys_lock);
file_write_at (victim_page->file, victim->upage,
victim_page->read_bytes, victim_page->offset);
lock_release (&filesys_lock);
}
}
else
/* Otherwise, insert the page into swap. */
page_insert_swapped (victim->upage, victim->frame, victim->owner);
/* If zero flag is set, zero out the victim page. */
if (flags & PAL_ZERO)
@@ -134,11 +155,34 @@ frame_alloc (enum palloc_flags flags, void *upage, struct thread *owner)
frame_metadata->upage = upage;
frame_metadata->owner = owner;
frame_metadata->pinned = false;
lock_release (&lru_lock);
return frame_metadata->frame;
}
void
frame_pin (void *frame)
{
struct frame_metadata *frame_metadata = frame_metadata_get (frame);
if (frame_metadata == NULL)
PANIC ("Attempted to pin a frame at an unallocated kernel address '%p'\n",
frame);
frame_metadata->pinned = true;
}
void
frame_unpin (void *frame)
{
struct frame_metadata *frame_metadata = frame_metadata_get (frame);
if (frame_metadata == NULL)
PANIC ("Attempted to unpin a frame at an unallocated kernel address '%p'\n",
frame);
frame_metadata->pinned = false;
}
/* Attempt to deallocate a frame for a user process by removing it from the
frame table as well as lru_list, and freeing the underlying page
memory & metadata struct. Panics if the frame isn't active in memory. */
@@ -192,6 +236,10 @@ get_victim (void)
upage = frame_metadata->upage;
e = lru_next (e);
/* Skip pinned frames */
if (frame_metadata->pinned)
continue;
if (!pagedir_is_accessed (pd, upage))
break;
@@ -219,14 +267,26 @@ frame_metadata_hash (const struct hash_elem *e, void *aux UNUSED)
bool
frame_metadata_less (const struct hash_elem *a_, const struct hash_elem *b_,
void *aux UNUSED)
{
struct frame_metadata *a =
hash_entry (a_, struct frame_metadata, hash_elem);
struct frame_metadata *b =
hash_entry (b_, struct frame_metadata, hash_elem);
{
struct frame_metadata *a =
hash_entry (a_, struct frame_metadata, hash_elem);
struct frame_metadata *b =
hash_entry (b_, struct frame_metadata, hash_elem);
return a->frame < b->frame;
}
return a->frame < b->frame;
}
static struct frame_metadata *
frame_metadata_get (void *frame)
{
struct frame_metadata key_metadata;
key_metadata.frame = frame;
struct hash_elem *e = hash_find (&frame_table, &key_metadata.hash_elem);
if (e == NULL) return NULL;
return hash_entry (e, struct frame_metadata, hash_elem);
}
/* Returns the next recently used element after the one provided, which
is achieved by iterating through lru_list like a circular queue

View File

@@ -6,6 +6,8 @@
void frame_init (void);
void *frame_alloc (enum palloc_flags, void *, struct thread *);
void frame_pin (void *frame);
void frame_unpin (void *frame);
void frame_free (void *frame);
#endif /* vm/frame.h */

View File

@@ -1,5 +1,6 @@
#include "mmap.h"
#include "page.h"
#include "threads/thread.h"
#include "threads/vaddr.h"
#include "threads/malloc.h"
#include "userprog/syscall.h"
@@ -70,7 +71,7 @@ mmap_unmap (struct mmap_entry *mmap)
void *upage = mmap->upage + ofs;
/* Get the SPT page entry for this page. */
struct page_entry *page = page_get(upage);
struct page_entry *page = page_get(thread_current (), upage);
if (page == NULL)
continue;

View File

@@ -39,20 +39,24 @@ static void page_flag_swap (uint32_t *pte, bool set);
static void page_set_swap (struct thread *owner, uint32_t *pte,
size_t swap_slot);
// TODO: Deal with NULL malloc returns
/* Swap out 'owner' process's 'upage' stored at 'kpage'. Then, allocate and
insert a new page entry into the user process thread's SPT representing
this swapped out page. */
struct page_entry *
page_insert_swapped (void *upage, void *kpage, struct thread *owner)
{
/* 1. Initialize swapped page entry. */
struct page_entry *page = malloc(sizeof (struct page_entry));
struct page_entry *page = page_get (thread_current (), upage);
if (page == NULL)
return NULL;
page->upage = upage;
lock_init (&page->lock);
{
page = malloc (sizeof (struct page_entry));
if (page == NULL)
return NULL;
page->upage = upage;
lock_init (&page->lock);
hash_insert (&owner->pages, &page->elem);
}
/* Mark page as 'swapped' and flag the page directory as having
been modified *before* eviction begins to prevent the owner of the
@@ -60,13 +64,9 @@ page_insert_swapped (void *upage, void *kpage, struct thread *owner)
/* TODO: We need to stop the process from destroying pagedir mid-eviction,
as this could render the page table entry invalid. */
uint32_t *pte = lookup_page (owner->pagedir, upage, false);
ASSERT (pte != NULL);
page_flag_swap (pte, true);
lock_acquire (&page->lock);
struct hash_elem *elem = hash_insert (&owner->pages, &page->elem);
ASSERT(elem == NULL);
pagedir_clear_page (owner->pagedir, upage);
size_t swap_slot = swap_out (kpage);
@@ -94,6 +94,7 @@ page_insert_file (struct file *file, off_t ofs, void *upage,
page->read_bytes = read_bytes;
page->zero_bytes = zero_bytes;
page->writable = writable;
lock_init (&page->lock);
hash_insert (&thread_current ()->pages, &page->elem);
return page;
@@ -102,13 +103,13 @@ page_insert_file (struct file *file, off_t ofs, void *upage,
/* Gets a page_entry from the starting address of the page. Returns NULL if no
such page_entry exists in the hash map.*/
struct page_entry *
page_get (void *upage)
page_get (struct thread *thread, void *upage)
{
struct page_entry fake_page_entry;
fake_page_entry.upage = upage;
struct hash_elem *e
= hash_find (&thread_current ()->pages, &fake_page_entry.elem);
= hash_find (&thread->pages, &fake_page_entry.elem);
if (e == NULL)
return NULL;

View File

@@ -7,8 +7,7 @@
enum page_type {
PAGE_FILE,
PAGE_MMAP,
PAGE_EMPTY
PAGE_MMAP
};
struct page_entry {
@@ -38,7 +37,7 @@ struct page_entry *page_insert_swapped (void *upage, void* kpage,
struct page_entry *page_insert_file (struct file *file, off_t ofs, void *upage,
uint32_t read_bytes, uint32_t zero_bytes,
bool writable, enum page_type);
struct page_entry *page_get (void *upage);
struct page_entry *page_get (struct thread *thread, void *upage);
bool page_load_file (struct page_entry *page, bool writable);
void page_cleanup (struct hash_elem *e, void *aux);