feat: add general SPT lock for operations across threads

Write back mmap file pages to file upon eviction

See merge request lab2425_autumn/pintos_22!59

src/Makefile.build

@@ -66,6 +66,7 @@ vm_SRC += vm/frame.c                    # Frame table manager.
 vm_SRC += vm/page.c                     # Page table manager.
 vm_SRC += vm/mmap.c                     # Memory-mapped files.
 vm_SRC += devices/swap.c		# Swap block manager.
+#vm_SRC = vm/file.c			# Some other file.
 
 # Filesystem code.
 filesys_SRC  = filesys/filesys.c	# Filesystem core.

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)
-      || !hash_init (&t->child_results, process_result_hash,
-                     process_result_less, t)
-      || !hash_init (&t->pages, page_hash, page_less, NULL))
+  if (!success)
     {
       palloc_free_page (t);
       free (t->result);
@@ -723,6 +736,10 @@ init_thread (struct thread *t, const char *name, int nice, int priority,
   t->recent_cpu = recent_cpu;
   t->priority = t->base_priority;
 
+  #ifdef VM
+  lock_init (&t->spt_lock);
+  #endif
+
   old_level = intr_disable ();
   list_push_back (&all_list, &t->allelem);
   intr_set_level (old_level);

src/threads/thread.h

@@ -149,6 +149,10 @@ struct thread
     struct hash open_files;             /* Hash Table of FD -> Struct File. */
 #endif
 
+    struct lock spt_lock;
+
+    void *curr_esp;
+
     /* Owned by thread.c. */
     unsigned magic;                     /* Detects stack overflow. */
   };

src/userprog/exception.c

@@ -1,19 +1,30 @@
 #include "userprog/exception.h"
 #include <inttypes.h>
 #include <stdio.h>
+#include "stdbool.h"
 #include "userprog/gdt.h"
-#include "userprog/pagedir.h"
 #include "threads/interrupt.h"
 #include "threads/thread.h"
-#include "threads/vaddr.h"
+#ifdef VM
+#include "vm/frame.h"
 #include "vm/page.h"
+#include "devices/swap.h"
+#include "threads/vaddr.h"
+#include "userprog/pagedir.h"
+#endif
+
+#define MAX_STACK_SIZE (8 * 1024 * 1024) // 8MB
+#define MAX_STACK_OFFSET 32 // 32 bytes offset below stack pointer (ESP)
 
 /* Number of page faults processed. */
 static long long page_fault_cnt;
 
 static void kill (struct intr_frame *);
 static void page_fault (struct intr_frame *);
-bool try_fetch_page (void *upage, bool write);
+
+static bool is_valid_stack_access (const void *fault_addr, const void *esp);
+static bool grow_stack (void *upage);
+bool fetch_page (void *upage, bool write);
 
 /* Registers handlers for interrupts that can be caused by user
    programs.
@@ -149,6 +160,26 @@ page_fault (struct intr_frame *f)
   write = (f->error_code & PF_W) != 0;
   user = (f->error_code & PF_U) != 0;
 
+  /* Select the appropriate stack pointer based on the context of the fault. */
+  void *esp = user ? f->esp : thread_current()->curr_esp;
+
+  /* If the fault address is in a user page that is not present, then it might
+   be just that the stack needs to grow or that it needs to be lazily loaded.
+   So we attempt to grow the stack. If this does not work, we check our SPT to
+   see if the page is expected to have data loaded in memory. */
+  void *upage = pg_round_down (fault_addr);
+  if (not_present && is_user_vaddr (upage) && upage != NULL)
+    {
+      if (fetch_page (upage, write))
+        return;
+
+      if (is_valid_stack_access (fault_addr, esp))
+          if (grow_stack (upage))
+            return;
+    }
+
+  /* If the page fault occurred in kernel mode,  then we intentionally indicate
+     a fault (for get_user() etc). */
   if (!user)
   {
     f->eip = (void *)f->eax;
@@ -157,16 +188,6 @@ page_fault (struct intr_frame *f)
   }
 
 
-  /* If the fault address is in a user page that is not present, then it might
-     just need to be lazily loaded. So, we check our SPT to see if the page
-     is expected to have data loaded in memory. */
-  void *upage = pg_round_down (fault_addr);
-  if (not_present && is_user_vaddr (upage) && upage != NULL)
-    {
-      if (try_fetch_page (upage, write))
-        return;
-    }
-
   /* To implement virtual memory, delete the rest of the function
      body, and replace it with code that brings in the page to
      which fault_addr refers. */
@@ -178,15 +199,88 @@ page_fault (struct intr_frame *f)
   kill (f);
 }
 
+/* Validates whether the fault address is a valid stack access. Access is a
+   valid stack access under the following two conditions:
+     1. The fault address must be within MAX_STACK_OFFSET (32) bytes below
+      the current stack pointer. (Accounts for both PUSH and PUSHA instructions)
+     2. Growing this stack to this address does not cause it to exceed the
+      MAX_STACK_SIZE (8MB) limit.
+
+   Returns true if both conditions are met, false otherwise.
+
+   Pre: fault_addr is a valid user virtual address (so also not NULL). */
+static bool
+is_valid_stack_access (const void *fault_addr, const void *esp)
+{
+  uint32_t new_stack_size = PHYS_BASE - pg_round_down (fault_addr);
+
+  uint32_t *lowest_valid_push_addr = (uint32_t *)esp - MAX_STACK_OFFSET;
+  bool is_within_push_range = (uint32_t *)fault_addr >= lowest_valid_push_addr;
+
+  return is_within_push_range && new_stack_size <= MAX_STACK_SIZE;
+}
+
+/* Attempts to grow the stack by allocating and mapping a new page.
+  This involves:
+    1. Allocating a zeroed page from the user pool
+    2. Installing it into the page table with write permissions
+
+  Returns true if the stack was successfully grown, false if either
+  allocation or installation fails.
+
+  Pre: upage is a valid page-aligned address (so also not NULL). */
+static bool
+grow_stack (void *upage)
+{
+  /* Allocate new page for stack */
+  void *new_page = frame_alloc (PAL_ZERO, upage, thread_current ());
+  if (new_page == NULL)
+    return false;
+
+  /* Install the page into user page table */
+  if (!pagedir_set_page (thread_current ()->pagedir, upage, new_page, true))
+    {
+      frame_free (new_page);
+      return false;
+    }
+
+  return true;
+}
+
 bool
-try_fetch_page (void *upage, bool write)
+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;
 
+  /* 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
+   frame. */
+  struct thread *t = thread_current ();
+  if (page_in_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);
+
+      lock_release (&page->lock);
+
+      bool writeable = pagedir_is_writable (t->pagedir, upage);
+
+      /* TODO: When this returns false we should quit the page fault,
+        but currently we continue and check the stack conditions in the
+        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)
     return false;
@@ -194,8 +288,10 @@ try_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);
       break;
     default:
       return false;

src/userprog/pagedir.c

@@ -2,12 +2,14 @@
 #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);
-static void invalidate_pagedir (uint32_t *);
 
 /* Creates a new page directory that has mappings for kernel
    virtual addresses, but none for user virtual addresses.
@@ -40,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);
@@ -53,7 +61,7 @@ pagedir_destroy (uint32_t *pd)
    on CREATE.  If CREATE is true, then a new page table is
    created and a pointer into it is returned.  Otherwise, a null
    pointer is returned. */
-static uint32_t *
+uint32_t *
 lookup_page (uint32_t *pd, const void *vaddr, bool create)
 {
   uint32_t *pt, *pde;
@@ -278,7 +286,7 @@ active_pd (void)
    This function invalidates the TLB if PD is the active page
    directory.  (If PD is not active then its entries are not in
    the TLB, so there is no need to invalidate anything.) */
-static void
+void
 invalidate_pagedir (uint32_t *pd) 
 {
   if (active_pd () == pd) 

src/userprog/pagedir.h

@@ -6,6 +6,7 @@
 
 uint32_t *pagedir_create (void);
 void pagedir_destroy (uint32_t *pd);
+uint32_t *lookup_page (uint32_t *pd, const void *vaddr, bool create);
 bool pagedir_set_page (uint32_t *pd, void *upage, void *kpage, bool rw);
 void *pagedir_get_page (uint32_t *pd, const void *upage);
 void pagedir_clear_page (uint32_t *pd, void *upage);
@@ -16,5 +17,6 @@ void pagedir_set_accessed (uint32_t *pd, const void *upage, bool accessed);
 bool pagedir_is_writable (uint32_t *pd, const void *upage);
 void pagedir_set_writable (uint32_t *pd, const void *upage, bool writable);
 void pagedir_activate (uint32_t *pd);
+void invalidate_pagedir (uint32_t *pd);
 
 #endif /* userprog/pagedir.h */

src/userprog/process.c

@@ -369,6 +369,8 @@ process_exit (void)
 
   /* Clean up all open files */
   hash_destroy (&cur->open_files, fd_cleanup);
+
+  /* Clean up the thread's supplemental page table. */
   hash_destroy (&cur->pages, page_cleanup);
 
   /* Close the executable file, implicitly allowing it to be written to. */
@@ -627,6 +629,9 @@ load (const char *file_name, void (**eip) (void), void **esp)
 
  done:
   /* We arrive here whether the load is successful or not. */
+#ifndef VM
+  file_close (file);
+#endif
   lock_release (&filesys_lock);
   return success;
 }
@@ -709,8 +714,8 @@ 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,
-                       writable, PAGE_FILE) == NULL)
+      if (page_insert_file (file, ofs, upage, page_read_bytes, page_zero_bytes,
+                            writable, PAGE_FILE) == NULL)
         return false;
 
       /* Advance. */
@@ -758,6 +763,7 @@ get_usr_kpage (enum palloc_flags flags, void *upage)
     return NULL;
   else
     page = frame_alloc (flags, upage, t);
+  pagedir_set_accessed (t->pagedir, upage, true);
 #else
   page = palloc_get_page (flags | PAL_USER);
 #endif

src/userprog/syscall.c

@@ -1,5 +1,4 @@
 #include "userprog/syscall.h"
-#include "userprog/exception.h"
 #include "devices/shutdown.h"
 #include "devices/input.h"
 #include "filesys/file.h"
@@ -11,9 +10,11 @@
 #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>
+#include <stdbool.h>
 #include <syscall-nr.h>
 
 #define MAX_SYSCALL_ARGS 3
@@ -52,8 +53,16 @@ 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 *start, size_t size, bool write);
-static void validate_user_string (const char *str);
+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);
 
 /* A struct defining a syscall_function pointer along with its arity. */
 struct syscall_arguments
@@ -104,8 +113,9 @@ 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);
-  uintptr_t syscall_number = *(int *) f->esp;
+  validate_user_ptr (f->esp, sizeof (uintptr_t), false);
+  uintptr_t syscall_number = *(int *)f->esp;
+  thread_current ()->curr_esp = f->esp;
 
   /* Ensures the number corresponds to a system call that can be handled. */
   if (syscall_number >= LOOKUP_SIZE)
@@ -114,12 +124,11 @@ 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};
+  uintptr_t args[MAX_SYSCALL_ARGS] = { 0 };
   for (int i = 0; i < syscall.arity && i < MAX_SYSCALL_ARGS; i++)
-    args[i] = *(uintptr_t *) (f->esp + sizeof (uintptr_t) * (i + 1));
+    args[i] = *(uintptr_t *)(f->esp + sizeof (uintptr_t) * (i + 1));
 
   /* Call the function that handles this system call with the arguments. When
      there is a return value it is stored in f->eax. */
@@ -148,10 +157,11 @@ syscall_exit (int status)
 static pid_t
 syscall_exec (const char *cmd_line)
 {
-  /* Validate the user string before executing the process. */
-  validate_user_string (cmd_line);
+  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
@@ -168,14 +178,15 @@ syscall_wait (pid_t pid)
 static bool
 syscall_create (const char *file, unsigned initial_size)
 {
-  /* Validate the user string before creating the file. */
-  validate_user_string (file);
+  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;
 }
@@ -186,14 +197,15 @@ syscall_create (const char *file, unsigned initial_size)
 static bool
 syscall_remove (const char *file)
 {
-  /* Validate the user string before removing the file. */
-  validate_user_string (file);
+  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,14 +217,15 @@ syscall_remove (const char *file)
 static int
 syscall_open (const char *file)
 {
-  /* Validate the user string before opening the file. */
-  validate_user_string (file);
+  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;
@@ -272,11 +285,11 @@ syscall_read (int fd, void *buffer, unsigned size)
   if (fd < STDIN_FILENO || fd == STDOUT_FILENO)
     return EXIT_FAILURE;
 
-  /* Validate the user buffer for the provided size before reading. */
-  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++)
@@ -294,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;
     }
 }
 
@@ -316,11 +335,11 @@ syscall_write (int fd, const void *buffer, unsigned size)
   if (fd <= 0)
     return 0;
 
-  /* Validate the user buffer for the provided size before writing. */
-  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);
 
@@ -336,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;
     }
 }
 
@@ -429,11 +454,15 @@ syscall_mmap (int fd, void *addr)
   if (file_size == 0)
     return MMAP_FAILURE;
 
+  /* 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;
     }
 
@@ -443,7 +472,7 @@ 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)
         return MMAP_FAILURE;
     }
@@ -459,7 +488,7 @@ syscall_mmap (int fd, void *addr)
 
 /* 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,67 +561,193 @@ fd_get_file (int fd)
   return hash_entry (e, struct open_file, elem);
 }
 
-/* Validates if a block of memory starting at START and of size SIZE bytes is
-   fully contained within user virtual memory. Kills the thread (by exiting with
-   failure) if the memory is invalid. Otherwise, returns (nothing) normally.
-   If the size is 0, the function does no checks and returns the given ptr. */
+/* 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_pointer (const void *start, size_t size, bool write)
+validate_user_ptr_helper (const void *start, size_t size, bool write, bool pin)
 {
-  /* If the size is 0, we do not need to check anything. */
   if (size == 0)
     return;
 
-  const void *end = start + size - 1;
-
-  /* Check if the start and end pointers are valid user virtual addresses. */
-  if (start == NULL || !is_user_vaddr (start) || !is_user_vaddr (end))
+  /* 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);
 
-  /* We no longer check if the memory is mapped to physical memory. This is
-     because the data may not necessarily be there at the time of the syscall,
-     but it may be lazily loaded later. In such case, we try to preload the
-     page. If that fails, we exit the thread. */
-  for (void *ptr = pg_round_down (start); ptr <= end; ptr += PGSIZE)
-    if (pagedir_get_page (thread_current ()->pagedir, ptr) == NULL &&
-        !try_fetch_page (ptr, write))
-      syscall_exit (EXIT_FAILURE);
-}
-
-/* Validates if a string is fully contained within user virtual memory. Kills
-   the thread (by exiting with failure) if the memory is invalid. Otherwise,
-   returns (nothing) normally. */
-static void
-validate_user_string (const char *str)
-{
-  /* Check if the string pointer is a valid user virtual address. */
-  if (str == NULL || !is_user_vaddr (str))
-    syscall_exit (EXIT_FAILURE);
-
-  /* Calculate the offset of the string within the (first) page. */
-  size_t offset = (uintptr_t) str % PGSIZE;
-
-  /* We move page by page, checking if the page is mapped to physical memory. */
-  for (;;)
+  for (const void *ptr = pg_round_down (start); ptr <= end; ptr += PGSIZE)
   {
-    void *page = pg_round_down (str);
+    int result;
 
-    /* If we reach addresses that are not mapped to physical memory before the
-       end of the string, the thread is terminated. */
-    if (!is_user_vaddr(page) ||
-        (pagedir_get_page (thread_current ()->pagedir, page) == NULL &&
-         !try_fetch_page (page, false)))
+    /* Check read access to pointer. */
+    if ((result = get_user (ptr)) == -1)
       syscall_exit (EXIT_FAILURE);
 
-    while (offset < PGSIZE)
-      {
-        if (*str == '\0')
-          return; /* We reached the end of the string without issues. */
+    /* Check write access to pointer (if required). */
+    if (write && !put_user ((uint8_t *)ptr, result))
+      syscall_exit (EXIT_FAILURE);
 
-        str++;
-        offset++;
+    /* 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;
       }
 
-    offset = 0; /* Next page will start at the beginning. */
+      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_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_and_pin_user_str (const char *ptr)
+{
+  size_t offset = (uintptr_t) ptr % PGSIZE;
+
+  for (;;)
+    {
+      if (!is_user_vaddr (ptr))
+        syscall_exit (EXIT_FAILURE);
+
+      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. */
+
+          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.
+   Returns the byte value if successful, -1 if a segfault occurred. */
+static int
+get_user (const uint8_t *uaddr)
+{
+  int result;
+  asm ("movl $1f, %0; movzbl %1, %0; 1:" : "=&a"(result) : "m"(*uaddr));
+  return result;
+}
+
+/* PROVIDED BY SPEC.
+   Writes BYTE to user address UDST.
+   UDST must be below PHYS_BASE.
+   Returns true if successful, false if a segfault occurred. */
+static bool
+put_user (uint8_t *udst, uint8_t byte)
+{
+  int error_code;
+  asm ("movl $1f, %0; movb %b2, %1; 1:"
+       : "=&a"(error_code), "=m"(*udst)
+       : "q"(byte));
+  return error_code != -1;
+}

src/vm/frame.c

@@ -2,38 +2,43 @@
 #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"
-#include "devices/swap.h"
 
 /* Hash table that maps every active frame's kernel virtual address
    to its corresponding 'frame_metadata'.*/
 struct hash frame_table;
 
-/* Linked list of frame_metadata whose pages are predicted to currently
-   be in the working set of a process. They are not considered for
-   eviction, but are considered for demotion to the 'inactive' list. */
-struct list active_list;
+/* Linked list used to represent the circular queue in the 'clock'
+   algorithm for page eviction. Iterating from the element that is
+   currently pointed at by 'next_victim' yields an ordering of the entries
+   from oldest to newest (in terms of when they were added or checked
+   for having been referenced by a process). */
+struct list lru_list;
 
-/* Linked list of frame_metadata whose pages are predicted to leave the
-   working set of their processes soon, so are considered for eviction.
-   Pages are considered for eviction from the tail end, and are initially
-   demoted to 'inactive' at the head. */
-struct list inactive_list;
+/* The next element in lru_list to be considered for eviction (oldest added
+   or referenced page in the circular queue). If this page has has an
+   'accessed' bit of 0 when considering eviction, then it will be the next
+   victim. Otherwise, the next element in the queue is similarly considered. */
+struct list_elem *next_victim = NULL;
 
 /* Synchronisation variables. */
-/* Protects access to the 'inactive' list. */
-struct lock inactive_lock;
+/* Protects access to 'lru_list'. */
+struct lock lru_lock;
 
 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;                 /* Indicates wheter the frame should be
+                                     considered as an eviction candidate.*/
      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. */
@@ -45,22 +50,27 @@ struct frame_metadata
 hash_hash_func frame_metadata_hash;
 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
-   the active & inactive lists. Also initializes the system's synchronisation
-   primitives. */
+   'lru_list' and its associated synchronisation primitives. */
 void
 frame_init (void)
 {
   hash_init (&frame_table, frame_metadata_hash, frame_metadata_less, NULL);
-  list_init (&active_list);
-  list_init (&inactive_list);
 
-  lock_init (&inactive_lock);
+  list_init (&lru_list);
+  lock_init (&lru_lock);
 }
 
+/* TODO: Consider synchronisation more closely (i.e. just for hash
+         table). */
 /* Attempt to allocate a frame for a user process, either by direct
    allocation of a user page if there is sufficient RAM, or by
    evicting a currently active page if memory allocated for user
@@ -69,7 +79,10 @@ frame_init (void)
 void *
 frame_alloc (enum palloc_flags flags, void *upage, struct thread *owner)
 {
+  struct frame_metadata *frame_metadata;
   flags |= PAL_USER;
+
+  lock_acquire (&lru_lock);
   void *frame = palloc_get_page (flags);
 
   /* If a frame couldn't be allocated we must be out of main memory. Thus,
@@ -77,80 +90,254 @@ frame_alloc (enum palloc_flags flags, void *upage, struct thread *owner)
      into disk. */
   if (frame == NULL)
     {
-      /* TODO: Deal with race condition wherein a page may be evicted in one
-        thread while it's in the middle of being evicted in another. */
-      struct frame_metadata *victim = get_victim ();
-      if (victim == NULL)
-        return NULL;
+      /* 1. Obtain victim. */
+      if (next_victim == NULL)
+        PANIC ("Couldn't allocate a single page to main memory!\n");
 
-      size_t swap_slot = swap_out (victim->frame);
-      page_set_swap (victim->owner, victim->upage, swap_slot);
+      struct frame_metadata *victim = get_victim ();
+      ASSERT (victim != NULL); /* get_victim () should never return null. */
+
+      /* 2. Handle victim page writing based on its type. */
+      struct page_entry *victim_page = page_get (thread_current (), 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->owners);
+        }
+
+      /* Free victim's owners. */
+      free_owners (&victim->owners);
 
       /* If zero flag is set, zero out the victim page. */
       if (flags & PAL_ZERO)
         memset (victim->frame, 0, PGSIZE);
 
-      frame = victim->frame;
+      /* 3. Indicate that the new frame's metadata will be stored
+            inside the same structure that stored the victim's metadata.
+            As both the new frame and the victim frame share the same kernel
+            virtual address, the hash map need not be updated, and neither
+            the list_elem value as both share the same lru_list position. */
+      frame_metadata = victim;
     }
 
-  struct frame_metadata *frame_metadata =
-    malloc (sizeof (struct frame_metadata));
-  frame_metadata->frame = frame;
+  /* If sufficient main memory allows the frame to be directly allocated,
+     we must update the frame table with a new entry, and grow lru_list. */
+  else
+    {
+      /* 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
+         represented by lru_list. Must explicitly handle the case where the
+         circular queue is empty (when next_victim == NULL). */
+      if (next_victim == NULL)
+        {
+          list_push_back (&lru_list, &frame_metadata->list_elem);
+          next_victim = &frame_metadata->list_elem;
+        }
+      else
+        {
+          struct list_elem *lru_tail = lru_prev (next_victim);
+          list_insert (lru_tail, &frame_metadata->list_elem);
+        }
+
+      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;
+}
 
-  /* Newly faulted pages begin at the head of the inactive list. */
-  lock_acquire (&inactive_lock);
-  list_push_front (&inactive_list, &frame_metadata->list_elem);
-  lock_release (&inactive_lock);
+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);
 
-  /* Finally, insert frame metadata within the frame table, with the key as its
-     allocated kernel address. */
-  hash_replace (&frame_table, &frame_metadata->hash_elem);
+  frame_metadata->pinned = true;
+}
 
-  return frame;
+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 active/inactive list, and freeing the underlying
-   page memory. Panics if the frame isn't active in memory. */
+   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;
-    key_metadata.frame = frame;
+    struct frame_metadata *frame_metadata = frame_metadata_find (frame);
+    if (frame_metadata == NULL)
+      PANIC ("Attempted to free a frame at kernel address %p, "
+             "but this address is not allocated!\n",
+             frame);
 
-    struct hash_elem *e =
-      hash_delete (&frame_table, &key_metadata.hash_elem);
-    if (e == NULL) PANIC ("Attempted to free a frame without a corresponding "
-                          "kernel address!\n");
-
-    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
+       next_victim to either be the next least recently used page, or NULL
+       if no pages are loaded in main memory. */
+    if (&frame_metadata->list_elem == next_victim)
+      {
+        if (list_empty (&lru_list))
+          next_victim = NULL;
+        else
+          next_victim = lru_next (next_victim);
+      }
+    lock_release (&lru_lock);
+
     free (frame_metadata);
     palloc_free_page (frame);
   }
 
-/* Obtain a pointer to the metadata of the frame we should evict next. */
+/* 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)
   {
-    lock_acquire (&inactive_lock);
-    if (list_empty (&inactive_list))
+    struct list_elem *ve = next_victim;
+    struct frame_metadata *frame_metadata;
+    bool found = false;
+    while (!found)
       {
-        return NULL;
-      }
-    else
-      {
-        struct list_elem *victim_elem = list_pop_back (&inactive_list);
-        lock_release (&inactive_lock);
-        
-        return list_entry (victim_elem, struct frame_metadata, list_elem);
+        frame_metadata = list_entry (ve, struct frame_metadata, list_elem);
+        ve = lru_next (ve);
+        struct list_elem *oe;
+
+        /* Skip pinned frames */
+        if (frame_metadata->pinned)
+          continue;
+
+        /* Returns once a frame that was not accessed by any owner is found. */
+        found = true;
+        for (oe = list_begin (&frame_metadata->owners);
+             oe != list_end (&frame_metadata->owners); oe = list_next (oe))
+          {
+            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 = 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
@@ -168,12 +355,47 @@ 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
+   (wrapping around the list at the tail). */
+static struct list_elem *
+lru_next (struct list_elem *e)
+{
+  if (!list_empty (&lru_list) && e == list_back (&lru_list))
+    return list_front (&lru_list);
+
+  return list_next (e);
+}
+
+/* Returns the previous 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 head). */
+static struct list_elem *
+lru_prev (struct list_elem *e)
+{
+  if (!list_empty (&lru_list) && e == list_front (&lru_list))
+    return list_back (&lru_list);
+
+  return list_prev (e);
+}

src/vm/frame.h

@@ -4,8 +4,19 @@
 #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/mmap.c

@@ -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;
 
@@ -126,21 +127,3 @@ mmap_cleanup (struct hash_elem *e, void *aux UNUSED)
   struct mmap_entry *mmap = hash_entry (e, struct mmap_entry, elem);
   mmap_unmap (mmap);
 }
-
-/* Updates the 'owner' thread's page table entry for virtual address 'upage'
-   to have a present bit of 0 and stores the specified swap slot value in the
-   entry for later retrieval from disk. */
-void
-page_set_swap (struct thread *owner, void *upage, size_t swap_slot)
-{
-
-}
-
-/* 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. */
-size_t
-page_get_swap (struct thread *owner, void *upage)
-{
-  return 0;
-}

src/vm/page.c

@@ -1,24 +1,57 @@
 #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
-page_hash (const struct hash_elem *e, UNUSED void *aux)
+static unsigned
+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);
+  return hash_ptr (page->upage);
 }
 
 /* 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)
 {
@@ -28,22 +61,100 @@ 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. */
-struct page_entry *
-page_insert (struct file *file, off_t ofs, void *upage, uint32_t read_bytes,
-             uint32_t zero_bytes, bool writable, enum page_type type)
+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. */
+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 = page_get (owner, upage);
+      if (page == NULL)
+        {
+          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
+        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. */
+      page_flag_swap (pte, true);
+      lock_acquire (&page->lock);
+      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 thread *t = thread_current ();
+  struct page_entry *existing = page_get (t, 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;
+  lock_init (&page->lock);
 
   hash_insert (&thread_current ()->pages, &page->elem);
   return page;
@@ -52,13 +163,15 @@ page_insert (struct file *file, off_t ofs, void *upage, uint32_t read_bytes,
 /* 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)
 {
+  lock_acquire (&thread->spt_lock);
   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);
+  lock_release (&thread->spt_lock);
   if (e == NULL)
       return NULL;
 
@@ -66,18 +179,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. */
-  void *frame = frame_alloc (PAL_USER, page->upage, thread_current ());
+  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;
     }
@@ -88,6 +254,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;
   }
@@ -95,6 +263,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;
 }
@@ -104,5 +293,167 @@ 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));
+  lock_acquire (&thread_current ()->spt_lock);
+  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);
+  lock_release (&thread_current ()->spt_lock);
+}
+
+/* Flags the provided page table entry as representing a swapped out page. */
+void
+page_flag_swap (uint32_t *pte, bool set)
+  {
+    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);
+  uint32_t swap_slot_bits = (swap_slot << ADDR_START_BIT) & PTE_ADDR;
+  *pte = (*pte & PTE_FLAGS) | swap_slot_bits;
+
+  invalidate_pagedir (owner->pagedir);
+}
+
+/* Returns true iff the page with user address 'upage' owned by 'owner'
+   is flagged to be in the swap disk via the owner's page table. */
+bool
+page_in_swap (struct thread *owner, void *upage)
+{
+   lock_acquire (&owner->spt_lock);
+   uint32_t *pte = lookup_page (owner->pagedir, upage, false);
+   lock_release (&owner->spt_lock);
+   return page_in_swap_pte (pte);
+}
+
+/* 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 and marks the PTE as not being in swap. */
+size_t
+page_get_swap (struct thread *owner, void *upage)
+{
+   lock_acquire (&owner->spt_lock);  
+   uint32_t *pte = lookup_page (owner->pagedir, upage, false);
+
+   ASSERT (pte != NULL);
+   ASSERT ((*pte & PTE_P) == 0);
+
+   /* Masks the address bits and returns truncated value. */
+   page_flag_swap (pte, false);
+   lock_release (&owner->spt_lock);
+   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,16 +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);
-bool page_less (const struct hash_elem *a_, const struct hash_elem *b_,
-                void *aux);
-struct page_entry *page_insert (struct file *file, off_t ofs, void *upage,
-                                uint32_t read_bytes, uint32_t zero_bytes,
-                                bool writable, enum page_type type);
-struct page_entry *page_get (void *upage);
-bool page_load (struct page_entry *page, bool writable);
-void page_cleanup (struct hash_elem *e, void *aux);
-void page_set_swap (struct thread *, void *, size_t);
-size_t page_get_swap (struct thread *, void *);
+struct shared_file_page
+{
+  struct file *file;
+  void *upage;
+  void *frame;
+  size_t swap_slot;
+  int ref_count;
 
-#endif /* vm/frame.h */
+  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);
+struct page_entry *page_get (struct thread *thread, void *upage);
+bool page_load_file (struct page_entry *page);
+void page_cleanup (struct hash_elem *e, void *aux);
+
+bool page_in_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);
+
+bool page_is_shared_pte (uint32_t *pte);
+void shared_file_pages_init (void);
+
+#endif