Update gitlab CI to only run the tests associated with this feature (mmapped-files).

.gitlab-ci.yml

@@ -32,9 +32,10 @@ test_userprog:
   extends: .pintos_tests
   variables:
     DIR: userprog
+    IGNORE: (tests/userprog/no-vm/multi-oom)
 
 test_vm:
   extends: .pintos_tests
   variables:
     DIR: vm
-    IGNORE: (tests/vm/page-parallel|tests/vm/page-merge-seq|tests/vm/page-merge-par|tests/vm/page-merge-stk|tests/vm/page-merge-mm|tests/vm/mmap-read|tests/vm/mmap-close|tests/vm/mmap-overlap|tests/vm/mmap-twice|tests/vm/mmap-write|tests/vm/mmap-exit|tests/vm/mmap-shuffle|tests/vm/mmap-clean|tests/vm/mmap-inherit|tests/vm/mmap-misalign|tests/vm/mmap-null|tests/vm/mmap-over-code|tests/vm/mmap-over-data|tests/vm/mmap-over-stk|tests/vm/mmap-remove)
+    IGNORE: (tests/vm/pt-grow-stack|tests/vm/pt-grow-pusha|tests/vm/pt-big-stk-obj|tests/vm/pt-overflowstk|tests/vm/pt-write-code2|tests/vm/pt-grow-stk-sc|tests/vm/page-linear|tests/vm/page-parallel|tests/vm/page-merge-seq|tests/vm/page-merge-par|tests/vm/page-merge-stk|tests/vm/page-merge-mm|tests/vm/mmap-over-stk)

src/Makefile.build

@@ -64,9 +64,8 @@ userprog_SRC += userprog/tss.c		# TSS management.
 # Virtual memory code.
 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/stackgrowth.c              # Stack growth functions.
-#vm_SRC = vm/file.c			# Some other file.
 
 # Filesystem code.
 filesys_SRC  = filesys/filesys.c	# Filesystem core.

src/threads/init.c

@@ -31,7 +31,6 @@
 #else
 #include "tests/threads/tests.h"
 #endif
-#include "vm/page.h"
 #ifdef VM
 #include "vm/frame.h"
 #include "devices/swap.h"
@@ -122,7 +121,6 @@ main (void)
   exception_init ();
   syscall_init ();
 #endif
-  shared_files_init ();
 
   /* Start thread scheduler and enable interrupts. */
   thread_start ();

src/threads/thread.c

@@ -15,10 +15,13 @@
 #include "threads/switch.h"
 #include "threads/synch.h"
 #include "threads/vaddr.h"
-#include "vm/page.h"
 #ifdef USERPROG
 #include "userprog/process.h"
 #include "userprog/syscall.h"
+#include "vm/page.h"
+#endif
+#ifdef VM
+#include "vm/mmap.h"
 #endif
 
 /* Random value for struct thread's `magic' member.
@@ -263,14 +266,10 @@ thread_create (const char *name, int priority,
   /* 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);
-  success = success && hash_init (&t->child_results, process_result_hash,
-                                  process_result_less, t);
-#ifdef VM
-  success = success && init_pages (t);
-#endif
-
-  if (!success)
+  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))
     {
       palloc_free_page (t);
       free (t->result);
@@ -278,6 +277,10 @@ thread_create (const char *name, int priority,
     }
 #endif
 
+#ifdef VM
+  mmap_init (t);
+#endif
+
   /* Prepare thread for first run by initializing its stack.
      Do this atomically so intermediate values for the 'stack' 
      member cannot be observed. */

src/threads/thread.h

@@ -135,6 +135,12 @@ struct thread
     /* Shared between thread.c and synch.c. */
     struct list_elem elem;              /* List element. */
 
+    struct hash pages;                  /* Table of open user pages. */
+
+    /* Memory mapped files for user virtual memory. */
+    struct hash mmap_files;             /* List of memory mapped files. */
+    unsigned int mmap_counter;          /* Counter for memory mapped files. */
+
 #ifdef USERPROG
     /* Owned by userprog/process.c. */
     uint32_t *pagedir;                  /* Page directory. */
@@ -143,12 +149,6 @@ struct thread
     struct hash open_files;             /* Hash Table of FD -> Struct File. */
 #endif
 
-#ifdef VM
-  struct hash pages;                    /* Table of open user pages. */
-#endif
-
-    void *curr_esp;
-
     /* Owned by thread.c. */
     unsigned magic;                     /* Detects stack overflow. */
   };

src/userprog/exception.c

@@ -1,26 +1,19 @@
 #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"
-#ifdef VM
-#include "vm/stackgrowth.h"
-#include "vm/frame.h"
-#include "vm/page.h"
-#include "devices/swap.h"
 #include "threads/vaddr.h"
-#include "userprog/pagedir.h"
-#endif
+#include "vm/page.h"
 
 /* Number of page faults processed. */
 static long long page_fault_cnt;
 
 static void kill (struct intr_frame *);
 static void page_fault (struct intr_frame *);
-static bool try_fetch_page (void *upage, bool write);
+bool try_fetch_page (void *upage, bool write);
 
 /* Registers handlers for interrupts that can be caused by user
    programs.
@@ -156,49 +149,24 @@ page_fault (struct intr_frame *f)
   write = (f->error_code & PF_W) != 0;
   user = (f->error_code & PF_U) != 0;
 
-#ifdef VM
+  if (!user)
+  {
+    f->eip = (void *)f->eax;
+    f->eax = 0xffffffff;
+    return;
+  }
+
+
+  /* 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))
+  if (not_present && is_user_vaddr (upage) && upage != NULL)
     {
-      struct thread *t = thread_current ();
-      void *esp = user ? f->esp : t->curr_esp;
-
-      /* 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. */
-      if (page_in_swap (t, fault_addr))
-        {
-          size_t swap_slot = page_get_swap (t, fault_addr);
-          void *kpage = frame_alloc (0, upage, t);
-          swap_in (kpage, swap_slot);
-
-          bool writeable = pagedir_is_writable (t->pagedir, upage);
-          if (pagedir_set_page (t->pagedir, upage, kpage, writeable)) return;
-        }
-
-      /* Handle user page faults that need to be resolved by dynamic
-         stack growth by checking if this is such a fault and responding
-         accordingly. */
-      if (handle_stack_fault (fault_addr, esp)) return;
-
-      /* Handle user page faults that need to be resolved by lazy loading
-         of executable files by checking if they contain entries in the
-         SPT hash map and responding accordingly. */
       if (try_fetch_page (upage, write))
         return;
     }
 
-  /* Allows for page faults within a kernel context to communicate with
-     user pages for sending error codes. */
-  if (!user)
-    {
-      f->eip = (void *)f->eax;
-      f->eax = 0xffffffff;
-      return;
-    }
-#endif
-
   /* 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. */
@@ -210,8 +178,7 @@ page_fault (struct intr_frame *f)
   kill (f);
 }
 
-#ifdef VM
-static bool
+bool
 try_fetch_page (void *upage, bool write)
 {
   /* Check if the page is in the supplemental page table. That is, it is a page
@@ -227,13 +194,16 @@ 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_EXECUTABLE:
-      success = page_load (page);
+    case PAGE_FILE:
+      success = page_load (page, page->writable);
       break;
     default:
       return false;
-    }
+  }
+
+  if (success && page->writable &&
+      !pagedir_is_writable(thread_current()->pagedir, upage))
+    pagedir_set_writable(thread_current()->pagedir, upage, true);
 
   return success;
 }
-#endif

src/userprog/exception.h

@@ -10,5 +10,7 @@
 
 void exception_init (void);
 void exception_print_stats (void);
+bool
+try_fetch_page (void *upage, bool write);
 
 #endif /* userprog/exception.h */

src/userprog/pagedir.c

@@ -5,13 +5,9 @@
 #include "threads/init.h"
 #include "threads/pte.h"
 #include "threads/palloc.h"
-#ifdef VM
-#include "threads/thread.h"
-#include "vm/frame.h"
-#include "vm/page.h"
-#endif
 
 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.
@@ -44,21 +40,8 @@ pagedir_destroy (uint32_t *pd)
         uint32_t *pte;
         
         for (pte = pt; pte < pt + PGSIZE / sizeof *pte; pte++)
-          {
-#ifdef VM
-            if (*pte & PTE_P)
-              {
-                void *page = pte_get_page (*pte);
-                frame_owner_remove (page, thread_current ());
-                // frame_free (page);
-                palloc_free_page (page);
-              }
-            page_cleanup_swap (pte);
-#else
-            if (*pte & PTE_P)
-              palloc_free_page (pte_get_page (*pte));
-#endif
-          }
+          if (*pte & PTE_P) 
+            palloc_free_page (pte_get_page (*pte));
         palloc_free_page (pt);
       }
   palloc_free_page (pd);
@@ -70,7 +53,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. */
-uint32_t *
+static uint32_t *
 lookup_page (uint32_t *pd, const void *vaddr, bool create)
 {
   uint32_t *pt, *pde;
@@ -295,7 +278,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.) */
-void
+static void
 invalidate_pagedir (uint32_t *pd) 
 {
   if (active_pd () == pd) 

src/userprog/pagedir.h

@@ -6,7 +6,6 @@
 
 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);
@@ -17,6 +16,5 @@ 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

@@ -25,6 +25,7 @@
 #include "threads/synch.h"
 #include "devices/timer.h"
 #include "vm/page.h"
+#include "vm/mmap.h"
 #ifdef VM
 #include "vm/frame.h"
 #endif
@@ -172,9 +173,8 @@ start_process (void *proc_start_data)
  to store the command that executed the process. */
   if (data->success)
     {
-      data->success = use_shared_file (exec_file)
-                      && process_init_stack (data->cmd_saveptr, &if_.esp,
-                                             data->file_name);
+      data->success =
+        process_init_stack (data->cmd_saveptr, &if_.esp, data->file_name);
     }
 
   /* Signal that the process has finished attempting to load. */
@@ -364,12 +364,12 @@ process_exit (void)
   struct thread *cur = thread_current ();
   uint32_t *pd;
 
+  /* Unmap all memory mapped files */
+  mmap_destroy ();
+
   /* Clean up all open files */
   hash_destroy (&cur->open_files, fd_cleanup);
-#ifdef VM
   hash_destroy (&cur->pages, page_cleanup);
-  unuse_shared_file (cur->exec_file);
-#endif
 
   /* Close the executable file, implicitly allowing it to be written to. */
   if (cur->exec_file != NULL)
@@ -627,9 +627,6 @@ 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;
 }
@@ -703,7 +700,6 @@ load_segment (struct file *file, off_t ofs, uint8_t *upage,
   ASSERT (pg_ofs (upage) == 0);
   ASSERT (ofs % PGSIZE == 0);
 
-#ifdef VM
   while (read_bytes > 0 || zero_bytes > 0)
     {
       /* Calculate how to fill this page.
@@ -714,7 +710,7 @@ load_segment (struct file *file, off_t ofs, uint8_t *upage,
 
       /* 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_EXECUTABLE) == NULL)
+                       writable, PAGE_FILE) == NULL)
         return false;
 
       /* Advance. */
@@ -724,58 +720,6 @@ load_segment (struct file *file, off_t ofs, uint8_t *upage,
       upage += PGSIZE;
     }
   return true;
-#else
-  file_seek (file, ofs);
-  while (read_bytes > 0 || zero_bytes > 0) 
-    {
-      /* Calculate how to fill this page.
-         We will read PAGE_READ_BYTES bytes from FILE
-         and zero the final PAGE_ZERO_BYTES bytes. */
-      size_t page_read_bytes = read_bytes < PGSIZE ? read_bytes : PGSIZE;
-      size_t page_zero_bytes = PGSIZE - page_read_bytes;
-      
-      /* Check if virtual page already allocated */
-      struct thread *t = thread_current ();
-      uint8_t *kpage = pagedir_get_page (t->pagedir, upage);
-      
-      if (kpage == NULL){
-        
-        /* Get a new page of memory. */
-        kpage = get_usr_kpage (0, upage);
-        if (kpage == NULL){
-          return false;
-        }
-        
-        /* Add the page to the process's address space. */
-        if (!install_page (upage, kpage, writable)) 
-        {
-          free_usr_kpage (kpage);
-          return false; 
-        }     
-        
-      } else {
-        
-        /* Check if writable flag for the page should be updated */
-        if(writable && !pagedir_is_writable(t->pagedir, upage)){
-          pagedir_set_writable(t->pagedir, upage, writable); 
-        }
-        
-      }
-
-      /* Load data into the page. */
-      if (file_read (file, kpage, page_read_bytes) != (int) page_read_bytes){
-        return false; 
-      }
-      memset (kpage + page_read_bytes, 0, page_zero_bytes);
-
-      /* Advance. */
-      read_bytes -= page_read_bytes;
-      zero_bytes -= page_zero_bytes;
-      ofs += PGSIZE;
-      upage += PGSIZE;
-    }
-  return true;
-#endif
 }
 
 /* Create a minimal stack by mapping a zeroed page at the top of
@@ -826,7 +770,6 @@ static void
 free_usr_kpage (void *kpage)
 {
 #ifdef VM
-  frame_owner_remove (kpage, thread_current ());
   frame_free (kpage);
 #else
   palloc_free_page (kpage);

src/userprog/syscall.c

@@ -11,12 +11,14 @@
 #include "threads/synch.h"
 #include "userprog/process.h"
 #include "userprog/pagedir.h"
+#include "vm/page.h"
+#include "vm/mmap.h"
 #include <stdio.h>
-#include <stdbool.h>
 #include <syscall-nr.h>
 
 #define MAX_SYSCALL_ARGS 3
 #define EXIT_FAILURE -1
+#define MMAP_FAILURE -1
 
 struct open_file
   {
@@ -46,13 +48,12 @@ static int syscall_write (int fd, const void *buffer, unsigned size);
 static void syscall_seek (int fd, unsigned position);
 static unsigned syscall_tell (int fd);
 static void syscall_close (int fd);
+static mapid_t syscall_mmap (int fd, void *addr);
+static void syscall_munmap (mapid_t mapping);
 
 static struct open_file *fd_get_file (int fd);
-static void validate_user_pointer (const void *ptr, size_t size,
-                                   bool check_write);
-static void validate_user_string (const char *str, bool check_write);
-static int get_user (const uint8_t *);
-static bool put_user (uint8_t *, uint8_t);
+static void validate_user_pointer (const void *start, size_t size, bool write);
+static void validate_user_string (const char *str);
 
 /* A struct defining a syscall_function pointer along with its arity. */
 struct syscall_arguments
@@ -78,6 +79,8 @@ static const struct syscall_arguments syscall_lookup[] =
   [SYS_SEEK] = {(syscall_function) syscall_seek, 2},
   [SYS_TELL] = {(syscall_function) syscall_tell, 1},
   [SYS_CLOSE] = {(syscall_function) syscall_close, 1},
+  [SYS_MMAP] = {(syscall_function) syscall_mmap, 2},
+  [SYS_MUNMAP] = {(syscall_function) syscall_munmap, 1}
 };
 
 /* The number of syscall functions (i.e, number of elements) within the
@@ -102,8 +105,7 @@ 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;
-  thread_current ()->curr_esp = f->esp;
+  uintptr_t syscall_number = *(int *) f->esp;
 
   /* Ensures the number corresponds to a system call that can be handled. */
   if (syscall_number >= LOOKUP_SIZE)
@@ -114,9 +116,10 @@ syscall_handler (struct intr_frame *f)
   /* Next, read and copy the arguments from the stack pointer. */
   validate_user_pointer (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. */
@@ -145,7 +148,8 @@ syscall_exit (int status)
 static pid_t
 syscall_exec (const char *cmd_line)
 {
-  validate_user_string (cmd_line, false);
+  /* Validate the user string before executing the process. */
+  validate_user_string (cmd_line);
 
   return process_execute (cmd_line); /* Returns the PID of the new process */
 }
@@ -164,7 +168,8 @@ syscall_wait (pid_t pid)
 static bool
 syscall_create (const char *file, unsigned initial_size)
 {
-  validate_user_string (file, false);
+  /* Validate the user string before creating the file. */
+  validate_user_string (file);
 
   /* Acquire the file system lock to prevent race conditions. */
   lock_acquire (&filesys_lock);
@@ -181,7 +186,8 @@ syscall_create (const char *file, unsigned initial_size)
 static bool
 syscall_remove (const char *file)
 {
-  validate_user_string (file, false);
+  /* Validate the user string before removing the file. */
+  validate_user_string (file);
 
   /* Acquire the file system lock to prevent race conditions. */
   lock_acquire (&filesys_lock);
@@ -199,7 +205,8 @@ syscall_remove (const char *file)
 static int
 syscall_open (const char *file)
 {
-  validate_user_string (file, false);
+  /* Validate the user string before opening the file. */
+  validate_user_string (file);
 
   /* Acquire the file system lock to prevent race conditions. */
   lock_acquire (&filesys_lock);
@@ -265,6 +272,7 @@ 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)
@@ -308,6 +316,7 @@ 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)
@@ -392,6 +401,79 @@ syscall_close (int fd)
     }
 }
 
+/* Handles the syscall for memory mapping a file. */
+static mapid_t
+syscall_mmap (int fd, void *addr)
+{
+  /* Ensure the FD is for a file in the filesystem (not STDIN or STDOUT). */
+  if (fd == STDOUT_FILENO || fd == STDIN_FILENO)
+    return MMAP_FAILURE;
+
+  /* Validate that there is a file associated with the given FD. */
+  struct open_file *file_info = fd_get_file (fd);
+  if (file_info == NULL)
+    return MMAP_FAILURE;
+
+  /* Ensure that the address is page-aligned and it's neither NULL nor zero. */
+  if (addr == 0 || addr == NULL || pg_ofs (addr) != 0)
+    return MMAP_FAILURE;
+
+  /* Reopen the file to obtain a separate and independent reference to the file
+     for the mapping. */
+  struct file *file = file_reopen (file_info->file);
+  if (file == NULL)
+    return MMAP_FAILURE;
+
+  /* Get the size of the file. Mmap fails if the file is empty. */
+  off_t file_size = file_length (file);
+  if (file_size == 0)
+    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)
+        return MMAP_FAILURE;
+    }
+
+  /* Map the file data into the user virtual memory starting from addr. */
+  for (off_t ofs = 0; ofs < file_size; ofs += PGSIZE)
+    {
+      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,
+                       PAGE_FILE) == NULL)
+        return MMAP_FAILURE;
+    }
+
+  /* Create a new mapping for the file. */
+  struct mmap_entry *mmap = mmap_insert (file, addr);
+  if (mmap == NULL)
+      return MMAP_FAILURE;
+
+
+  return mmap->mapping;
+}
+
+/* Handles the syscall for unmapping a memory mapped file.
+
+    Pre: mapping is a valid mapping identifier returned by mmap syscall. */
+static void
+syscall_munmap (mapid_t mapping)
+{
+  /* Get the mmap entry from the mapping identifier. */
+  struct mmap_entry *mmap = mmap_get (mapping);
+
+  /* Delete the mmap entry from the hash table. */
+  hash_delete (&thread_current ()->mmap_files, &mmap->elem);
+
+  /* Unmap the mmap entry: free the pages and write back to the file if
+     necessary. NOTE. freeing and cleaning up is also handled by mmap_unmap. */
+  mmap_unmap (mmap);
+}
+
 /* Hashing function needed for the open_file table. Returns a hash for an entry,
    based on its FD. */
 unsigned
@@ -450,91 +532,67 @@ fd_get_file (int fd)
   return hash_entry (e, struct open_file, elem);
 }
 
-/* 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. */
+/* 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. */
 static void
-validate_user_pointer (const void *ptr, size_t size, bool check_write)
+validate_user_pointer (const void *start, size_t size, bool write)
 {
+  /* If the size is 0, we do not need to check anything. */
   if (size == 0)
     return;
-  /* ptr < ptr + size - 1, so sufficient to check that (ptr + size -1) is a
-     valid user virtual memory address. */
-  void *last = ptr + size - 1;
-  if (!is_user_vaddr (last))
+
+  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))
     syscall_exit (EXIT_FAILURE);
-  ptr = pg_round_down (ptr);
-  while (ptr <= last)
-    {
-      int result;
-      /* Check read access to pointer. */
-      if ((result = get_user (ptr)) == -1)
-        syscall_exit (EXIT_FAILURE);
-      /* Check write access to pointer (if required). */
-      if (check_write && !put_user (ptr, result))
-        syscall_exit (EXIT_FAILURE);
-      ptr += PGSIZE;
-    }
+
+  /* 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 of a C-string starting at ptr is fully contained within valid
-   user virtual memory. thread_exit () if the memory is invalid. */
+/* 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 *ptr, bool check_write)
+validate_user_string (const char *str)
 {
-  size_t offset = (uintptr_t) ptr % PGSIZE;
+  /* 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 (;;)
-    {
-      void *page = pg_round_down (ptr);
+  {
+    void *page = pg_round_down (str);
 
-      if (!is_user_vaddr (page))
-        syscall_exit (EXIT_FAILURE);
-      if (!is_user_vaddr (ptr))
-        syscall_exit (EXIT_FAILURE);
-      int result;
-      if ((result = get_user ((const uint8_t *)ptr)) == -1)
-        syscall_exit (EXIT_FAILURE);
-      if (check_write && !put_user ((uint8_t *)ptr, result))
-        syscall_exit (EXIT_FAILURE);
+    /* 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)))
+      syscall_exit (EXIT_FAILURE);
 
-      while (offset < PGSIZE)
+    while (offset < PGSIZE)
       {
-        if (*ptr == '\0')
+        if (*str == '\0')
           return; /* We reached the end of the string without issues. */
 
-        ptr++;
+        str++;
         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;
+    offset = 0; /* Next page will start at the beginning. */
+  }
 }

src/vm/frame.c

@@ -5,10 +5,8 @@
 
 #include "frame.h"
 #include "page.h"
-#include "filesys/file.h"
 #include "threads/malloc.h"
 #include "threads/vaddr.h"
-#include "userprog/pagedir.h"
 #include "threads/synch.h"
 #include "devices/swap.h"
 
@@ -16,35 +14,26 @@
    to its corresponding 'frame_metadata'.*/
 struct hash frame_table;
 
-/* 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 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;
 
-/* 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;
+/* 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;
 
 /* Synchronisation variables. */
-/* Protects access to 'lru_list'. */
-struct lock lru_lock;
-
-struct frame_owner
-{
-  struct thread *thread; /* Pointer to the thread referenced by the owner.*/
-  struct list_elem elem; /* List element for the owners list in
-                            frame_metadata. */
-};
+/* Protects access to the 'inactive' list. */
+struct lock inactive_lock;
 
 struct frame_metadata
   {
      void *frame;  /* The kernel virtual address holding the frame. */
      void *upage; /* The user virtual address pointing to the frame. */
-     struct list owners;          /* List of owners of the frame. */
+     struct thread *owner; /* Pointer to the thread that owns the frame. */
      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. */
@@ -56,26 +45,22 @@ struct frame_metadata
 hash_hash_func frame_metadata_hash;
 hash_less_func frame_metadata_less;
 
-static struct frame_metadata *frame_metadata_find (void *frame);
-
-static struct list_elem *lru_next (struct list_elem *e);
-static struct list_elem *lru_prev (struct list_elem *e);
 static struct frame_metadata *get_victim (void);
 
 /* Initialize the frame system by initializing the frame (hash) table with
    the frame_metadata hashing and comparison functions, as well as initializing
-   'lru_list' and its associated synchronisation primitives. */
+   the active & inactive lists. Also initializes the system's 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);
 
-  list_init (&lru_list);
-  lock_init (&lru_lock);
+  lock_init (&inactive_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
@@ -84,10 +69,7 @@ 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,
@@ -95,232 +77,78 @@ frame_alloc (enum palloc_flags flags, void *upage, struct thread *owner)
      into disk. */
   if (frame == NULL)
     {
-      /* 1. Obtain victim. */
-      if (next_victim == NULL)
-        PANIC ("Couldn't allocate a single page to main memory!\n");
-
+      /* 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 ();
-      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
-         been modified *before* eviction begins to prevent the owner of the
-         victim page from accessing/modifying it mid-eviction. */
-      struct list_elem *e;
-      struct file *file = NULL;
-      for (e = list_begin (&victim->owners); e != list_end (&victim->owners);
-           e = list_next (e))
-        {
-          struct frame_owner *frame_owner
-              = list_entry (e, struct frame_owner, elem);
-          file = frame_owner->thread->exec_file;
-          pagedir_clear_page (frame_owner->thread->pagedir, victim->upage);
-        }
-
-      /* If file is found then it must be the same for all owners, and might
-         have a single shared page entry. */
-      struct shared_page_entry *shared_page = NULL;
-      if (file != NULL)
-        {
-          lock_acquire (&shared_files_lock);
-          shared_page = shared_page_get (file, victim->upage);
-          ASSERT (shared_page == NULL || shared_page->frame != NULL);
-          if (shared_page == NULL)
-            lock_release (&shared_files_lock);
-        }
-
-      // TODO: Lock PTE of victim page for victim process.
+      if (victim == NULL)
+        return NULL;
 
       size_t swap_slot = swap_out (victim->frame);
-
-      /* If frame had a shared page, unsign it, and set the swap slot.
-         Otherwise, set the swap slot in the pagedir of the owners threads. */
-      if (shared_page != NULL)
-        {
-          shared_page->frame = NULL;
-          shared_page->swap_slot = swap_slot;
-          lock_release (&shared_files_lock);
-        }
-      else
-        for (e = list_begin (&victim->owners); e != list_end (&victim->owners);
-             e = list_next (e))
-          {
-            struct frame_owner *frame_owner
-                = list_entry (e, struct frame_owner, elem);
-            page_set_swap (frame_owner->thread, victim->upage, swap_slot);
-          }
+      page_set_swap (victim->owner, victim->upage, swap_slot);
 
       /* If zero flag is set, zero out the victim page. */
       if (flags & PAL_ZERO)
         memset (victim->frame, 0, PGSIZE);
 
-      /* 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;
-    }
-
-  /* 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));
-      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);
+      frame = victim->frame;
     }
 
+  struct frame_metadata *frame_metadata =
+    malloc (sizeof (struct frame_metadata));
+  frame_metadata->frame = frame;
   frame_metadata->upage = upage;
-  list_init (&frame_metadata->owners);
-  struct frame_owner *frame_owner = malloc (sizeof (struct frame_owner));
-  frame_owner->thread = owner;
-  list_push_back (&frame_metadata->owners, &frame_owner->elem);
-  lock_release (&lru_lock);
+  frame_metadata->owner = owner;
 
-  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);
 
-/* 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;
+  /* Finally, insert frame metadata within the frame table, with the key as its
+     allocated kernel address. */
+  hash_replace (&frame_table, &frame_metadata->hash_elem);
 
-  struct frame_owner *frame_owner = malloc (sizeof (struct frame_owner));
-  if (frame_owner == NULL)
-    return false;
-  frame_owner->thread = 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->thread == owner)
-        {
-          list_remove (&frame_owner->elem);
-          free (frame_owner);
-          return;
-        }
-    }
-  NOT_REACHED ();
+  return frame;
 }
 
 /* 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. */
+   frame table as well as active/inactive list, and freeing the underlying
+   page memory. Panics if the frame isn't active in memory. */
 void
 frame_free (void *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 frame_metadata key_metadata;
+    key_metadata.frame = frame;
 
-    ASSERT (list_empty (&frame_metadata->owners));
+    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");
 
-    lock_acquire (&lru_lock);
+    struct frame_metadata *frame_metadata =
+      hash_entry (e, struct 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);
   }
 
-/* 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. */
+/* Obtain a pointer to the metadata of the frame we should evict next. */
 static struct frame_metadata *
 get_victim (void)
   {
-    struct list_elem *ve = next_victim;
-    struct frame_metadata *frame_metadata;
-    bool found = false;
-    while (!found)
+    lock_acquire (&inactive_lock);
+    if (list_empty (&inactive_list))
       {
-        frame_metadata = list_entry (ve, struct frame_metadata, list_elem);
-        void *upage = frame_metadata->upage;
-        ve = lru_next (ve);
-
-        /* Check whether any owner thread has accessed the page. */
-        found = true;
-        struct list_elem *oe;
-        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->thread->pagedir;
-            if (pagedir_is_accessed (pd, upage))
-              {
-                found = false;
-                pagedir_set_accessed (pd, upage, false);
-              }
-          }
+        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);
       }
-
-    next_victim = ve;
-    return frame_metadata;
   }
 
 /* Hash function for frame metadata, used for storing entries in the
@@ -349,26 +177,3 @@ frame_metadata_less (const struct hash_elem *a_, const struct hash_elem *b_,
     return a->frame < b->frame;
   }
 
-/* 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

@@ -8,7 +8,4 @@ void frame_init (void);
 void *frame_alloc (enum palloc_flags, void *, struct thread *);
 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

@@ -0,0 +1,146 @@
+#include "mmap.h"
+#include "page.h"
+#include "threads/vaddr.h"
+#include "threads/malloc.h"
+#include "userprog/syscall.h"
+#include "userprog/pagedir.h"
+#include <stdio.h>
+
+static unsigned mmap_hash (const struct hash_elem *e, void *aux);
+static bool mmap_less (const struct hash_elem *a_, const struct hash_elem *b_,
+                void *aux);
+static void mmap_cleanup(struct hash_elem *e, void *aux);
+
+/* Initializes the mmap table for the given thread, setting the mmap counter to
+   0 and initializing the hash table. */
+bool
+mmap_init (struct thread *t)
+{
+  t->mmap_counter = 0;
+  return hash_init (&t->mmap_files, mmap_hash, mmap_less, NULL);
+}
+
+struct mmap_entry *
+mmap_get (mapid_t mapping)
+{
+  struct mmap_entry fake_mmap_entry;
+  fake_mmap_entry.mapping = mapping;
+
+  struct hash_elem *e
+    = hash_find (&thread_current ()->mmap_files, &fake_mmap_entry.elem);
+
+  if (e == NULL)
+    return NULL;
+
+  return hash_entry (e, struct mmap_entry, elem);
+}
+
+/* Inserts a new mmap entry into the mmap table for the current thread. Upage
+   is the start address of the file data in the user VM. */
+struct mmap_entry *
+mmap_insert (struct file *file, void *upage)
+{
+  if (file == NULL || upage == NULL)
+    return NULL;
+
+  struct mmap_entry *mmap = malloc (sizeof (struct mmap_entry));
+  if (mmap == NULL)
+    return NULL;
+
+  mmap->mapping = thread_current ()->mmap_counter++;
+  mmap->file = file;
+  mmap->upage = upage;
+
+  hash_insert (&thread_current ()->mmap_files, &mmap->elem);
+  return mmap;
+}
+
+/* Unmaps the given mmap entry from the current thread's mmap table. */
+void
+mmap_unmap (struct mmap_entry *mmap)
+{
+  if (mmap == NULL)
+    return;
+
+  /* Free all the pages associated with the mapping, writing back to the file
+     if necessary. */
+  off_t length = file_length (mmap->file);
+  for (off_t ofs = 0; ofs < length; ofs += PGSIZE)
+  {
+    void *upage = mmap->upage + ofs;
+
+    /* Get the SPT page entry for this page. */
+    struct page_entry *page = page_get(upage);
+    if (page == NULL)
+      continue;
+
+    /* Write the page back to the file if it is dirty. */
+    if (pagedir_is_dirty (thread_current ()->pagedir, upage))
+    {
+      lock_acquire (&filesys_lock);
+      file_write_at (mmap->file, upage, page->read_bytes, ofs);
+      lock_release (&filesys_lock);
+    }
+
+    /* Remove the page from the supplemental page table. */
+    hash_delete (&thread_current ()->pages, &page->elem);
+  }
+
+  file_close (mmap->file);
+  free (mmap);
+}
+
+/* Destroys the mmap table for the current thread. Frees all the memory
+   allocated for the mmap entries. */
+void
+mmap_destroy (void)
+{
+  hash_destroy (&thread_current ()->mmap_files, mmap_cleanup);
+}
+
+/* A hash function for the mmap table. Returns a hash for an entry, based on its
+   mapping. */
+static unsigned
+mmap_hash (const struct hash_elem *e, void *aux UNUSED)
+{
+  return hash_entry (e, struct mmap_entry, elem)->mapping;
+}
+
+/* A comparator function for the mmap table. Compares two entries based on their
+   mappings. */
+static bool
+mmap_less (const struct hash_elem *a_, const struct hash_elem *b_,
+                void *aux UNUSED)
+{
+  const struct mmap_entry *a = hash_entry (a_, struct mmap_entry, elem);
+  const struct mmap_entry *b = hash_entry (b_, struct mmap_entry, elem);
+
+  return a->mapping < b->mapping;
+}
+
+/* Cleans up the mmap table for the current thread. Implicitly unmaps the mmap
+   entry, freeing pages and writing back to the file if necessary. */
+static void
+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/mmap.h

@@ -0,0 +1,27 @@
+#ifndef VM_MMAP_H
+#define VM_MMAP_H
+
+#include <hash.h>
+#include "threads/thread.h"
+#include "filesys/file.h"
+
+/* A mapping identifier type. */
+typedef unsigned mapid_t;
+
+/* A structure to represent a memory mapped file. */
+struct mmap_entry {
+  mapid_t mapping;      /* The mapping identifier of the mapped file. */
+  struct file *file;    /* A pointer to the file that is being mapped. */
+  void *upage;          /* The start address of the file data in the user VM. */
+
+  struct hash_elem elem; /* An elem for the hash table. */
+};
+
+bool mmap_init (struct thread *t);
+struct mmap_entry *mmap_get (mapid_t mapping);
+struct mmap_entry *mmap_insert (struct file *file, void *upage);
+void mmap_unmap (struct mmap_entry *mmap);
+void mmap_umap_all (void);
+void mmap_destroy (void);
+
+#endif /* vm/mmap.h */

src/vm/page.c

@@ -1,49 +1,16 @@
 #include "page.h"
 #include <string.h>
 #include <stdio.h>
-#include "devices/swap.h"
 #include "filesys/file.h"
-#include "filesys/filesys.h"
 #include "threads/malloc.h"
 #include "threads/palloc.h"
-#include "threads/pte.h"
-#include "threads/vaddr.h"
-#include "userprog/pagedir.h"
 #include "userprog/process.h"
 #include "vm/frame.h"
 
-#define SWAP_FLAG_BIT 9
-#define ADDR_START_BIT 12
-
-struct hash shared_files;
-
-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 struct shared_file_entry *shared_file_insert (struct file *file);
-static struct shared_page_entry *shared_page_insert (struct file *file,
-                                                     void *upage, void *frame);
-static struct shared_file_entry *shared_file_get (struct file *file);
-static unsigned shared_file_hash (const struct hash_elem *e, void *aux UNUSED);
-static bool shared_file_less (const struct hash_elem *a_,
-                              const struct hash_elem *b_, void *aux UNUSED);
-static unsigned shared_page_hash (const struct hash_elem *e, void *aux UNUSED);
-static bool shared_page_less (const struct hash_elem *a_,
-                              const struct hash_elem *b_, void *aux UNUSED);
-static void shared_page_cleanup (struct hash_elem *e, void *aux UNUSED);
-static void page_unset_swap (struct thread *owner, void *upage);
-
-/* Initialise a thread's supplemental pages table. */
-bool
-init_pages (struct thread *t)
-{
-  return hash_init (&t->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, void *aux UNUSED)
+page_hash (const struct hash_elem *e, UNUSED void *aux)
 {
   struct page_entry *page = hash_entry (e, struct page_entry, elem);
   return hash_ptr(page->upage);
@@ -66,28 +33,18 @@ 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)
 {
-  /* 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;
-    }
-
-  /* Otherwise allocate a new one. */
   struct page_entry *page = malloc(sizeof (struct page_entry));
   if (page == NULL)
     return NULL;
+
   page->file = file;
   page->offset = ofs;
   page->upage = upage;
   page->read_bytes = read_bytes;
   page->zero_bytes = zero_bytes;
   page->writable = writable;
-  page->shared = false;
   page->type = type;
+
   hash_insert (&thread_current ()->pages, &page->elem);
   return page;
 }
@@ -102,7 +59,6 @@ page_get (void *upage)
 
   struct hash_elem *e
     = hash_find (&thread_current ()->pages, &fake_page_entry.elem);
-
   if (e == NULL)
       return NULL;
 
@@ -110,79 +66,37 @@ page_get (void *upage)
 }
 
 bool
-page_load (struct page_entry *page)
+page_load (struct page_entry *page, bool writable)
 {
-  struct thread *t = thread_current ();
-  /* If the page is read-only, we want to check if it is a shared page already
-     loaded into memory. If it is, we can just map the page to the frame. */
-  if (!page->writable)
-    {
-      lock_acquire (&shared_files_lock);
-      struct shared_page_entry *shared_page =
-        shared_page_get (page->file, page->upage);
-
-      /* Mark page as shared and install the shared frame. */
-      if (shared_page != NULL)
-        {
-          if (shared_page->frame == NULL)
-            {
-              void *frame = frame_alloc (PAL_USER, page->upage, t);
-              if (frame == NULL)
-                return false;
-              shared_page->frame = frame;
-            }
-          lock_release (&shared_files_lock);
-          if (!install_page (page->upage, shared_page->frame, false))
-            return false;
-          page->shared = true;
-          return true;
-        }
-    }
   /* 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, t);
+  void *frame = frame_alloc (PAL_USER, page->upage, thread_current ());
   if (frame == NULL)
     PANIC ("Could not allocate a frame to load page into memory.");
 
-  /* Ensure page is not marked as shared while it doesn't exist in the
-     shared_files table, to avoid memory leaks. */
-  page->shared = false;
-
   /* Map the page to the frame. */
-  if (!install_page (page->upage, frame, page->writable))
-    goto fail;
+  if (!install_page (page->upage, frame, writable))
+    {
+      frame_free (frame);
+      return false;
+    }
 
   /* Move the file pointer to the correct location in the file. Then, read the
      data from the file into the frame. Checks that we were able to read the
      expected number of bytes. */
   file_seek (page->file, page->offset);
   if (file_read (page->file, frame, page->read_bytes) != (int) page->read_bytes)
-    goto fail;
+  {
+    frame_free (frame);
+    return false;
+  }
 
   /* Zero out the remaining bytes in the frame. */
   memset (frame + page->read_bytes, 0, page->zero_bytes);
 
-  /* If the page is read-only, we need to add it to the shared pages table. */
-  if (!page->writable)
-    {
-      struct shared_page_entry *shared_page
-          = shared_page_insert (page->file, page->upage, frame);
-      if (shared_page == NULL)
-        goto fail;
-      lock_release (&shared_files_lock);
-      page->shared = true;
-    }
-
   /* Mark the page as loaded successfully. */
   return true;
-
-fail:
-  if (!page->writable)
-    lock_release (&shared_files_lock);
-  frame_owner_remove (frame, t);
-  frame_free (frame);
-  return false;
 }
 
 /* Function to clean up a page_entry. Given the elem of that page_entry, frees
@@ -190,273 +104,5 @@ fail:
 void
 page_cleanup (struct hash_elem *e, void *aux UNUSED)
 {
-  struct thread *t = thread_current ();
-  struct page_entry *page = hash_entry (e, struct page_entry, elem);
-
-  /* If page is shared then mark it as not present and not in swap, to avoid
-   * being freed. */
-  uint32_t *pd = t->pagedir;
-  if (pd != NULL && page->shared)
-    {
-      frame_owner_remove (pagedir_get_page (pd, page->upage), t);
-      pagedir_clear_page (pd, page->upage);
-      page_unset_swap (t, page->upage);
-    }
-  free (page);
+  free (hash_entry (e, struct page_entry, elem));
 }
-
-/* Initialise the shared files and table and lock. */
-void
-shared_files_init ()
-{
-  lock_init (&shared_files_lock);
-  if (!hash_init (&shared_files, shared_file_hash, shared_file_less, NULL))
-    PANIC ("Failed to initialise shared_files table.");
-}
-
-bool
-use_shared_file (struct file *file)
-{
-  lock_acquire (&shared_files_lock);
-  struct shared_file_entry *shared_file = shared_file_get (file);
-  if (shared_file == NULL)
-    {
-      shared_file = shared_file_insert (file);
-      if (shared_file == NULL)
-        {
-          lock_release (&shared_files_lock);
-          return false;
-        }
-    }
-  shared_file->ref_count++;
-  lock_release (&shared_files_lock);
-  return true;
-}
-
-bool
-unuse_shared_file (struct file *file)
-{
-  lock_acquire (&shared_files_lock);
-  struct shared_file_entry *shared_file = shared_file_get (file);
-  if (shared_file == NULL)
-    {
-      lock_release (&shared_files_lock);
-      return false;
-    }
-  shared_file->ref_count--;
-  if (shared_file->ref_count <= 0)
-    {
-      hash_destroy (&shared_file->pages, shared_page_cleanup);
-      hash_delete (&shared_files, &shared_file->elem);
-      free (shared_file);
-    }
-  lock_release (&shared_files_lock);
-}
-
-static void
-shared_page_cleanup (struct hash_elem *e, void *aux UNUSED)
-{
-  struct shared_page_entry *shared_page
-      = hash_entry (e, struct shared_page_entry, elem);
-  if (shared_page->frame == NULL)
-    swap_drop (shared_page->swap_slot);
-  else
-    /* Note: ref_count <= 0, so it is guaranteed that the frame is unused. */
-    frame_free (shared_page->frame);
-  free (shared_page);
-}
-
-/* Hashing function needed for the shared_file table. Returns a hash for an
-   entry based on its file pointer. */
-static unsigned
-shared_file_hash (const struct hash_elem *e, void *aux UNUSED)
-{
-  return file_hash (hash_entry (e, struct shared_file_entry, elem)->file);
-}
-
-/* Less function needed for the shared_file table. */
-static bool
-shared_file_less (const struct hash_elem *a_, const struct hash_elem *b_,
-                  void *aux UNUSED)
-{
-  const struct shared_file_entry *a = hash_entry (a_, struct shared_file_entry,
-                                                  elem);
-  const struct shared_file_entry *b = hash_entry (b_, struct shared_file_entry,
-                                                  elem);
-
-  return !file_compare (a->file, b->file);
-}
-
-/* Hashing function needed for the shared pages table. Returns a hash for an
-   entry based on its user virtual address (upage) pointer. */
-static unsigned
-shared_page_hash (const struct hash_elem *e, void *aux UNUSED)
-{
-  return hash_ptr (hash_entry (e, struct shared_page_entry, elem)->upage);
-}
-
-/* Less function needed for the shared pages table. */
-static bool
-shared_page_less (const struct hash_elem *a_, const struct hash_elem *b_,
-                  void *aux UNUSED)
-{
-  const struct shared_page_entry *a = hash_entry (a_, struct shared_page_entry,
-                                                  elem);
-  const struct shared_page_entry *b = hash_entry (b_, struct shared_page_entry,
-                                                  elem);
-
-  return a->upage < b->upage;
-}
-
-static struct shared_file_entry *
-shared_file_get (struct file *file)
-{
-  struct shared_file_entry fake_shared_file;
-  fake_shared_file.file = file;
-
-  struct hash_elem *e = hash_find (&shared_files, &fake_shared_file.elem);
-
-  if (e == NULL)
-    return NULL;
-
-  return hash_entry (e, struct shared_file_entry, elem);
-}
-
-/* Gets a shared_page_entry from the shared_pages table using the file and upage
-   of the page. Returns NULL if no such page_entry exists in the hash map.*/
-struct shared_page_entry *
-shared_page_get (struct file *file, void *upage)
-{
-  /* Search first for the file within the shared_pages structure */
-  struct shared_file_entry *shared_file = shared_file_get (file);
-  if (shared_file == NULL)
-    return NULL;
-
-  /* Search for the page within the shared_file's hash table */
-  struct shared_page_entry fake_shared_page_entry;
-  fake_shared_page_entry.upage = upage;
-
-  struct hash_elem *e = hash_find (&shared_file->pages, &fake_shared_page_entry.elem);
-
-  if (e == NULL)
-    return NULL;
-
-  return hash_entry (e, struct shared_page_entry, elem);
-}
-
-static struct shared_file_entry *
-shared_file_insert (struct file *file)
-{
-  struct shared_file_entry *shared_file
-      = malloc (sizeof (struct shared_file_entry));
-  if (shared_file == NULL)
-    return NULL;
-
-  shared_file->file = file;
-  shared_file->ref_count = 0;
-  if (!hash_init (&shared_file->pages, shared_page_hash, shared_page_less,
-                  NULL))
-    {
-      free (shared_file);
-      return NULL;
-    }
-
-  hash_insert (&shared_files, &shared_file->elem);
-  return shared_file;
-}
-
-static struct shared_page_entry *
-shared_page_insert (struct file *file, void *upage, void *frame)
-{
-  struct shared_file_entry *shared_file = shared_file_get (file);
-
-  /* Allocate a new shared_page_entry first for easier error handling. */
-  struct shared_page_entry *shared_page
-    = malloc (sizeof (struct shared_page_entry));
-  if (shared_page == NULL)
-    return NULL;
-
-  /* If shared file doesn't exist in table, also create it. */
-  if (shared_file == NULL)
-    {
-      shared_file = shared_file_insert (file);
-      if (shared_file == NULL)
-        {
-          free (shared_page);
-          return NULL;
-        }
-    }
-
-  shared_page->upage = upage;
-  shared_page->frame = frame;
-  hash_insert (&shared_file->pages, &shared_page->elem);
-  return shared_page;
-}
-
-/* Updates the 'owner' thread's page table entry for virtual address 'upage'
-   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)
-{
-  uint32_t *pte = lookup_page (owner->pagedir, upage, false);
-
-  /* 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);
-}
-
-/* Updates the page table entry for virtual address 'upage' to flag the page as
-   NOT being stored in swap, and clears the excess bits. */
-static void
-page_unset_swap (struct thread *owner, void *upage)
-{
-  uint32_t *pte = lookup_page (owner->pagedir, upage, false);
-
-  *pte &= ~(1 << SWAP_FLAG_BIT);
-  *pte &= ~PTE_ADDR;
-
-  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)
-{
-   uint32_t *pte = lookup_page (owner->pagedir, upage, false);
-   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. */
-size_t
-page_get_swap (struct thread *owner, void *upage)
-{
-   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. */
-   return ((*pte & PTE_ADDR) >> ADDR_START_BIT);
-}
-
-/* If the swap bit is set for a page table entry, drop the swap. */
-bool
-page_cleanup_swap (uint32_t *pte)
-{
-  if ((*pte & (1 << SWAP_FLAG_BIT)) != 0)
-    {
-      size_t swap_slot = ((*pte & PTE_ADDR) >> ADDR_START_BIT);
-      swap_drop (swap_slot);
-      return true;
-    }
-  return false;
-}

src/vm/page.h

@@ -2,13 +2,10 @@
 #define VM_PAGE_H
 
 #include "threads/thread.h"
-#include "threads/synch.h"
 #include "filesys/off_t.h"
 
-struct lock shared_files_lock;
-
 enum page_type {
-  PAGE_EXECUTABLE,
+  PAGE_FILE,
   PAGE_EMPTY
 };
 
@@ -22,42 +19,20 @@ struct page_entry {
   uint32_t read_bytes; /* Number of bytes to read within the page. */
   uint32_t zero_bytes; /* Number of bytes to zero within the page. */
   bool writable;       /* Flag for whether this page is writable or not. */
-  bool shared;         /* Flag for whether this page is shared or not. */
 
   struct hash_elem elem; /* An elem for the hash table. */
 };
 
-struct shared_file_entry {
-  struct file *file;  /* Pointer to the file. */
-  struct hash pages;
-  int ref_count;
-
-  struct hash_elem elem;
-};
-
-struct shared_page_entry {
-  void *upage;
-  void *frame;
-  size_t swap_slot;
-
-  struct hash_elem elem;
-};
-
-bool init_pages (struct thread *t);
+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);
-void page_cleanup (struct hash_elem *e, void *aux UNUSED);
+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);
-bool page_in_swap (struct thread *, void *);
 size_t page_get_swap (struct thread *, void *);
-bool page_cleanup_swap (uint32_t *pte);
-
-void shared_files_init ();
-bool use_shared_file (struct file *file);
-bool unuse_shared_file (struct file *file);
-struct shared_page_entry *shared_page_get (struct file *file, void *upage);
 
 #endif /* vm/frame.h */

src/vm/stackgrowth.c

@@ -1,60 +0,0 @@
-#include <stdio.h>
-#include "stackgrowth.h"
-#include "frame.h"
-#include "threads/palloc.h"
-#include "threads/thread.h"
-#include "threads/vaddr.h"
-#include "userprog/pagedir.h"
-
-#define MAX_STACK_ACCESS_DIST 32
-
-static bool is_stack_fault (const void *addr, const void *esp);
-static bool grow_stack (const void *addr);
-
-/* Determine whether a particular page fault occured due to a stack
-   access below the stack pointer that should induce stack growth, and
-   if so grow the stack by a single page (capped at MAX_STACK_SIZE). */
-bool
-handle_stack_fault (const void *ptr, const void *esp)
-{
-  return is_stack_fault (ptr, esp) && grow_stack (ptr);
-}
-
-/* Determines whether a particular page fault appears to be caused by
-   a stack access that should induce dynamic stack growth. Stack size
-   is capped at MAX_STACK_SIZE. */
-static bool
-is_stack_fault (const void *addr, const void *esp)
-{
-  return ((uint32_t*)addr >= ((uint32_t*)esp - MAX_STACK_ACCESS_DIST) &&
-          ((PHYS_BASE - pg_round_down (addr)) <= MAX_STACK_SIZE));
-}
-
-/* Grows the stack of the process running inside the current thread by a single
-   page given a user virtual address inside of the page wherein the new section
-   of the stack should be allocated. */
-static bool
-grow_stack (const void *addr)
-{
-  struct thread *t = thread_current ();
-  void *last_page = pg_round_down (addr);
-
-  /* This function should only be called when dealing with a faulting stack
-     access that induces stack growth, so the provided address shouldn't be
-     present in a page within the current thread's page directory. */
-  ASSERT (pagedir_get_page (t->pagedir, last_page) == NULL);
-
-  uint8_t *new_page = frame_alloc (PAL_ZERO, last_page, t);
-  if (new_page == NULL)
-    return false;
-
-  if (!pagedir_set_page (t->pagedir, last_page, new_page, true))
-  {
-    frame_owner_remove (new_page, t);
-    frame_free (new_page);
-    return false;
-  }
-
-  return true;
-}
-

src/vm/stackgrowth.h

@@ -1,10 +0,0 @@
-#ifndef VM_GROWSTACK_H
-#define VM_GROWSTACK_H
-
-#include <stdio.h>
-
-#define MAX_STACK_SIZE 8388608 // (8MB)
-
-bool handle_stack_fault (const void *ptr, const void *esp);
-
-#endif /* vm/frame.h */