Maintain a reference to the frame allocated in the SPT

Implement frame-pinning to protect against eviction leading to deadlocks

See merge request lab2425_autumn/pintos_22!58

src/userprog/exception.c

@@ -262,7 +262,12 @@ fetch_page (void *upage, bool write)
 
     bool writeable = pagedir_is_writable (t->pagedir, upage);
     if (pagedir_set_page (t->pagedir, upage, kpage, writeable))
+    {
+      struct page_entry *page = page_get(upage);
+      if (page != NULL)
+        page->frame = kpage;
       return true;
+    }
   }
 
   /* Check if the page is in the supplemental page table. That is, it is a page

src/userprog/syscall.c

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

src/vm/frame.c

@@ -2,7 +2,7 @@
 #include <hash.h>
 #include <list.h>
 #include <string.h>
-
+#include <stdio.h>
 #include "frame.h"
 #include "page.h"
 #include "threads/malloc.h"
@@ -11,141 +11,133 @@
 #include "threads/synch.h"
 #include "devices/swap.h"
 
-/* Hash table that maps every active frame's kernel virtual address
+struct frame_entry
-   to its corresponding 'frame_metadata'.*/
+{
+  void *frame;
+  void *upage;
+  struct thread *owner;
+  bool pinned;
+
+  struct hash_elem hash_elem;
+  struct list_elem list_elem;
+};
+
 struct hash frame_table;
-
+struct lock frame_lock;
-/* 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;
+struct list_elem *next_victim;
 
-/* The next element in lru_list to be considered for eviction (oldest added
+hash_hash_func frame_hash;
-   or referenced page in the circular queue). If this page has has an
+hash_less_func frame_less;
-   '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 '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 hash_elem hash_elem;  /* Tracks the position of the frame metadata
-                                     within 'frame_table', whose key is the 
-                                     kernel virtual address of the frame. */
-     struct list_elem list_elem;  /* Tracks the position of the frame metadata
-                                     in either the 'active' or 'inactive' list,
-                                     so a victim can be chosen for eviction. */
-  };
-
-hash_hash_func frame_metadata_hash;
-hash_less_func frame_metadata_less;
 
+static struct frame_entry *frame_get (void *frame);
+static struct frame_entry *get_victim (void);
 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. */
 void
 frame_init (void)
 {
-  hash_init (&frame_table, frame_metadata_hash, frame_metadata_less, NULL);
+  hash_init (&frame_table, frame_hash, frame_less, NULL);
-
+  lock_init (&frame_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
-   processes is fulled and storing it in swap. If swap is full in
-   the former case, panic the kernel. */
 void *
 frame_alloc (enum palloc_flags flags, void *upage, struct thread *owner)
 {
-  struct frame_metadata *frame_metadata;
+  lock_acquire (&frame_lock);
+  struct frame_entry *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,
-     obtain a victim page to replace with our page, and swap the victim
-     into disk. */
   if (frame == NULL)
-    {
+  {
-      /* 1. Obtain victim. */
+    if (next_victim == NULL)
-      if (next_victim == NULL)
+      PANIC ("Couldn't allocate a single page to main memory!\n");
-        PANIC ("Couldn't allocate a single page to main memory!\n");
 
-      struct frame_metadata *victim = get_victim ();
+    struct frame_entry *victim = get_victim ();
-      ASSERT (victim != NULL); /* get_victim () should never return null. */
+    ASSERT (victim != NULL); /* get_victim () should never return null. */
 
-      /* 2. Swap out victim into disk. */
+    /* 2. Swap out victim into disk. */
-      /* Mark page as 'not present' and flag the page directory as having
+    /* Mark page as 'not present' and flag the page directory as having
-         been modified *before* eviction begins to prevent the owner of the
+       been modified *before* eviction begins to prevent the owner of the
-         victim page from accessing/modifying it mid-eviction. */
+       victim page from accessing/modifying it mid-eviction. */
-      pagedir_clear_page (victim->owner->pagedir, victim->upage);
+    pagedir_clear_page (victim->owner->pagedir, victim->upage);
 
-      // TODO: Lock PTE of victim page for victim process.
+    // TODO: Lock PTE of victim page for victim process.
 
-      size_t swap_slot = swap_out (victim->frame);
+    size_t swap_slot = swap_out (victim->frame);
-      page_set_swap (victim->owner, victim->upage, swap_slot);
+    page_set_swap (victim->owner, victim->upage, swap_slot);
 
-      /* If zero flag is set, zero out the victim page. */
+    /* If zero flag is set, zero out the victim page. */
-      if (flags & PAL_ZERO)
+    if (flags & PAL_ZERO)
-        memset (victim->frame, 0, PGSIZE);
+      memset (victim->frame, 0, PGSIZE);
 
-      /* 3. Indicate that the new frame's metadata will be stored
+    /* 3. Indicate that the new frame's metadata will be stored
-            inside the same structure that stored the victim's metadata.
+          inside the same structure that stored the victim's metadata.
-            As both the new frame and the victim frame share the same kernel
+          As both the new frame and the victim frame share the same kernel
-            virtual address, the hash map need not be updated, and neither
+          virtual address, the hash map need not be updated, and neither
-            the list_elem value as both share the same lru_list position. */
+          the list_elem value as both share the same lru_list position. */
-      frame_metadata = victim;
+    frame_metadata = victim;
-    }
+  }
 
-  /* If sufficient main memory allows the frame to be directly allocated,
+    /* 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. */
+       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_entry));
+    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)
     {
-      /* Must own lru_lock here, as otherwise there is a race condition
+      list_push_back (&lru_list, &frame_metadata->list_elem);
-         with next_victim either being NULL or uninitialized. */
+      next_victim = &frame_metadata->list_elem;
-      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);
     }
+    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_metadata->upage = upage;
   frame_metadata->owner = owner;
-  lock_release (&lru_lock);
+  frame_metadata->pinned = false;
 
-  return frame_metadata->frame;
+  void *frame_addr = frame_metadata->frame;
+  lock_release (&frame_lock);
+  return frame_addr;
+}
+
+void
+frame_pin (void *frame)
+{
+  struct frame_entry *frame_metadata = frame_get (frame);
+  if (frame_metadata == NULL)
+    PANIC ("Attempted to pin a frame at an unallocated kernel address '%p'\n",
+           frame);
+
+  frame_metadata->pinned = true;
+}
+
+void
+frame_unpin (void *frame)
+{
+  struct frame_entry *frame_metadata = frame_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
@@ -153,89 +145,112 @@ frame_alloc (enum palloc_flags flags, void *upage, struct thread *owner)
    memory & metadata struct. Panics if the frame isn't active in memory. */
 void
 frame_free (void *frame)
+{
+  lock_acquire(&frame_lock);
+  struct frame_entry key_metadata;
+  key_metadata.frame = frame;
+
+  struct hash_elem *e =
+    hash_delete (&frame_table, &key_metadata.hash_elem);
+  if (e == NULL)
+    return;
+
+  struct frame_entry *frame_metadata =
+  hash_entry (e, struct frame_entry, hash_elem);
+
+  struct page_entry *page = page_get (frame_metadata->upage);
+  if (page != NULL)
   {
-    struct frame_metadata key_metadata;
+    page->frame = NULL;
-    key_metadata.frame = frame;
-
-    struct hash_elem *e =
-      hash_delete (&frame_table, &key_metadata.hash_elem);
-    if (e == NULL) PANIC ("Attempted to free a frame at kernel address %p, "
-                          "but this address is not allocated!\n", frame);
-
-    struct frame_metadata *frame_metadata =
-      hash_entry (e, struct frame_metadata, hash_elem);
-    
-    lock_acquire (&lru_lock);
-    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);
   }
 
+  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);
+  }
+
+  free (frame_metadata);
+  palloc_free_page (frame);
+
+  lock_release (&frame_lock);
+}
+
 /* 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 *
+static struct frame_entry *
 get_victim (void)
+{
+  struct list_elem *e = next_victim;
+  struct frame_entry *frame_metadata;
+  uint32_t *pd;
+  void *upage;
+  for (;;)
   {
-    struct list_elem *e = next_victim;
+    frame_metadata = list_entry (e, struct frame_entry, list_elem);
-    struct frame_metadata *frame_metadata;
+    pd = frame_metadata->owner->pagedir;
-    uint32_t *pd;
+    upage = frame_metadata->upage;
-    void *upage;
+    e = lru_next (e);
-    for (;;)
-      {
-        frame_metadata = list_entry (e, struct frame_metadata, list_elem);
-        pd = frame_metadata->owner->pagedir;
-        upage = frame_metadata->upage;
-        e = lru_next (e);
 
-        if (!pagedir_is_accessed (pd, upage))
+    /* Skip pinned frames */
-          break;
+    if (frame_metadata->pinned)
+      continue;
 
-        pagedir_set_accessed (pd, upage, false);
+    if (!pagedir_is_accessed (pd, upage))
-      }
+      break;
 
-    next_victim = e;
+    pagedir_set_accessed (pd, upage, false);
-    return frame_metadata;
   }
 
+  next_victim = e;
+  return frame_metadata;
+}
+
 /* Hash function for frame metadata, used for storing entries in the
    frame table. */
 unsigned
-frame_metadata_hash (const struct hash_elem *e, void *aux UNUSED)
+frame_hash (const struct hash_elem *e, void *aux UNUSED)
-  {
+{
-    struct frame_metadata *frame_metadata = 
+  struct frame_entry *entry =
-      hash_entry (e, struct frame_metadata, hash_elem);
+  hash_entry (e, struct frame_entry, hash_elem);
 
-    return hash_bytes (&frame_metadata->frame, sizeof (frame_metadata->frame));
+  return hash_bytes (&entry->frame, sizeof (entry->frame));
-  }
+}
 
 /* 'less_func' comparison function for frame metadata, used for comparing
    the keys of the frame table. Returns true iff the kernel virtual address
    of the first frame is less than that of the second frame. */
 bool
-frame_metadata_less (const struct hash_elem *a_, const struct hash_elem *b_,
+frame_less (const struct hash_elem *a_, const struct hash_elem *b_,
-                     void *aux UNUSED)
+            void *aux UNUSED)
-  {
+{
-    struct frame_metadata *a =
+  struct frame_entry *a =
-      hash_entry (a_, struct frame_metadata, hash_elem);
+  hash_entry (a_, struct frame_entry, hash_elem);
-    struct frame_metadata *b =
+  struct frame_entry *b =
-      hash_entry (b_, struct frame_metadata, hash_elem);
+  hash_entry (b_, struct frame_entry, hash_elem);
 
-    return a->frame < b->frame;
+  return a->frame < b->frame;
-  }
+}
+
+static struct frame_entry *
+frame_get (void *frame)
+{
+  struct frame_entry fake_frame;
+  fake_frame.frame = frame;
+
+  struct hash_elem *e = hash_find (&frame_table, &fake_frame.hash_elem);
+  if (e == NULL) return NULL;
+
+  return hash_entry (e, struct frame_entry, hash_elem);
+}
 
 /* Returns the next recently used element after the one provided, which
    is achieved by iterating through lru_list like a circular queue

src/vm/frame.h

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

src/vm/page.c

@@ -42,9 +42,10 @@ page_insert (struct file *file, off_t ofs, void *upage, uint32_t read_bytes,
   if (page == NULL)
     return NULL;
 
+  page->upage = upage;
+  page->frame = NULL;
   page->file = file;
   page->offset = ofs;
-  page->upage = upage;
   page->read_bytes = read_bytes;
   page->zero_bytes = zero_bytes;
   page->writable = writable;
@@ -102,6 +103,8 @@ 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);
 
+  page->frame = frame;
+
   /* Mark the page as loaded successfully. */
   return true;
 }
@@ -111,7 +114,12 @@ page_load (struct page_entry *page, bool writable)
 void
 page_cleanup (struct hash_elem *e, void *aux UNUSED)
 {
-  free (hash_entry (e, struct page_entry, elem));
+  struct page_entry *page = hash_entry (e, struct page_entry, elem);
+
+  if (page->frame != NULL)
+    frame_free (page->frame);
+
+  free (page);
 }
 
 /* Updates the 'owner' thread's page table entry for virtual address 'upage'

src/vm/page.h

@@ -12,6 +12,7 @@ enum page_type {
 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). */
+  void *frame;         /* Frame Address where the page is loaded. */
 
   /* File Data */
   struct file *file;   /* Pointer to the file for executables. */