fix: properly assign frame owners and deallocate in all required places

src/threads/init.c

@@ -33,6 +33,7 @@
 #endif
 #ifdef VM
 #include "vm/frame.h"
+#include "vm/page.h"
 #include "devices/swap.h"
 #endif
 #ifdef FILESYS
@@ -104,6 +105,7 @@ main (void)
   paging_init ();
 #ifdef VM
   frame_init ();
+  shared_file_pages_init ();
 #endif
 
   /* Segmentation. */

src/threads/thread.c

@@ -265,11 +265,24 @@ thread_create (const char *name, int priority,
 #ifdef USERPROG
   /* Initialize the thread's file descriptor table. */
   t->fd_counter = MINIMUM_USER_FD;
+  bool success = hash_init (&t->open_files, fd_hash, fd_less, NULL);
+  if (success)
+    {
+      success = hash_init (&t->child_results, process_result_hash,
+                           process_result_less, t);
+      if (!success)
+        hash_destroy (&t->open_files, NULL);
+#ifdef VM
+      else
+        {
+          success = init_pages (&t->pages);
+          if (!success)
+            hash_destroy (&t->child_results, NULL);
+        }
+#endif
+    }
 
-  if (!hash_init (&t->open_files, fd_hash, fd_less, NULL)
+  if (!success)
-      || !hash_init (&t->child_results, process_result_hash,
-                     process_result_less, t)
-      || !hash_init (&t->pages, page_hash, page_less, NULL))
     {
       palloc_free_page (t);
       free (t->result);

src/userprog/exception.c

@@ -2,6 +2,7 @@
 #include <inttypes.h>
 #include <stdio.h>
 #include "stdbool.h"
+#include "threads/synch.h"
 #include "userprog/gdt.h"
 #include "userprog/pagedir.h"
 #include "userprog/process.h"
@@ -249,6 +250,12 @@ grow_stack (void *upage)
 bool
 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);
+  if (page == NULL)
+    return false;
+
   /* Check if the non-present user page is in the swap partition.
    If so, swap it back into main memory, updating the PTE for
    the faulted virtual address to point to the newly allocated
@@ -256,20 +263,25 @@ fetch_page (void *upage, bool write)
   struct thread *t = thread_current ();
   if (page_in_swap (t, upage))
   {
-    size_t swap_slot = page_get_swap (t, upage);
+    /* NOTE: This code should be refactored and moved into helper functions
+      within 'page.c'.*/
     void *kpage = frame_alloc (0, upage, t);
+    lock_acquire (&page->lock);
+
+    size_t swap_slot = page_get_swap (t, upage);
     swap_in (kpage, swap_slot);
 
-    bool writeable = pagedir_is_writable (t->pagedir, upage);
+    hash_delete (&thread_current ()->pages, &page->elem);
-    if (pagedir_set_page (t->pagedir, upage, kpage, writeable))
+    lock_release (&page->lock);
-      return true;
+    page_cleanup (&page->elem, NULL);
-  }
 
-  /* Check if the page is in the supplemental page table. That is, it is a page
+    bool writeable = pagedir_is_writable (t->pagedir, upage);
-     that is expected to be in memory. */
+
-  struct page_entry *page = page_get (upage);
+    /* TODO: When this returns false we should quit the page fault,
-  if (page == NULL)
+      but currently we continue and check the stack conditions in the
-    return false;
+      page fault handler. */
+    return pagedir_set_page (t->pagedir, upage, kpage, writeable);
+  }
 
   /* An attempt to write to a non-writeable should fail. */
   if (write && !page->writable)
@@ -278,8 +290,15 @@ fetch_page (void *upage, bool write)
   /* Load the page into memory based on the type of data it is expecting. */
   bool success = false;
   switch (page->type) {
+    case PAGE_MMAP:
     case PAGE_FILE:
-      success = page_load (page, page->writable);
+    case PAGE_SHARED:
+      success = page_load_file (page);
+      if (success && page->type == PAGE_FILE)
+        {
+          hash_delete (&thread_current ()->pages, &page->elem);
+          page_cleanup (&page->elem, NULL);
+        }
       break;
     default:
       return false;

src/userprog/pagedir.c

@@ -2,9 +2,12 @@
 #include <stdbool.h>
 #include <stddef.h>
 #include <string.h>
+#include "devices/swap.h"
 #include "threads/init.h"
 #include "threads/pte.h"
 #include "threads/palloc.h"
+#include "vm/frame.h"
+#include "vm/page.h"
 
 static uint32_t *active_pd (void);
 
@@ -39,8 +42,14 @@ pagedir_destroy (uint32_t *pd)
         uint32_t *pte;
         
         for (pte = pt; pte < pt + PGSIZE / sizeof *pte; pte++)
-          if (*pte & PTE_P) 
+          {
-            palloc_free_page (pte_get_page (*pte));
+            if (page_is_shared_pte (pte))
+              continue;
+            else if (page_in_swap_pte (pte))
+              swap_drop (page_get_swap_pte (pte));
+            else if (*pte & PTE_P)
+              frame_free (pte_get_page (*pte));
+          }
         palloc_free_page (pt);
       }
   palloc_free_page (pd);

src/userprog/process.c

@@ -714,7 +714,7 @@ load_segment (struct file *file, off_t ofs, uint8_t *upage,
       size_t page_zero_bytes = PGSIZE - page_read_bytes;
 
       /* Add the page metadata to the SPT to be lazy loaded later on */
-      if (page_insert (file, ofs, upage, page_read_bytes, page_zero_bytes,
+      if (page_insert_file (file, ofs, upage, page_read_bytes, page_zero_bytes,
                             writable, PAGE_FILE) == NULL)
         return false;
 

src/userprog/syscall.c

@@ -10,7 +10,6 @@
 #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>
@@ -53,14 +52,9 @@ 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_ptr (const void *start, size_t size,
+static void validate_user_pointer (const void *ptr, size_t size,
-                                   bool write);
+                                   bool check_write);
-static void validate_and_pin_user_ptr (const void *start, size_t size,
+static void validate_user_string (const char *str, bool check_write);
-                                       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);
 
@@ -113,7 +107,7 @@ static void
 syscall_handler (struct intr_frame *f)
 {
   /* First, read the system call number from the stack. */
-  validate_user_ptr (f->esp, sizeof (uintptr_t), false);
+  validate_user_pointer (f->esp, sizeof (uintptr_t), false);
   uintptr_t syscall_number = *(int *)f->esp;
   thread_current ()->curr_esp = f->esp;
 
@@ -124,7 +118,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_ptr (f->esp + sizeof (uintptr_t),
+  validate_user_pointer (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++)
@@ -157,11 +151,9 @@ syscall_exit (int status)
 static pid_t
 syscall_exec (const char *cmd_line)
 {
-  validate_and_pin_user_str (cmd_line);
+  validate_user_string (cmd_line, false);
-  pid_t pid = process_execute (cmd_line);
-  unpin_user_str (cmd_line);
 
-  return pid;
+  return process_execute (cmd_line); /* Returns the PID of the new process */
 }
 
 /* Handles the syscall of wait. Effectively a wrapper for process_wait as the
@@ -178,15 +170,13 @@ syscall_wait (pid_t pid)
 static bool
 syscall_create (const char *file, unsigned initial_size)
 {
-  validate_and_pin_user_str (file);
+  validate_user_string (file, false);
 
   /* 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;
 }
@@ -197,15 +187,13 @@ syscall_create (const char *file, unsigned initial_size)
 static bool
 syscall_remove (const char *file)
 {
-  validate_and_pin_user_str (file);
+  validate_user_string (file, false);
 
   /* 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;
 }
@@ -217,15 +205,13 @@ syscall_remove (const char *file)
 static int
 syscall_open (const char *file)
 {
-  validate_and_pin_user_str (file);
+  validate_user_string (file, false);
 
   /* 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;
@@ -285,11 +271,10 @@ 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++)
@@ -307,19 +292,13 @@ 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_read = file_read (file_info->file, buffer, size);
+      int bytes_written = 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_read;
+      return bytes_written;
     }
 }
 
@@ -335,11 +314,10 @@ 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);
 
@@ -355,19 +333,13 @@ 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_written = file_write (file_info->file, buffer, size);
+      int bytes = 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_written;
+      return bytes;
     }
 }
 
@@ -454,8 +426,8 @@ syscall_mmap (int fd, void *addr)
   if (file_size == 0)
     return MMAP_FAILURE;
 
-  /* ensures the page for mmap does not overlap with the stack */
+  /* Ensure that the mmap page doesn't overlap with the stack. */
-  if (addr >= (thread_current ()->curr_esp - PGSIZE))
+  if (addr >= (thread_current ()->curr_esp) - PGSIZE)
     return MMAP_FAILURE;
 
   /* Check and ensure that there is enough space in the user virtual memory to
@@ -472,8 +444,8 @@ syscall_mmap (int fd, void *addr)
       off_t read_bytes = file_size - ofs < PGSIZE ? file_size - ofs : PGSIZE;
       off_t zero_bytes = PGSIZE - read_bytes;
 
-      if (page_insert (file, ofs, addr + ofs, read_bytes, zero_bytes, true,
+      if (page_insert_file (file, ofs, addr + ofs, read_bytes, zero_bytes, true,
-                       PAGE_FILE) == NULL)
+                            PAGE_MMAP) == NULL)
         return MMAP_FAILURE;
     }
 
@@ -482,7 +454,6 @@ syscall_mmap (int fd, void *addr)
   if (mmap == NULL)
       return MMAP_FAILURE;
 
-
   return mmap->mapping;
 }
 
@@ -561,127 +532,54 @@ 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_ptr (const void *start, size_t size, bool write)
+validate_user_pointer (const void *ptr, size_t size, bool check_write)
 {
-  validate_user_ptr_helper (start, size, write, false);
+  if (size == 0)
-}
+    return;
-
+  /* ptr < ptr + size - 1, so sufficient to check that (ptr + size -1) is a
-/* Validates if a block of memory starting at PTR and of size SIZE bytes is
+     valid user virtual memory address. */
-   fully contained within valid user virtual memory. thread_exit () if the
+  void *last = ptr + size - 1;
-   memory is invalid. The function also checks if the memory is writable if
+  if (!is_user_vaddr (last))
-   WRITE flag is set.
+    syscall_exit (EXIT_FAILURE);
-
+  ptr = pg_round_down (ptr);
-   The function attempts to preload the pages in case they are not in memory
+  while (ptr <= last)
-   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);
+      int result;
-}
+      /* Check read access to pointer. */
-
+      if ((result = get_user (ptr)) == -1)
-/* Unpins all the pages containing a block of memory starting at START and of
+        syscall_exit (EXIT_FAILURE);
-   size SIZE bytes.
+      /* Check write access to pointer (if required). */
-
+      if (check_write && !put_user (ptr, result))
-   Pre: The pages were previously pinned by validate_and_pin_user_ptr (START,
+        syscall_exit (EXIT_FAILURE);
-        SIZE). */
+      ptr += PGSIZE;
-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_and_pin_user_str (const char *ptr)
+validate_user_string (const char *ptr, bool check_write)
 {
   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 (get_user ((const uint8_t *)ptr) == -1)
+      if ((result = get_user ((const uint8_t *)ptr)) == -1)
+        syscall_exit (EXIT_FAILURE);
+      if (check_write && !put_user ((uint8_t *)ptr, result))
         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)
       {
@@ -693,36 +591,7 @@ validate_and_pin_user_str (const char *ptr)
       }
 
       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;
     }
 }
 

src/vm/frame.c

@@ -9,7 +9,6 @@
 #include "threads/vaddr.h"
 #include "userprog/pagedir.h"
 #include "threads/synch.h"
-#include "devices/swap.h"
 
 /* Hash table that maps every active frame's kernel virtual address
    to its corresponding 'frame_metadata'.*/
@@ -36,9 +35,7 @@ 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. */
+     struct list owners;          /* List of threads that own 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. */
@@ -52,8 +49,9 @@ 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);
+static void free_owners (struct list *owners);
+static struct frame_metadata *frame_metadata_find (void *frame);
 
 /* Initialize the frame system by initializing the frame (hash) table with
    the frame_metadata hashing and comparison functions, as well as initializing
@@ -96,15 +94,10 @@ frame_alloc (enum palloc_flags flags, void *upage, struct thread *owner)
       ASSERT (victim != NULL); /* get_victim () should never return null. */
 
       /* 2. Swap out victim into disk. */
-      /* Mark page as 'not present' and flag the page directory as having
+      page_insert_swapped (victim->upage, victim->frame, &victim->owners);
-         been modified *before* eviction begins to prevent the owner of the
-         victim page from accessing/modifying it mid-eviction. */
-      pagedir_clear_page (victim->owner->pagedir, victim->upage);
 
-      // TODO: Lock PTE of victim page for victim process.
+      /* Free victim's owners. */
-
+      free_owners (&victim->owners);
-      size_t swap_slot = swap_out (victim->frame);
-      page_set_swap (victim->owner, victim->upage, swap_slot);
 
       /* If zero flag is set, zero out the victim page. */
       if (flags & PAL_ZERO)
@@ -125,6 +118,8 @@ frame_alloc (enum palloc_flags flags, void *upage, struct thread *owner)
       /* Must own lru_lock here, as otherwise there is a race condition
          with next_victim either being NULL or uninitialized. */
       frame_metadata = malloc (sizeof (struct frame_metadata));
+      if (frame_metadata == NULL)
+        PANIC ("Couldn't allocate memory for frame metadata!\n");
       frame_metadata->frame = frame;
 
       /* Newly allocated frames are pushed to the back of the circular queue
@@ -144,54 +139,32 @@ frame_alloc (enum palloc_flags flags, void *upage, struct thread *owner)
       hash_insert (&frame_table, &frame_metadata->hash_elem);
     }
 
+  struct frame_owner *frame_owner = malloc (sizeof (struct frame_owner));
+  if (frame_owner == NULL)
+    PANIC ("Couldn't allocate memory for frame owner!\n");
+  frame_owner->owner = owner;
+  list_init (&frame_metadata->owners);
+  list_push_back (&frame_metadata->owners, &frame_owner->elem);
   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. */
 void
 frame_free (void *frame)
   {
-    struct frame_metadata key_metadata;
+    struct frame_metadata *frame_metadata = frame_metadata_find (frame);
-    key_metadata.frame = frame;
+    if (frame_metadata == NULL)
-
+      PANIC ("Attempted to free a frame at kernel address %p, "
-    struct hash_elem *e =
+             "but this address is not allocated!\n",
-      hash_delete (&frame_table, &key_metadata.hash_elem);
+             frame);
-    if (e == NULL) PANIC ("Attempted to free a frame at kernel address %p, "
-                          "but this address is not allocated!\n", frame);
-
-    struct frame_metadata *frame_metadata =
-      hash_entry (e, struct frame_metadata, hash_elem);
 
+    free_owners (&frame_metadata->owners);
     lock_acquire (&lru_lock);
+    hash_delete (&frame_table, &frame_metadata->hash_elem);
     list_remove (&frame_metadata->list_elem);
 
     /* If we're freeing the frame marked as the next victim, update
@@ -210,37 +183,113 @@ frame_free (void *frame)
     palloc_free_page (frame);
   }
 
+/* Add a thread to a frame's frame_metadata owners list. */
+bool
+frame_owner_insert (void *frame, struct thread *owner)
+{
+  struct frame_metadata *frame_metadata = frame_metadata_find (frame);
+  if (frame_metadata == NULL)
+    return false;
+
+  struct frame_owner *frame_owner = malloc (sizeof (struct frame_owner));
+  if (frame_owner == NULL)
+    return false;
+  frame_owner->owner = owner;
+  list_push_back (&frame_metadata->owners, &frame_owner->elem);
+  return true;
+}
+
+/* Remove and deallocate a frame owner from the frame_metadata owners list.
+  */
+void
+frame_owner_remove (void *frame, struct thread *owner)
+{
+  struct frame_metadata *frame_metadata = frame_metadata_find (frame);
+  if (frame_metadata == NULL)
+    PANIC ("Attempted to remove an owner from a frame at kernel "
+            "address %p, but this address is not allocated!\n",
+            frame);
+
+  struct list_elem *oe;
+  for (oe = list_begin (&frame_metadata->owners);
+        oe != list_end (&frame_metadata->owners);)
+    {
+      struct frame_owner *frame_owner
+          = list_entry (oe, struct frame_owner, elem);
+      oe = list_next (oe);
+      if (frame_owner->owner == owner)
+        {
+          list_remove (&frame_owner->elem);
+          free (frame_owner);
+          return;
+        }
+    }
+  NOT_REACHED ();
+}
+
+/* Find a frame_metadata entry in the frame table. */
+static struct frame_metadata *
+frame_metadata_find (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);
+}
+
 /* TODO: Account for page aliases when checking accessed bit. */
 /* A pre-condition for calling this function is that the calling thread
    owns lru_lock and that lru_list is non-empty. */
 static struct frame_metadata *
 get_victim (void)
   {
-    struct list_elem *e = next_victim;
+    struct list_elem *ve = next_victim;
     struct frame_metadata *frame_metadata;
-    uint32_t *pd;
+    bool found = false;
-    void *upage;
+    while (!found)
-    for (;;)
       {
-        frame_metadata = list_entry (e, struct frame_metadata, list_elem);
+        frame_metadata = list_entry (ve, struct frame_metadata, list_elem);
-        pd = frame_metadata->owner->pagedir;
+        ve = lru_next (ve);
-        upage = frame_metadata->upage;
+        struct list_elem *oe;
-        e = lru_next (e);
 
-        /* Skip pinned frames */
+        /* Returns once a frame that was not accessed by any owner is found. */
-        if (frame_metadata->pinned)
+        found = true;
-          continue;
+        for (oe = list_begin (&frame_metadata->owners);
-
+             oe != list_end (&frame_metadata->owners); oe = list_next (oe))
-        if (!pagedir_is_accessed (pd, upage))
+          {
-          break;
+            struct frame_owner *frame_owner
+                = list_entry (oe, struct frame_owner, elem);
+            uint32_t *pd = frame_owner->owner->pagedir;
+            void *upage = frame_metadata->upage;
 
+            if (pagedir_is_accessed (pd, upage))
+              {
+                found = false;
                 pagedir_set_accessed (pd, upage, false);
               }
+          }
+      }
 
-    next_victim = e;
+    next_victim = ve;
     return frame_metadata;
   }
 
+static void
+free_owners (struct list *owners)
+{
+  struct list_elem *oe;
+  for (oe = list_begin (owners); oe != list_end (owners);)
+    {
+      struct frame_owner *frame_owner
+          = list_entry (oe, struct frame_owner, elem);
+      oe = list_remove (oe);
+      free (frame_owner);
+    }
+}
+
 /* Hash function for frame metadata, used for storing entries in the
    frame table. */
 unsigned
@@ -267,18 +316,6 @@ frame_metadata_less (const struct hash_elem *a_, const struct hash_elem *b_,
     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
    (wrapping around the list at the tail). */

src/vm/frame.h

@@ -4,10 +4,17 @@
 #include "threads/thread.h"
 #include "threads/palloc.h"
 
+struct frame_owner
+{
+  struct thread *owner;  /* The thread that owns the frame. */
+  struct list_elem elem; /* List element for the list of owners. */
+};
+
 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);
 
+bool frame_owner_insert (void *frame, struct thread *owner);
+void frame_owner_remove (void *frame, struct thread *owner);
+
 #endif /* vm/frame.h */

src/vm/page.c

@@ -1,21 +1,49 @@
 #include "page.h"
+#include <stdint.h>
 #include <string.h>
 #include <stdio.h>
 #include "filesys/file.h"
 #include "threads/pte.h"
 #include "threads/malloc.h"
 #include "threads/palloc.h"
+#include "threads/synch.h"
+#include "devices/swap.h"
 #include "userprog/process.h"
 #include "userprog/pagedir.h"
 #include "vm/frame.h"
 
 #define SWAP_FLAG_BIT 9
+#define SHARED_FLAG_BIT 10
 #define ADDR_START_BIT 12
 
+struct hash shared_file_pages;
+struct lock shared_file_pages_lock;
+
+static unsigned page_hash (const struct hash_elem *e, void *aux UNUSED);
+static bool page_less (const struct hash_elem *a_, const struct hash_elem *b_,
+                       void *aux UNUSED);
+
+static void page_flag_shared (struct thread *owner, void *upage, bool shared);
+static unsigned shared_file_page_hash (const struct hash_elem *e,
+                                       void *aux UNUSED);
+static bool shared_file_page_less (const struct hash_elem *a_,
+                                   const struct hash_elem *b_,
+                                   void *aux UNUSED);
+static struct shared_file_page *shared_file_page_get (struct file *file,
+                                                      void *upage);
+
+/* Initialise a supplementary page table. */
+bool
+init_pages (struct hash *pages)
+{
+  ASSERT (pages != NULL);
+  return hash_init (pages, page_hash, page_less, NULL);
+}
+
 /* Hashing function needed for the SPT table. Returns a hash for an entry,
    based on its upage. */
-unsigned
+static unsigned
-page_hash (const struct hash_elem *e, UNUSED void *aux)
+page_hash (const struct hash_elem *e, void *aux UNUSED)
 {
   struct page_entry *page = hash_entry (e, struct page_entry, elem);
   return hash_ptr (page->upage);
@@ -23,7 +51,7 @@ page_hash (const struct hash_elem *e, UNUSED void *aux)
 
 /* Comparator function for the SPT table. Compares two entries based on their
    upages. */
-bool
+static bool
 page_less (const struct hash_elem *a_, const struct hash_elem *b_,
            void *aux UNUSED)
 {
@@ -33,22 +61,98 @@ page_less (const struct hash_elem *a_, const struct hash_elem *b_,
   return a->upage < b->upage;
 }
 
-/* Allocate and insert a new page entry into the thread's page table. */
+static void page_flag_swap (uint32_t *pte, bool set);
-struct page_entry *
+static void page_set_swap (struct thread *owner, uint32_t *pte,
-page_insert (struct file *file, off_t ofs, void *upage, uint32_t read_bytes,
+                           size_t swap_slot);
-             uint32_t zero_bytes, bool writable, enum page_type type)
+
+/* 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. */
+bool
+page_insert_swapped (void *upage, void *kpage, struct list *owners)
 {
+  struct file *exec_file = NULL;
+  struct list_elem *e;
+  for (e = list_begin (owners); e != list_end (owners); e = list_next (e))
+    {
+      struct thread *owner = list_entry (e, struct frame_owner, elem)->owner;
+      uint32_t *pte = lookup_page (owner->pagedir, upage, false);
+      if (exec_file != NULL || page_is_shared_pte (pte))
+        {
+          ASSERT (page_is_shared_pte (pte));
+          pagedir_clear_page (owner->pagedir, upage);
+          exec_file = owner->exec_file;
+          ASSERT (exec_file != NULL);
+          continue;
+        }
+      ASSERT (list_size (owners) == 1);
+
+      /* 1. Initialize swapped page entry. */
+      struct page_entry *page = malloc (sizeof (struct page_entry));
+      if (page == NULL)
+        return false;
+
+      page->upage = upage;
+      lock_init (&page->lock);
+
+      /* Mark page as 'swapped' and flag the page directory as having
+         been modified *before* eviction begins to prevent the owner of the
+         victim page from accessing/modifying it mid-eviction. */
+      /* TODO: We need to stop the process from destroying pagedir
+        mid-eviction, as this could render the page table entry invalid. */
+      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);
+      page_set_swap (owner, pte, swap_slot);
+
+      lock_release (&page->lock);
+    }
+  if (exec_file != NULL)
+    {
+      lock_acquire (&shared_file_pages_lock);
+      struct shared_file_page *sfp = shared_file_page_get (exec_file, upage);
+      sfp->frame = NULL;
+      sfp->swap_slot = swap_out (kpage);
+      lock_release (&shared_file_pages_lock);
+    }
+  return true;
+}
+
+/* Allocate and insert a new page entry into the user process thread's
+   SPT representing a file page. */
+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 type)
+{
+  /* If page exists, just update it. */
+  struct page_entry *existing = page_get (upage);
+  if (existing != NULL)
+    {
+      ASSERT (existing->read_bytes == read_bytes);
+      ASSERT (existing->zero_bytes == zero_bytes);
+      existing->writable = existing->writable || writable;
+      return existing;
+    }
+
   struct page_entry *page = malloc(sizeof (struct page_entry));
   if (page == NULL)
     return NULL;
 
+  page->type = type;
   page->file = file;
   page->offset = ofs;
   page->upage = upage;
   page->read_bytes = read_bytes;
   page->zero_bytes = zero_bytes;
   page->writable = writable;
-  page->type = type;
 
   hash_insert (&thread_current ()->pages, &page->elem);
   return page;
@@ -71,20 +175,71 @@ page_get (void *upage)
 }
 
 bool
-page_load (struct page_entry *page, bool writable)
+page_load_file (struct page_entry *page)
 {
   /* Allocate a frame for the page. If a frame allocation fails, then
      frame_alloc should try to evict a page. If it is still NULL, the OS
      panics as this should not happen if eviction is working correctly. */
   struct thread *t = thread_current ();
+  bool shareable = !page->writable && file_compare (page->file, t->exec_file);
+  if (shareable)
+    {
+      lock_acquire (&shared_file_pages_lock);
+      struct shared_file_page *sfp
+          = shared_file_page_get (page->file, page->upage);
+      if (sfp != NULL)
+        {
+          /* Frame exists, just install it. */
+          if (sfp->frame != NULL)
+            {
+              if (!install_page (page->upage, sfp->frame, page->writable))
+                {
+                  lock_release (&shared_file_pages_lock);
+                  return false;
+                }
+              /* First time adding the shared page, so add thread as owner. */
+              if (page->type != PAGE_SHARED)
+                {
+                  frame_owner_insert (sfp->frame, t);
+                }
+            }
+            /* Shared page is in swap. Load it. */
+            else
+              {
+                void *frame = frame_alloc (PAL_USER, page->upage, t);
+                if (frame == NULL)
+                  PANIC (
+                      "Could not allocate a frame to load page into memory.");
+                swap_in (frame, sfp->swap_slot);
+
+                if (!install_page (page->upage, frame, false))
+                  {
+                    frame_free (frame);
+                    lock_release (&shared_file_pages_lock);
+                    return false;
+                  }
+              }
+            page_flag_shared (t, page->upage, true);
+            if (page->type != PAGE_SHARED)
+              {
+                sfp->ref_count++;
+                page->type = PAGE_SHARED;
+              }
+            lock_release (&shared_file_pages_lock);
+            return true;
+        }
+    }
+
   void *frame = frame_alloc (PAL_USER, page->upage, t);
   pagedir_set_accessed (t->pagedir, page->upage, true);
   if (frame == NULL)
     PANIC ("Could not allocate a frame to load page into memory.");
 
   /* Map the page to the frame. */
-  if (!install_page (page->upage, frame, writable))
+  if (!install_page (page->upage, frame, page->writable))
     {
+      if (shareable)
+        lock_release (&shared_file_pages_lock);
       frame_free (frame);
       return false;
     }
@@ -95,6 +250,8 @@ page_load (struct page_entry *page, bool writable)
   file_seek (page->file, page->offset);
   if (file_read (page->file, frame, page->read_bytes) != (int) page->read_bytes)
   {
+    if (shareable)
+      lock_release (&shared_file_pages_lock);
     frame_free (frame);
     return false;
   }
@@ -102,6 +259,27 @@ page_load (struct page_entry *page, bool writable)
   /* Zero out the remaining bytes in the frame. */
   memset (frame + page->read_bytes, 0, page->zero_bytes);
 
+  /* If file page is read-only, make it shared. */
+  if (shareable)
+    {
+      struct shared_file_page *sfp = malloc (sizeof (struct shared_file_page));
+      if (sfp == NULL)
+        {
+          lock_release (&shared_file_pages_lock);
+          frame_free (frame);
+          return false;
+        }
+      sfp->file = page->file;
+      sfp->upage = page->upage;
+      sfp->frame = frame;
+      sfp->swap_slot = 0;
+      sfp->ref_count = 1;
+      hash_insert (&shared_file_pages, &sfp->elem);
+      page_flag_shared (t, page->upage, true);
+      page->type = PAGE_SHARED;
+      lock_release (&shared_file_pages_lock);
+    }
+
   /* Mark the page as loaded successfully. */
   return true;
 }
@@ -111,17 +289,45 @@ page_load (struct page_entry *page, bool writable)
 void
 page_cleanup (struct hash_elem *e, void *aux UNUSED)
 {
-  free (hash_entry (e, struct page_entry, elem));
+  struct page_entry *page = hash_entry (e, struct page_entry, elem);
+  if (page->type == PAGE_SHARED)
+    {
+      lock_acquire (&shared_file_pages_lock);
+      struct shared_file_page *sfp
+          = shared_file_page_get (page->file, page->upage);
+      ASSERT (sfp != NULL);
+      if (sfp->frame != NULL)
+        frame_owner_remove (sfp->frame, thread_current ());
+      sfp->ref_count--;
+      if (sfp->ref_count == 0)
+        {
+          hash_delete (&shared_file_pages, &sfp->elem);
+          if (sfp->frame != NULL)
+            frame_free (sfp->frame);
+          else
+            swap_drop (sfp->swap_slot);
+          free (sfp);
+        }
+      lock_release (&shared_file_pages_lock);
+    }
+  free (page);
 }
 
-/* Updates the 'owner' thread's page table entry for virtual address 'upage'
+/* Flags the provided page table entry as representing a swapped out page. */
-   to flag the page as being stored in swap, and stores the specified swap slot
-   value in the entry at the address bits for later retrieval from disk. */
 void
-page_set_swap (struct thread *owner, void *upage, size_t swap_slot)
+page_flag_swap (uint32_t *pte, bool set)
   {
-  uint32_t *pte = lookup_page (owner->pagedir, upage, false);
+    if (set)
+      *pte |= (1 << SWAP_FLAG_BIT);
+    else
+      *pte &= ~(1 << SWAP_FLAG_BIT);
+  }
 
+/* Sets the address bits of the page table entry to the provided swap slot
+   value. To be used for later retrieval of the swap slot when page faulting. */
+static void
+page_set_swap (struct thread *owner, uint32_t *pte, size_t swap_slot)
+{
   /* Store the provided swap slot in the address bits of the page table
      entry, truncating excess bits. */
   *pte |= (1 << SWAP_FLAG_BIT);
@@ -137,13 +343,19 @@ bool
 page_in_swap (struct thread *owner, void *upage)
 {
    uint32_t *pte = lookup_page (owner->pagedir, upage, false);
-   return pte != NULL &&
+   return page_in_swap_pte (pte);
-          (*pte & (1 << SWAP_FLAG_BIT)) != 0;
+}
+
+/* Returns true iff the page table entry is marked to be in the swap disk. */
+bool
+page_in_swap_pte (uint32_t *pte)
+{
+  return pte != NULL && (*pte & (1 << SWAP_FLAG_BIT)) != 0;
 }
 
 /* Given that the page with user address 'upage' owned by 'owner' is flagged
    to be in the swap disk via the owner's page table, returns its stored
-   swap slot. Otherwise panics the kernel. */
+   swap slot and marks the PTE as not being in swap. */
 size_t
 page_get_swap (struct thread *owner, void *upage)
 {
@@ -153,5 +365,85 @@ page_get_swap (struct thread *owner, void *upage)
    ASSERT ((*pte & PTE_P) == 0);
 
    /* Masks the address bits and returns truncated value. */
+   page_flag_swap (pte, false);
    return ((*pte & PTE_ADDR) >> ADDR_START_BIT);
 }
+
+/* Returns the swap slot stored in a PTE. */
+size_t
+page_get_swap_pte (uint32_t *pte)
+{
+  ASSERT (pte != NULL);
+  ASSERT ((*pte & PTE_P) == 0);
+  return ((*pte & PTE_ADDR) >> ADDR_START_BIT);
+}
+
+/* Flags the provided page table entry as representing a shared page. */
+static void
+page_flag_shared (struct thread *owner, void *upage, bool shared)
+{
+  uint32_t *pte = lookup_page (owner->pagedir, upage, false);
+  ASSERT (pte != NULL);
+
+  if (shared)
+    *pte |= (1 << SHARED_FLAG_BIT);
+  else
+    *pte &= ~(1 << SHARED_FLAG_BIT);
+}
+
+/* Returns true iff the page table entry is marked to be shared. */
+bool
+page_is_shared_pte (uint32_t *pte)
+{
+  return pte != NULL && (*pte & (1 << SHARED_FLAG_BIT)) != 0;
+}
+
+/* Initializes the shared file pages hash table. */
+void
+shared_file_pages_init ()
+{
+  if (!hash_init (&shared_file_pages, shared_file_page_hash,
+                  shared_file_page_less, NULL))
+    PANIC ("Failed to initialize shared file pages hash table.");
+  lock_init (&shared_file_pages_lock);
+}
+
+/* Hash function for shared file pages, used for storing entries in the
+   shared file pages table. */
+static unsigned
+shared_file_page_hash (const struct hash_elem *e, void *aux UNUSED)
+{
+  struct shared_file_page *sfp = hash_entry (e, struct shared_file_page, elem);
+  void *inode = file_get_inode (sfp->file);
+  void *upage = sfp->upage;
+  void *bytes[2] = { inode, upage };
+  return hash_bytes (bytes, sizeof (bytes));
+}
+
+/* 'less_func' comparison function for shared file pages, used for comparing
+   the keys of the shared file pages table. */
+static bool
+shared_file_page_less (const struct hash_elem *a_, const struct hash_elem *b_,
+                       void *aux UNUSED)
+{
+  const struct shared_file_page *a
+      = hash_entry (a_, struct shared_file_page, elem);
+  const struct shared_file_page *b
+      = hash_entry (b_, struct shared_file_page, elem);
+
+  return !file_compare (a->file, b->file) || a->upage < b->upage;
+}
+
+static struct shared_file_page *
+shared_file_page_get (struct file *file, void *upage)
+{
+  struct shared_file_page fake_sfp;
+  fake_sfp.file = file;
+  fake_sfp.upage = upage;
+
+  struct hash_elem *e = hash_find (&shared_file_pages, &fake_sfp.elem);
+  if (e == NULL)
+    return NULL;
+
+  return hash_entry (e, struct shared_file_page, elem);
+}

src/vm/page.h

@@ -2,17 +2,27 @@
 #define VM_PAGE_H
 
 #include "threads/thread.h"
+#include "threads/synch.h"
 #include "filesys/off_t.h"
 
-enum page_type {
+enum page_type
+{
   PAGE_FILE,
-  PAGE_EMPTY
+  PAGE_MMAP,
+  PAGE_EMPTY,
+  PAGE_SHARED
 };
 
-struct page_entry {
+struct page_entry
+{
   enum page_type type; /* Type of Data that should go into the page */
   void *upage;         /* Start Address of the User Page (Key of hash table). */
 
+  /* Data for swapped pages */
+  struct lock lock;    /* Enforces mutual exclusion in accessing the page
+                          referenced by the entry between its owning process
+                          and any thread performing page eviction. */
+
   /* File Data */
   struct file *file;   /* Pointer to the file for executables. */
   off_t offset;        /* Offset of the page content within the file. */
@@ -23,18 +33,32 @@ struct page_entry {
   struct hash_elem elem; /* An elem for the hash table. */
 };
 
-unsigned page_hash (const struct hash_elem *e, void *aux);
+struct shared_file_page
-bool page_less (const struct hash_elem *a_, const struct hash_elem *b_,
+{
-                void *aux);
+  struct file *file;
-struct page_entry *page_insert (struct file *file, off_t ofs, void *upage,
+  void *upage;
+  void *frame;
+  size_t swap_slot;
+  int ref_count;
+
+  struct hash_elem elem;
+};
+
+bool init_pages (struct hash *pages);
+bool page_insert_swapped (void *upage, void *kpage, struct list *owners);
+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 type);
+                                     bool writable, enum page_type);
 struct page_entry *page_get (void *upage);
-bool page_load (struct page_entry *page, bool writable);
+bool page_load_file (struct page_entry *page);
 void page_cleanup (struct hash_elem *e, void *aux);
 
-void page_set_swap (struct thread *, void *, size_t);
 bool page_in_swap (struct thread *, void *);
-size_t page_get_swap (struct thread *, void *);
+bool page_in_swap_pte (uint32_t *pte);
+size_t page_get_swap (struct thread *owner, void *upage);
+size_t page_get_swap_pte (uint32_t *pte);
 
-#endif /* vm/frame.h */
+bool page_is_shared_pte (uint32_t *pte);
+void shared_file_pages_init (void);
+
+#endif