feat: set accessed bit to allocated frames in page_load and get_usr_kpage

Implement helper functions for managing the supplemental page table

See merge request lab2425_autumn/pintos_22!55

.gitignore

@@ -4,6 +4,13 @@
 #ignore pdf files (just keep source files)
 *.pdf
 
+#ignore Mac OS generated files
+.DS_Store
+
+#ignore code editor generated directories
+.idea
+.vscode
+
 #ignore junk files from latex output
 *.out
 *.log
@@ -24,3 +31,6 @@
 *.nav
 *.toc
 
+#ignore files from CLion/VSCode IDEs
+.idea
+.vscode

.gitlab-ci.yml

@@ -0,0 +1,40 @@
+stages:
+  - test
+
+.pintos_tests:
+  stage: test
+  image: gitlab.doc.ic.ac.uk:4567/lab2425_autumn/pintos_22/pintos-testing:latest
+  artifacts:
+    when: always
+    paths:
+      - src/$DIR/build/tests/$DIR/
+  before_script:
+    - cd src/utils
+    - make
+    - export PATH=$PWD:$PATH
+    - cd ../..
+  script:
+    - cd src/$DIR
+    - make check | tee build.log
+    - grep -vE "^FAIL $IGNORE\$" build.log | grep -q "FAIL tests/$DIR" && exit 1 || exit 0
+
+test_devices:
+  extends: .pintos_tests
+  variables:
+    DIR: devices
+
+test_threads:
+  extends: .pintos_tests
+  variables:
+    DIR: threads
+
+test_userprog:
+  extends: .pintos_tests
+  variables:
+    DIR: userprog
+
+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)

Dockerfile.devel

@@ -0,0 +1,3 @@
+FROM debian:12-slim
+
+RUN apt update && apt install gcc perl make qemu-system-i386 gdb -y

src/Makefile.build

@@ -62,7 +62,10 @@ userprog_SRC += userprog/gdt.c		# GDT initialization.
 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 += devices/swap.c		# Swap block manager.
+vm_SRC += vm/stackgrowth.c              # Stack growth functions.
 #vm_SRC = vm/file.c			# Some other file.
 
 # Filesystem code.

src/devices/timer.c

@@ -119,9 +119,6 @@ timer_sleep (int64_t ticks)
                        NULL);
   intr_set_level (old_level);
   sema_down (&st.semaphore);
-  old_level = intr_disable ();
-  list_remove (&st.elem);
-  intr_set_level (old_level);
 }
 
 /* Sleeps for approximately MS milliseconds.  Interrupts must be
@@ -204,7 +201,10 @@ timer_interrupt (struct intr_frame *args UNUSED)
     {
       struct asleep_thread *st = list_entry (e, struct asleep_thread, elem);
       if (ticks >= st->end_at)
-        sema_up (&st->semaphore);
+        {
+          list_remove (&st->elem);
+          sema_up (&st->semaphore);
+        }
       else
         break;
     }

src/examples/Makefile

@@ -4,7 +4,7 @@ SRCDIR = ..
 # To add a new test, put its name on the PROGS list
 # and then add a name_SRC line that lists its source files.
 PROGS = cat cmp cp echo halt hex-dump mcat mcp rm \
-	bubsort insult lineup matmult recursor
+	bubsort insult lineup matmult recursor args-ovf
 
 # Should work from task 2 onward.
 cat_SRC = cat.c
@@ -18,6 +18,7 @@ lineup_SRC = lineup.c
 ls_SRC = ls.c
 recursor_SRC = recursor.c
 rm_SRC = rm.c
+args-ovf_SRC = args-ovf.c
 
 # Should work in task 3; also in task 4 if VM is included.
 bubsort_SRC = bubsort.c

src/filesys/file.h

@@ -4,6 +4,9 @@
 #include "filesys/off_t.h"
 #include <stdbool.h>
 
+/* The maximum length of a file name in PintOS. */
+#define FNAME_MAX_LEN 14
+
 struct inode;
 
 /* Opening and closing files. */

src/lib/kernel/list.c

@@ -170,6 +170,9 @@ list_insert (struct list_elem *before, struct list_elem *elem)
 {
   ASSERT (is_interior (before) || is_tail (before));
   ASSERT (elem != NULL);
+  // Sanity checks to prevent (some) loop lists
+  ASSERT (before != elem);
+  ASSERT (before->prev != elem);
 
   elem->prev = before->prev;
   elem->next = before;

src/lib/user/syscall.c

@@ -166,7 +166,7 @@ mkdir (const char *dir)
 }
 
 bool
-readdir (int fd, char name[READDIR_MAX_LEN + 1]) 
+readdir (int fd, char name[FNAME_MAX_LEN + 1]) 
 {
   return syscall2 (SYS_READDIR, fd, name);
 }

src/lib/user/syscall.h

@@ -3,6 +3,7 @@
 
 #include <stdbool.h>
 #include <debug.h>
+#include "../../filesys/file.h"
 
 /* Process identifier. */
 typedef int pid_t;
@@ -12,9 +13,6 @@ typedef int pid_t;
 typedef int mapid_t;
 #define MAP_FAILED ((mapid_t) -1)
 
-/* Maximum characters in a filename written by readdir(). */
-#define READDIR_MAX_LEN 14
-
 /* Typical return values from main() and arguments to exit(). */
 #define EXIT_SUCCESS 0          /* Successful execution. */
 #define EXIT_FAILURE 1          /* Unsuccessful execution. */
@@ -41,7 +39,7 @@ void munmap (mapid_t);
 /* Task 4 only. */
 bool chdir (const char *dir);
 bool mkdir (const char *dir);
-bool readdir (int fd, char name[READDIR_MAX_LEN + 1]);
+bool readdir (int fd, char name[FNAME_MAX_LEN + 1]);
 bool isdir (int fd);
 int inumber (int fd);
 

src/tests/userprog/Make.tests

@@ -9,14 +9,14 @@ sc-bad-arg sc-bad-num sc-boundary sc-boundary-2 halt exit create-normal		\
 create-empty create-null create-bad-ptr create-long create-exists	\
 create-bound open-normal open-missing open-boundary open-empty		\
 open-null open-bad-ptr open-twice close-normal close-twice close-stdin	\
-close-stdout close-bad-fd read-normal read-bad-ptr read-boundary	\
+close-stdout close-bad-fd read-normal read-bad-ptr read-bad-buf read-boundary	\
-read-zero read-stdout read-bad-fd write-normal write-bad-ptr		\
+read-zero read-stdout read-bad-fd write-normal write-bad-ptr write-bad-buf	\
 write-boundary write-zero write-stdin write-bad-fd exec-once exec-arg	\
 exec-large-arg exec-multiple exec-missing exec-over-arg exec-over-args \
 exec-bad-ptr wait-simple wait-twice wait-killed wait-load-kill \
 wait-bad-pid wait-bad-child multi-recurse multi-child-fd rox-simple	\
 rox-child rox-multichild bad-read bad-write bad-read2 bad-write2        \
-bad-jump bad-jump2 bad-maths)
+bad-jump bad-jump2 bad-maths overflow-stack)
 
 tests/userprog_PROGS = $(tests/userprog_TESTS) $(addprefix \
 tests/userprog/,child-simple child-args child-bad child-close child-rox exec-exit)
@@ -36,6 +36,7 @@ tests/userprog/bad-read2_SRC = tests/userprog/bad-read2.c tests/main.c
 tests/userprog/bad-write2_SRC = tests/userprog/bad-write2.c tests/main.c
 tests/userprog/bad-jump2_SRC = tests/userprog/bad-jump2.c tests/main.c
 tests/userprog/bad-maths_SRC = tests/userprog/bad-maths.c tests/main.c
+tests/userprog/overflow-stack_SRC = tests/userprog/overflow-stack.c tests/main.c
 tests/userprog/sc-boundary_SRC = tests/userprog/sc-boundary.c	\
 tests/userprog/boundary.c tests/main.c
 tests/userprog/sc-boundary-2_SRC = tests/userprog/sc-boundary-2.c	\
@@ -66,6 +67,7 @@ tests/userprog/close-stdout_SRC = tests/userprog/close-stdout.c tests/main.c
 tests/userprog/close-bad-fd_SRC = tests/userprog/close-bad-fd.c tests/main.c
 tests/userprog/read-normal_SRC = tests/userprog/read-normal.c tests/main.c
 tests/userprog/read-bad-ptr_SRC = tests/userprog/read-bad-ptr.c tests/main.c
+tests/userprog/read-bad-buf_SRC = tests/userprog/read-bad-buf.c tests/main.c
 tests/userprog/read-boundary_SRC = tests/userprog/read-boundary.c	\
 tests/userprog/boundary.c tests/main.c
 tests/userprog/read-zero_SRC = tests/userprog/read-zero.c tests/main.c
@@ -73,6 +75,7 @@ tests/userprog/read-stdout_SRC = tests/userprog/read-stdout.c tests/main.c
 tests/userprog/read-bad-fd_SRC = tests/userprog/read-bad-fd.c tests/main.c
 tests/userprog/write-normal_SRC = tests/userprog/write-normal.c tests/main.c
 tests/userprog/write-bad-ptr_SRC = tests/userprog/write-bad-ptr.c tests/main.c
+tests/userprog/write-bad-buf_SRC = tests/userprog/write-bad-buf.c tests/main.c
 tests/userprog/write-boundary_SRC = tests/userprog/write-boundary.c	\
 tests/userprog/boundary.c tests/main.c
 tests/userprog/write-zero_SRC = tests/userprog/write-zero.c tests/main.c
@@ -122,10 +125,12 @@ tests/userprog/close-normal_PUTFILES += tests/userprog/sample.txt
 tests/userprog/close-twice_PUTFILES += tests/userprog/sample.txt
 tests/userprog/read-normal_PUTFILES += tests/userprog/sample.txt
 tests/userprog/read-bad-ptr_PUTFILES += tests/userprog/sample.txt
+tests/userprog/read-bad-buf_PUTFILES += tests/userprog/sample.txt
 tests/userprog/read-boundary_PUTFILES += tests/userprog/sample.txt
 tests/userprog/read-zero_PUTFILES += tests/userprog/sample.txt
 tests/userprog/write-normal_PUTFILES += tests/userprog/sample.txt
 tests/userprog/write-bad-ptr_PUTFILES += tests/userprog/sample.txt
+tests/userprog/write-bad-buf_PUTFILES += tests/userprog/sample.txt
 tests/userprog/write-boundary_PUTFILES += tests/userprog/sample.txt
 tests/userprog/write-zero_PUTFILES += tests/userprog/sample.txt
 tests/userprog/multi-child-fd_PUTFILES += tests/userprog/sample.txt

src/tests/userprog/Rubric.robustnessCR

@@ -1,5 +1,9 @@
-Full robustness of argument passing code:
+Full robustness of argument passing and syscall handling code:
-- Test user stack overflow robustness of "exec" system calls.
+- Test user stack overflow robustness of "exec" system calls and user code.
 5	exec-over-arg
 5	exec-over-args
+5	overflow-stack
 
+- Test syscall user provided buffer validity checks.
+5	read-bad-buf
+5	write-bad-buf

src/tests/userprog/exec-bad-ptr.ck

@@ -2,11 +2,7 @@
 use strict;
 use warnings;
 use tests::tests;
-check_expected ([<<'EOF', <<'EOF']);
+check_expected ([<<'EOF']);
-(exec-bad-ptr) begin
-(exec-bad-ptr) end
-exec-bad-ptr: exit(0)
-EOF
 (exec-bad-ptr) begin
 exec-bad-ptr: exit(-1)
 EOF

src/tests/userprog/open-bad-ptr.ck

@@ -2,11 +2,7 @@
 use strict;
 use warnings;
 use tests::tests;
-check_expected ([<<'EOF', <<'EOF']);
+check_expected ([<<'EOF']);
-(open-bad-ptr) begin
-(open-bad-ptr) end
-open-bad-ptr: exit(0)
-EOF
 (open-bad-ptr) begin
 open-bad-ptr: exit(-1)
 EOF

src/tests/userprog/overflow-stack.c

@@ -0,0 +1,17 @@
+/* Attempt to overflow the user stack by allocating a 4kB buffer and writing into it.
+   The process must be terminated with -1 exit code until stack growth has been implemented in Task 3
+*/
+
+#include <string.h>
+#include <syscall.h>
+#include "tests/lib.h"
+#include "tests/main.h"
+
+void
+test_main (void)
+{
+  char stack_obj[4096];
+  memset (stack_obj, 'a', sizeof stack_obj);
+  memset (stack_obj+10, '\0', 1);
+  msg ("buffer: %s", stack_obj);
+}

src/tests/userprog/overflow-stack.ck

@@ -0,0 +1,14 @@
+# -*- perl -*-
+use strict;
+use warnings;
+use tests::tests;
+check_expected (IGNORE_USER_FAULTS => 1, [<<'EOF',<<'EOF']);
+(overflow-stack) begin
+overflow-stack: exit(-1)
+EOF
+(overflow-stack) begin
+(overflow-stack) buffer: aaaaaaaaaa
+(overflow-stack) end
+overflow-stack: exit(0)
+EOF
+pass;

src/tests/userprog/read-bad-buf.c

@@ -0,0 +1,17 @@
+/* Passes a buffer to the read system call that starts in valid memory, but runs into kernel space.
+   The process must be terminated with -1 exit code.
+*/
+
+#include <syscall.h>
+#include "tests/lib.h"
+#include "tests/main.h"
+
+void
+test_main (void)
+{
+  int handle;
+  CHECK ((handle = open ("sample.txt")) > 1, "open \"sample.txt\"");
+
+  read (handle, (char *) 0xbfffffe0, 100);
+  fail ("should not have survived read()");
+}

src/tests/userprog/read-bad-buf.ck

@@ -0,0 +1,10 @@
+# -*- perl -*-
+use strict;
+use warnings;
+use tests::tests;
+check_expected (IGNORE_KERNEL_FAULTS => 1, [<<'EOF']);
+(read-bad-buf) begin
+(read-bad-buf) open "sample.txt"
+read-bad-buf: exit(-1)
+EOF
+pass;

src/tests/userprog/read-bad-ptr.ck

@@ -2,12 +2,7 @@
 use strict;
 use warnings;
 use tests::tests;
-check_expected ([<<'EOF', <<'EOF']);
+check_expected ([<<'EOF']);
-(read-bad-ptr) begin
-(read-bad-ptr) open "sample.txt"
-(read-bad-ptr) end
-read-bad-ptr: exit(0)
-EOF
 (read-bad-ptr) begin
 (read-bad-ptr) open "sample.txt"
 read-bad-ptr: exit(-1)

src/tests/userprog/write-bad-buf.c

@@ -0,0 +1,17 @@
+/* Passes a buffer to the write system call that starts in valid memory, but runs into kernel space.
+   The process must be terminated with -1 exit code.
+*/
+
+#include <syscall.h>
+#include "tests/lib.h"
+#include "tests/main.h"
+
+void
+test_main (void)
+{
+  int handle;
+  CHECK ((handle = open ("sample.txt")) > 1, "open \"sample.txt\"");
+
+  write (handle, (char *) 0xbffffff0, 32);
+  fail ("should have exited with -1");
+}

src/tests/userprog/write-bad-buf.ck

@@ -0,0 +1,10 @@
+# -*- perl -*-
+use strict;
+use warnings;
+use tests::tests;
+check_expected (IGNORE_KERNEL_FAULTS => 1, [<<'EOF']);
+(write-bad-buf) begin
+(write-bad-buf) open "sample.txt"
+write-bad-buf: exit(-1)
+EOF
+pass;

src/tests/userprog/write-bad-ptr.ck

@@ -2,12 +2,7 @@
 use strict;
 use warnings;
 use tests::tests;
-check_expected ([<<'EOF', <<'EOF']);
+check_expected ([<<'EOF']);
-(write-bad-ptr) begin
-(write-bad-ptr) open "sample.txt"
-(write-bad-ptr) end
-write-bad-ptr: exit(0)
-EOF
 (write-bad-ptr) begin
 (write-bad-ptr) open "sample.txt"
 write-bad-ptr: exit(-1)

src/threads/fixed-point.h

@@ -0,0 +1,100 @@
+#include <stdint.h>
+#ifndef FIXED_POINT_H
+#define FIXED_POINT_H
+
+typedef struct
+  {
+    int32_t raw;
+  } fp32_t;
+
+/* Fixed Point Arithmetic bit count constants */
+#define NUM_FRAC_BITS 14
+#define NUM_INT_BITS (31 - NUM_FRAC_BITS)
+#define CONVERSION_FACTOR (1 << NUM_FRAC_BITS) /* f = 2^q, (2^14) */
+
+/* Fixed Point Arithmetic conversion operations */
+/* Converts an integer n to a fixed point number */
+inline fp32_t
+fp_from_int (int32_t n)
+{
+  return (fp32_t){ n * CONVERSION_FACTOR };
+}
+
+/* Handles conversion of fixed point to integer,
+   with truncation */
+inline int32_t
+fp_floor (fp32_t x)
+{
+  return x.raw / CONVERSION_FACTOR;
+}
+
+/* Handles conversion of fixed point to integer,
+   with rounding */
+inline int32_t
+fp_round (fp32_t x)
+{
+  if (x.raw >= 0)
+    return (x.raw + CONVERSION_FACTOR / 2) / CONVERSION_FACTOR;
+  else
+    return (x.raw - CONVERSION_FACTOR / 2) / CONVERSION_FACTOR;
+}
+
+/* Add two fixed points */
+inline fp32_t
+fp_add (fp32_t x, fp32_t y)
+{
+  return (fp32_t){ x.raw + y.raw };
+}
+
+/* Subtract two fixed points */
+inline fp32_t
+fp_sub (fp32_t x, fp32_t y)
+{
+  return (fp32_t){ x.raw - y.raw };
+}
+
+
+
+/* Multiple two fixed points */
+inline fp32_t
+fp_mul (fp32_t x, fp32_t y)
+{
+  return (fp32_t){ ((int64_t)x.raw) * y.raw / CONVERSION_FACTOR };
+}
+
+/* Divide two fixed points */
+inline fp32_t
+fp_div (fp32_t x, fp32_t y)
+{
+  return (fp32_t){ ((int64_t)x.raw) * CONVERSION_FACTOR / y.raw };
+}
+
+/* Multiply fixed point and integer */
+inline fp32_t
+fp_mul_int (fp32_t x, int32_t n)
+{
+  return (fp32_t){ x.raw * n };
+}
+
+/* Divide fixed point by integer */
+inline fp32_t
+fp_div_int (fp32_t x, int32_t n)
+{
+  return (fp32_t){ x.raw / n };
+}
+
+/* Add fixed point to integer */
+inline fp32_t
+fp_add_int (fp32_t x, int32_t n)
+{
+  return (fp32_t){ x.raw + n * CONVERSION_FACTOR };
+}
+
+/* Subtract integer from fixed point */
+inline fp32_t
+fp_sub_int (fp32_t x, int32_t n)
+{
+  return (fp32_t){ x.raw - n * CONVERSION_FACTOR };
+}
+
+#endif //FIXED_POINT_H

src/threads/init.c

@@ -32,6 +32,7 @@
 #include "tests/threads/tests.h"
 #endif
 #ifdef VM
+#include "vm/frame.h"
 #include "devices/swap.h"
 #endif
 #ifdef FILESYS
@@ -101,6 +102,9 @@ main (void)
   palloc_init (user_page_limit);
   malloc_init ();
   paging_init ();
+#ifdef VM
+  frame_init ();
+#endif
 
   /* Segmentation. */
 #ifdef USERPROG

src/threads/synch.c

@@ -32,6 +32,10 @@
 #include "threads/interrupt.h"
 #include "threads/thread.h"
 
+static bool
+priority_less (const struct list_elem *a_, const struct list_elem *b_,
+               void *aux UNUSED);
+
 /* Initializes semaphore SEMA to VALUE.  A semaphore is a
    nonnegative integer along with two atomic operators for
    manipulating it:
@@ -109,15 +113,33 @@ void
 sema_up (struct semaphore *sema)
 {
   enum intr_level old_level;
+  bool thread_unblocked = false; /* Flag to track if any thread was woken up. */
 
   ASSERT (sema != NULL);
 
   old_level = intr_disable ();
   if (!list_empty (&sema->waiters))
-    thread_unblock (list_entry (list_pop_front (&sema->waiters),
+    {
-                                struct thread, elem));
+      /* Enforces wake-up of the highest priority thread waiting for the
+         semaphore. */
+      struct list_elem *e = list_max (&sema->waiters, priority_less, NULL);
+      list_remove (e);
+      thread_unblock (list_entry (e, struct thread, elem));
+      thread_unblocked = true;
+    }
   sema->value++;
   intr_set_level (old_level);
+
+  /* Yields the CPU in case the thread that has been woken up has a higher
+     priority that the current running thread, including the case when called
+     within an interrupt handler. */
+  if (thread_unblocked)
+    {
+      if (intr_context ())
+        intr_yield_on_return ();
+      else
+        thread_yield ();
+    }
 }
 
 static void sema_test_helper (void *sema_);
@@ -181,6 +203,48 @@ lock_init (struct lock *lock)
   sema_init (&lock->semaphore, 1);
 }
 
+/* Current thread donates its priority to donee, iteratively
+   propagating the donation in the case of chains in the wait-for graph.
+   Also keeps track of the donation by updating the donors list. Expects
+   interrupts to be disabled. */
+static void
+donate_priority (struct thread *donee) {
+  ASSERT (intr_get_level () == INTR_OFF);
+
+  struct thread *donor = thread_current ();
+  list_remove (&donor->donor_elem);
+  list_push_back (&donee->donors_list, &donor->donor_elem);
+  
+  while (donee != NULL)
+    {
+      /* Stop propagation of donation once a donee is reached that has
+         a higher effective priority (as its donees can't have less
+         priority than that being donated). */
+      if (donor->priority <= donee->priority)
+          break;
+
+      /* Also stop propagation of donation once a donee is reached with
+         no donees of its own (sink node in WFG). */
+      if (donee->waiting_lock == NULL)
+        {
+          /* Only the sink node of the WFG isn't waiting for a lock and
+             could be on the ready list. Thus, as its priority changed,
+             it must be reinserted into the list. */
+          enum intr_level old_level = intr_disable ();
+          donee->priority = donor->priority;
+          ready_list_reinsert (donee);
+          intr_set_level (old_level);
+          
+          donee = NULL;
+        }
+      else
+        {
+          donee->priority = donor->priority;
+          donee = donee->waiting_lock->holder;
+        }
+    }
+}
+
 /* Acquires LOCK, sleeping until it becomes available if
    necessary.  The lock must not already be held by the current
    thread.
@@ -196,8 +260,20 @@ lock_acquire (struct lock *lock)
   ASSERT (!intr_context ());
   ASSERT (!lock_held_by_current_thread (lock));
 
+  struct thread *t = thread_current ();
+  ASSERT (t->waiting_lock == NULL);
+
+  enum intr_level old_level = intr_disable ();
+  if (lock->holder != NULL)
+    {
+      t->waiting_lock = lock;
+      donate_priority (lock->holder);
+    }
+  intr_set_level (old_level);
+
   sema_down (&lock->semaphore);
   lock->holder = thread_current ();
+  t->waiting_lock = NULL;
 }
 
 /* Tries to acquires LOCK and returns true if successful or false
@@ -231,6 +307,51 @@ lock_release (struct lock *lock)
   ASSERT (lock != NULL);
   ASSERT (lock_held_by_current_thread (lock));
 
+  struct thread *current_thread = thread_current ();
+  struct thread *max_donor = NULL;
+
+  struct list orphan_list;
+  list_init (&orphan_list);
+
+  enum intr_level old_level = intr_disable ();
+  /* Loop through current thread's donors, removing the ones waiting for the
+     lock being released and keeping track of them (within orphan_list).
+     Also identifies the highest priority donor thread among them. */
+  struct list_elem *tail = list_tail (&current_thread->donors_list);
+  struct list_elem *e = list_begin (&current_thread->donors_list);
+  while (e != tail)
+    {
+      struct thread *donor = list_entry (e, struct thread, donor_elem);
+      struct list_elem *next = list_next (e);
+
+      /* Excludes donors that aren't waiting for the lock being released,
+         and tracks the rest. */
+      if (donor->waiting_lock == lock)
+        {
+          list_remove (e);
+          list_push_back (&orphan_list, e);
+
+          /* Identify highest priority donor. */
+          if (max_donor == NULL || donor->priority > max_donor->priority)
+            max_donor = donor;
+        }
+
+      e = next;
+    }
+
+  /* If there exists a maximum donor thread waiting for this lock to be
+     released, transfer the remaining orphaned donors to its donor list. */
+  if (max_donor != NULL)
+    {
+      while (!list_empty (&orphan_list))
+        list_push_back (&max_donor->donors_list, list_pop_front (&orphan_list));
+    }
+
+  intr_set_level (old_level);
+  /* Removal of donors to this thread may change its effective priority,
+     so recalculate. */
+  thread_recalculate_priority ();
+
   lock->holder = NULL;
   sema_up (&lock->semaphore);
 }
@@ -253,6 +374,49 @@ struct semaphore_elem
     struct semaphore semaphore;         /* This semaphore. */
   };
 
+/* Function that compares the two threads associated with the provided
+   pointers to their 'elem' member. Returns true if the thread associated
+   with a_ has a lower priority than that of b_. */
+static bool
+priority_less (const struct list_elem *a_, const struct list_elem *b_,
+               void *aux UNUSED)
+{
+  struct thread *a = list_entry (a_, struct thread, elem);
+  struct thread *b = list_entry (b_, struct thread, elem);
+
+  return a->priority < b->priority;
+}
+
+/* Function that compares the two *semaphores* associated with the provided
+   list_elem structures. [i.e., takes list_elem of semaphore_elem, and]
+   Returns true if the thread associated with the semaphore associated with a_
+   has a higher priority than that of b_.
+
+    If aux is provided, then it is a pointer to an integer representing the
+    priority of the first semaphore. This is useful when the thread has not been
+    sema'd down yet. */
+static bool
+sema_priority_more(const struct list_elem *a, const struct list_elem *b,
+                   void *inserting_telem)
+{
+  struct list_elem *te_a, *te_b;
+  
+  te_b = list_front (
+    &list_entry (b, struct semaphore_elem, elem)->semaphore.waiters);
+
+  if (inserting_telem == NULL)
+    {
+      te_a = list_front (
+        &list_entry (a, struct semaphore_elem, elem)->semaphore.waiters);
+    }
+  else
+    {
+      te_a = inserting_telem;
+    }
+
+  return priority_more (te_a, te_b, NULL);
+}
+
 /* Initializes condition variable COND.  A condition variable
    allows one piece of code to signal a condition and cooperating
    code to receive the signal and act upon it. */
@@ -317,8 +481,13 @@ cond_signal (struct condition *cond, struct lock *lock UNUSED)
   ASSERT (lock_held_by_current_thread (lock));
 
   if (!list_empty (&cond->waiters))
-    sema_up (&list_entry (list_pop_front (&cond->waiters),
+    {
-                          struct semaphore_elem, elem)->semaphore);
+      /* Enforce wake-up of highest priority thread within the singleton 
+         semaphores waiting for condvar. */
+      struct list_elem *e = list_min (&cond->waiters, sema_priority_more, NULL);
+      list_remove (e);
+      sema_up (&list_entry (e, struct semaphore_elem, elem)->semaphore);
+    }
 }
 
 /* Wakes up all threads, if any, waiting on COND (protected by

src/threads/thread.c

@@ -1,18 +1,24 @@
 #include "threads/thread.h"
 #include <debug.h>
+#include <hash.h>
 #include <stddef.h>
 #include <random.h>
 #include <stdio.h>
 #include <string.h>
+#include "devices/timer.h"
+#include "threads/fixed-point.h"
 #include "threads/flags.h"
 #include "threads/interrupt.h"
 #include "threads/intr-stubs.h"
+#include "threads/malloc.h"
 #include "threads/palloc.h"
 #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"
 #endif
 
 /* Random value for struct thread's `magic' member.
@@ -49,9 +55,11 @@ struct kernel_thread_frame
 static long long idle_ticks;    /* # of timer ticks spent idle. */
 static long long kernel_ticks;  /* # of timer ticks in kernel threads. */
 static long long user_ticks;    /* # of timer ticks in user programs. */
+static fp32_t load_avg = { 0 }; /* System load average. */
 
 /* Scheduling. */
 #define TIME_SLICE 4            /* # of timer ticks to give each thread. */
+#define PRI_UPDATE_FREQ 4       /* # of timer ticks to update priorities. */
 static unsigned thread_ticks;   /* # of timer ticks since last yield. */
 
 /* If false (default), use round-robin scheduler.
@@ -64,12 +72,23 @@ static void kernel_thread (thread_func *, void *aux);
 static void idle (void *aux UNUSED);
 static struct thread *running_thread (void);
 static struct thread *next_thread_to_run (void);
-static void init_thread (struct thread *, const char *name, int priority);
+static bool init_process_result (struct thread *t);
+static void init_thread (struct thread *, const char *name, int nice,
+                         int priority, fp32_t recent_cpu);
 static bool is_thread (struct thread *) UNUSED;
 static void *alloc_frame (struct thread *, size_t size);
+static int calculate_bsd_priority (fp32_t recent_cpu, int nice);
+static void update_recent_cpu (struct thread *t, void *aux UNUSED);
+static void recalculate_priority (struct thread *t);
 static void schedule (void);
 void thread_schedule_tail (struct thread *prev);
 static tid_t allocate_tid (void);
+static bool donor_priority_less (const struct list_elem *a_,
+                                 const struct list_elem *b_, void *aux UNUSED);
+static unsigned process_result_hash (const struct hash_elem *e,
+                                     void *aux UNUSED);
+static bool process_result_less (const struct hash_elem *a,
+                                 const struct hash_elem *b, void *aux UNUSED);
 
 /* Initializes the threading system by transforming the code
    that's currently running into a thread.  This can't work in
@@ -95,9 +114,12 @@ thread_init (void)
 
   /* Set up a thread structure for the running thread. */
   initial_thread = running_thread ();
-  init_thread (initial_thread, "main", PRI_DEFAULT);
+  fp32_t initial_thread_recent_cpu = { 0 };
+  init_thread (initial_thread, "main", NICE_DEFAULT, PRI_DEFAULT,
+               initial_thread_recent_cpu);
   initial_thread->status = THREAD_RUNNING;
   initial_thread->tid = allocate_tid ();
+  initial_thread->result = NULL; /* Main thread cannot be waited for. */
 }
 
 /* Starts preemptive thread scheduling by enabling interrupts.
@@ -105,6 +127,13 @@ thread_init (void)
 void
 thread_start (void) 
 {
+  /* Malloc has been initalised, we can allocate the child results table
+     for the main thread. */
+  struct thread *t = thread_current ();
+  if (!hash_init (&t->child_results, process_result_hash, process_result_less,
+                  t))
+    PANIC ("Failed to initialise child results table for main thread.");
+
   /* Create the idle thread. */
   struct semaphore idle_started;
   sema_init (&idle_started, 0);
@@ -145,6 +174,35 @@ thread_tick (void)
   else
     kernel_ticks++;
 
+  /* Update system load_avg and all threads recent_cpu every second. */
+  int64_t ticks = timer_ticks ();
+  if (thread_mlfqs)
+    {
+      if (t != idle_thread)
+          t->recent_cpu = fp_add_int (t->recent_cpu, 1);
+
+      if (ticks % TIMER_FREQ == 0)
+        {
+          size_t ready = threads_ready ();
+          if (t != idle_thread)
+            ready++;
+          fp32_t old_coeff = fp_div_int (fp_mul_int (load_avg, 59), 60);
+          fp32_t new_coeff = fp_div_int (fp_from_int (ready), 60);
+          load_avg = fp_add (old_coeff, new_coeff);
+
+          thread_foreach (update_recent_cpu, NULL);
+          /* Priorities have been updated, need to re-sort. */
+          list_sort (&ready_list, priority_more, NULL);
+        }
+
+      /* Recent cpu was updated, update priority. */
+      if (t != idle_thread && ticks % PRI_UPDATE_FREQ == 0)
+        {
+          t->base_priority = calculate_bsd_priority (t->recent_cpu, t->nice);
+          recalculate_priority (t);
+        }
+    }
+
   /* Enforce preemption. */
   if (++thread_ticks >= TIME_SLICE)
     intr_yield_on_return ();
@@ -192,8 +250,33 @@ thread_create (const char *name, int priority,
     return TID_ERROR;
 
   /* Initialize thread. */
-  init_thread (t, name, priority);
+  struct thread *parent_thread = thread_current ();
+  init_thread (t, name, parent_thread->nice, priority, parent_thread->recent_cpu);
   tid = t->tid = allocate_tid ();
+  if (!init_process_result (t))
+    {
+      palloc_free_page (t);
+      return TID_ERROR;
+    }
+
+#ifdef USERPROG
+  /* Initialize the thread's file descriptor table. */
+  t->fd_counter = MINIMUM_USER_FD;
+
+  bool success = hash_init (&t->open_files, fd_hash, fd_less, NULL);
+  success = success && hash_init (&t->child_results, process_result_hash,
+                                  process_result_less, t);
+#ifdef VM
+  success = success && hash_init (&t->pages, page_hash, page_less, NULL);
+#endif
+
+  if (!success)
+    {
+      palloc_free_page (t);
+      free (t->result);
+      return TID_ERROR;
+    }
+#endif
 
   /* Prepare thread for first run by initializing its stack.
      Do this atomically so intermediate values for the 'stack' 
@@ -217,9 +300,16 @@ thread_create (const char *name, int priority,
 
   intr_set_level (old_level);
 
+  hash_insert (&parent_thread->child_results, &t->result->elem);
+
   /* Add to run queue. */
   thread_unblock (t);
 
+  /* Yield if the newly created thread has higher priority than the current
+     thread. */
+  if (t->priority > thread_get_priority ())
+    thread_yield ();
+
   return tid;
 }
 
@@ -256,7 +346,10 @@ thread_unblock (struct thread *t)
 
   old_level = intr_disable ();
   ASSERT (t->status == THREAD_BLOCKED);
-  list_push_back (&ready_list, &t->elem);
+
+  /* Insert the thread back into the ready list in priority order. */
+  list_insert_ordered (&ready_list, &t->elem, priority_more, NULL);
+
   t->status = THREAD_READY;
   intr_set_level (old_level);
 }
@@ -309,7 +402,9 @@ thread_exit (void)
      and schedule another process.  That process will destroy us
      when it calls thread_schedule_tail(). */
   intr_disable ();
-  list_remove (&thread_current()->allelem);
+  struct thread *t = thread_current ();
+  list_remove (&t->allelem);
+  list_remove (&t->donor_elem);
   thread_current ()->status = THREAD_DYING;
   schedule ();
   NOT_REACHED ();
@@ -326,8 +421,13 @@ thread_yield (void)
   ASSERT (!intr_context ());
 
   old_level = intr_disable ();
+
   if (cur != idle_thread)
-    list_push_back (&ready_list, &cur->elem);
+    {
+      /* Insert the thread back into the ready list in priority order. */
+      list_insert_ordered (&ready_list, &cur->elem, priority_more, NULL);
+    }
+
   cur->status = THREAD_READY;
   schedule ();
   intr_set_level (old_level);
@@ -350,49 +450,161 @@ thread_foreach (thread_action_func *func, void *aux)
     }
 }
 
-/* Sets the current thread's priority to NEW_PRIORITY. */
+/* Function that compares the two threads associated with the provided
-void
+   pointers to their 'elem' member. Returns true if the thread associated
-thread_set_priority (int new_priority) 
+   with a_ has a higher priority than that of b_. */
+bool
+priority_more (const struct list_elem *a_, const struct list_elem *b_,
+               void *aux UNUSED)
 {
-  thread_current ()->priority = new_priority;
+  struct thread *a = list_entry (a_, struct thread, elem);
+  struct thread *b = list_entry (b_, struct thread, elem);
+
+  return a->priority > b->priority;
+
 }
 
-/* Returns the current thread's priority. */
+/* Function that compares the two threads associated with the provided
+   pointers to their 'donor_elem' member. Returns true if the thread associated
+   with a_ has a lower priority than that of b_. */
+static bool
+donor_priority_less (const struct list_elem *a_, const struct list_elem *b_,
+               void *aux UNUSED)
+{
+  struct thread *a = list_entry (a_, struct thread, donor_elem);
+  struct thread *b = list_entry (b_, struct thread, donor_elem);
+
+  return a->priority < b->priority;
+}
+
+/* Sets the current thread's base priority to new_base_priority.
+   Updates the current thread's effective priority if necessary. */
+void
+thread_set_priority (int new_base_priority)
+{
+
+  if (thread_mlfqs)
+    return;
+
+  ASSERT (new_base_priority >= PRI_MIN);
+  ASSERT (new_base_priority <= PRI_MAX);
+
+  struct thread *t = thread_current ();
+
+  /* If the base priority is unchanged, do nothing. */
+  if (new_base_priority == t->base_priority)
+    return;
+
+  t->base_priority = new_base_priority;
+  recalculate_priority (t);
+
+  thread_yield ();
+}
+
+/* Returns the current thread's effective priority. */
 int
 thread_get_priority (void) 
 {
   return thread_current ()->priority;
 }
 
+
+/* Updates recent_cpu for a thread. */
+static void
+update_recent_cpu (struct thread *t, void *aux UNUSED)
+{
+  fp32_t curr_recent_cpu = t->recent_cpu;
+  fp32_t dbl_load_avg = fp_mul_int (load_avg, 2);
+  fp32_t recent_cpu_coeff
+      = fp_div (dbl_load_avg, fp_add_int (dbl_load_avg, 1));
+  t->recent_cpu
+      = fp_add_int (fp_mul (recent_cpu_coeff, curr_recent_cpu), t->nice);
+  // recent_cpu was updated, update priority.
+  t->base_priority = calculate_bsd_priority (t->recent_cpu, t->nice);
+  recalculate_priority (t);
+}
+
+/* Recalculates the effective priority of the current thread. */
+void
+thread_recalculate_priority (void)
+{
+  struct thread *t = thread_current ();
+  recalculate_priority (t);
+}
+
+static void
+recalculate_priority (struct thread *t)
+{
+  enum intr_level old_level = intr_disable ();
+  t->priority = t->base_priority;
+
+  /* If there are no donors to the current thread, then the effective
+     priority is just the base priority. */
+  if (!list_empty (&t->donors_list))
+    {
+      int max_donated_priority =
+        list_entry (list_max (&t->donors_list, donor_priority_less, NULL),
+                    struct thread, donor_elem)->priority;
+
+      /* The effective priority is the max donated priority if this is
+         higher than the base priority. */
+      if (max_donated_priority > t->priority)
+        t->priority = max_donated_priority;
+    }
+  intr_set_level (old_level);
+}
+
 /* Sets the current thread's nice value to NICE. */
 void
-thread_set_nice (int nice UNUSED) 
+thread_set_nice (int nice)
 {
-  /* Not yet implemented. */
+  ASSERT (NICE_MIN <= nice && nice <= NICE_MAX);
+
+  struct thread *t = thread_current ();
+  t->nice = nice;
+  t->base_priority = calculate_bsd_priority (t->recent_cpu, t->nice);
+  recalculate_priority (t);
+  struct thread *next_t
+      = list_entry (list_begin (&ready_list), struct thread, elem);
+  if (t->priority < next_t->priority)
+    thread_yield ();
 }
 
 /* Returns the current thread's nice value. */
 int
 thread_get_nice (void) 
 {
-  /* Not yet implemented. */
+  return thread_current ()->nice;
-  return 0;
 }
 
 /* Returns 100 times the system load average. */
 int
 thread_get_load_avg (void) 
 {
-  /* Not yet implemented. */
+  return fp_round (fp_mul_int (load_avg, 100));
-  return 0;
 }
 
 /* Returns 100 times the current thread's recent_cpu value. */
 int
 thread_get_recent_cpu (void) 
 {
-  /* Not yet implemented. */
+  return fp_round (fp_mul_int (thread_current ()->recent_cpu, 100));
-  return 0;
+}
+
+/* Reinsert thread t into the ready list at its correct position
+   in descending order of priority. Used when this thread's priority
+   may have changed. Must be called with interrupts disabled. */
+void
+ready_list_reinsert (struct thread *t)
+{
+  ASSERT (intr_get_level () == INTR_OFF);
+
+  /* If the thread isn't ready to run, do nothing. */
+  if (t->status != THREAD_READY)
+    return;
+
+  list_remove (&t->elem);
+  list_insert_ordered (&ready_list, &t->elem, priority_more, NULL);
 }
 
 /* Idle thread.  Executes when no other thread is ready to run.
@@ -465,10 +677,26 @@ is_thread (struct thread *t)
   return t != NULL && t->magic == THREAD_MAGIC;
 }
 
+/* Allocate and initialise a process result for given thread. */
+static bool
+init_process_result (struct thread *t)
+{
+  struct process_result *result = malloc (sizeof (struct process_result));
+  if (result == NULL)
+    return false;
+  result->tid = t->tid;
+  result->exit_status = -1;
+  lock_init (&result->lock);
+  sema_init (&result->sema, 0);
+  t->result = result;
+  return true;
+}
+
 /* Does basic initialization of T as a blocked thread named
    NAME. */
 static void
-init_thread (struct thread *t, const char *name, int priority)
+init_thread (struct thread *t, const char *name, int nice, int priority,
+             fp32_t recent_cpu)
 {
   enum intr_level old_level;
 
@@ -480,9 +708,18 @@ init_thread (struct thread *t, const char *name, int priority)
   t->status = THREAD_BLOCKED;
   strlcpy (t->name, name, sizeof t->name);
   t->stack = (uint8_t *) t + PGSIZE;
-  t->priority = priority;
   t->magic = THREAD_MAGIC;
 
+  t->base_priority
+      = thread_mlfqs ? calculate_bsd_priority (recent_cpu, nice) : priority;
+  list_init (&t->donors_list);
+  list_push_back (&t->donors_list, &t->donor_elem);
+  t->waiting_lock = NULL;
+
+  t->nice = nice;
+  t->recent_cpu = recent_cpu;
+  t->priority = t->base_priority;
+
   old_level = intr_disable ();
   list_push_back (&all_list, &t->allelem);
   intr_set_level (old_level);
@@ -561,6 +798,21 @@ thread_schedule_tail (struct thread *prev)
     }
 }
 
+/* Calculates BSD priority for a thread */
+static int
+calculate_bsd_priority (fp32_t recent_cpu, int nice)
+{
+
+  ASSERT (thread_mlfqs);
+
+  int priority = PRI_MAX - (fp_round (recent_cpu) / 4) - (nice * 2);
+  if (priority < PRI_MIN)
+    return PRI_MIN;
+  if (priority > PRI_MAX)
+    return PRI_MAX;
+  return priority;
+}
+
 /* Schedules a new process.  At entry, interrupts must be off and
    the running process's state must have been changed from
    running to some other state.  This function finds another
@@ -598,6 +850,29 @@ allocate_tid (void)
   return tid;
 }
 
+/* Hashing function needed for child_results table.
+   Returns hash of process_result's TID. */
+static unsigned
+process_result_hash (const struct hash_elem *e, void *aux UNUSED)
+{
+  const struct process_result *result
+      = hash_entry (e, struct process_result, elem);
+  return hash_int (result->tid);
+}
+
+/* Comparator function needed for child_results table.
+   Returns less than comparison on process_results' TIDs. */
+static bool
+process_result_less (const struct hash_elem *a_, const struct hash_elem *b_,
+                     void *aux UNUSED)
+{
+  const struct process_result *a
+      = hash_entry (a_, struct process_result, elem);
+  const struct process_result *b
+      = hash_entry (b_, struct process_result, elem);
+  return a->tid < b->tid;
+}
+
 /* Offset of `stack' member within `struct thread'.
    Used by switch.S, which can't figure it out on its own. */
 uint32_t thread_stack_ofs = offsetof (struct thread, stack);

src/threads/thread.h

@@ -2,8 +2,12 @@
 #define THREADS_THREAD_H
 
 #include <debug.h>
+#include <hash.h>
 #include <list.h>
 #include <stdint.h>
+#include <stdbool.h>
+#include "threads/synch.h"
+#include "threads/fixed-point.h"
 
 /* States in a thread's life cycle. */
 enum thread_status
@@ -24,6 +28,25 @@ typedef int tid_t;
 #define PRI_DEFAULT 31                  /* Default priority. */
 #define PRI_MAX 63                      /* Highest priority. */
 
+#define NICE_MIN -20   /* Lowest niceness. */
+#define NICE_DEFAULT 0 /* Default niceness. */
+#define NICE_MAX 20    /* Highest niceness. */
+
+/* File Descriptors. */
+#define MINIMUM_USER_FD 2 /* Minimum file descriptor for user programs. */
+
+/* A process result, synchronised between parent and child. */
+struct process_result
+{
+  tid_t tid;             /* The tid of the child process. */
+  int exit_status;       /* The exit status of the child process. Initially set
+                            to -1, then to exit_status when child dies. */
+  struct lock lock;      /* Lock the exit_status and sema. */
+  struct semaphore sema; /* Semaphore to signal the parent that the exit_status
+                            has been set. */
+  struct hash_elem elem; /* Hash element for the parent's children map. */
+};
+
 /* A kernel thread or user process.
 
    Each thread structure is stored in its own 4 kB page.  The
@@ -90,14 +113,42 @@ struct thread
     int priority;                       /* Priority. */
     struct list_elem allelem;           /* List element for all threads list. */
 
+    /* Donation Related */
+    int base_priority;                  /* Base priority of the thread. */
+    struct list donors_list;            /* List of threads that have donated
+                                           to this thread. */
+    struct lock *waiting_lock;          /* The lock that the current thread is
+                                           waiting for. */
+    struct list_elem donor_elem;        /* List element so that thread can be
+                                           enlisted in other donors list. */
+
+    /* MLFQS items */
+    int nice;                           /* Nice value for this thread */
+    fp32_t recent_cpu;                  /* Amount of time this process received */
+
+    /* Process wait properties. */
+    struct process_result *result;      /* Result of the process. */
+    struct hash child_results;          /* Map of children's of this thread
+                                           TID to process result. */
+    struct file *exec_file;             /* Thread's currently running file */
+
     /* Shared between thread.c and synch.c. */
     struct list_elem elem;              /* List element. */
 
 #ifdef USERPROG
     /* Owned by userprog/process.c. */
     uint32_t *pagedir;                  /* Page directory. */
+    unsigned int fd_counter;            /* File descriptor counter for thread's
+                                           open files. */
+    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. */
   };
@@ -131,12 +182,17 @@ void thread_yield (void);
 typedef void thread_action_func (struct thread *t, void *aux);
 void thread_foreach (thread_action_func *, void *);
 
+bool priority_more (const struct list_elem *a_, const struct list_elem *b_,
+                    void *aux UNUSED);
 int thread_get_priority (void);
 void thread_set_priority (int);
+void thread_recalculate_priority (void);
 
 int thread_get_nice (void);
 void thread_set_nice (int);
 int thread_get_recent_cpu (void);
 int thread_get_load_avg (void);
 
+void ready_list_reinsert (struct thread *t);
+
 #endif /* threads/thread.h */

src/userprog/exception.c

@@ -1,15 +1,25 @@
 #include "userprog/exception.h"
 #include <inttypes.h>
 #include <stdio.h>
+#include "stdbool.h"
 #include "userprog/gdt.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
 
 /* Number of page faults processed. */
 static long long page_fault_cnt;
 
 static void kill (struct intr_frame *);
 static void page_fault (struct intr_frame *);
+bool try_fetch_page (void *upage, bool write);
 
 /* Registers handlers for interrupts that can be caused by user
    programs.
@@ -145,6 +155,49 @@ page_fault (struct intr_frame *f)
   write = (f->error_code & PF_W) != 0;
   user = (f->error_code & PF_U) != 0;
 
+#ifdef VM
+  void *upage = pg_round_down (fault_addr);
+  if (not_present && is_user_vaddr(upage))
+    {
+      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. */
@@ -156,3 +209,35 @@ page_fault (struct intr_frame *f)
   kill (f);
 }
 
+#ifdef VM
+bool
+try_fetch_page (void *upage, bool write)
+{
+  /* Check if the page is in the supplemental page table. That is, it is a page
+     that is expected to be in memory. */
+  struct page_entry *page = page_get (upage);
+  if (page == NULL)
+    return false;
+
+  /* An attempt to write to a non-writeable should fail. */
+  if (write && !page->writable)
+    return false;
+
+  /* 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, 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

@@ -1,6 +1,8 @@
 #ifndef USERPROG_EXCEPTION_H
 #define USERPROG_EXCEPTION_H
 
+#include <stdbool.h>
+
 /* Page fault error code bits that describe the cause of the exception.  */
 #define PF_P 0x1    /* 0: not-present page. 1: access rights violation. */
 #define PF_W 0x2    /* 0: read, 1: write. */
@@ -8,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

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

src/userprog/pagedir.h

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

src/userprog/process.c

@@ -1,12 +1,15 @@
 #include "userprog/process.h"
 #include <debug.h>
+#include <hash.h>
 #include <inttypes.h>
+#include <list.h>
 #include <round.h>
 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
 #include "userprog/gdt.h"
 #include "userprog/pagedir.h"
+#include "userprog/syscall.h"
 #include "userprog/tss.h"
 #include "filesys/directory.h"
 #include "filesys/file.h"
@@ -14,57 +17,173 @@
 #include "threads/flags.h"
 #include "threads/init.h"
 #include "threads/interrupt.h"
+#include "threads/synch.h"
 #include "threads/palloc.h"
+#include "threads/malloc.h"
 #include "threads/thread.h"
 #include "threads/vaddr.h"
+#include "threads/synch.h"
+#include "devices/timer.h"
+#include "vm/page.h"
+#ifdef VM
+#include "vm/frame.h"
+#endif
+
+/* Defines the native number of bytes processed by the processor
+   (for the purposes of alignment). */
+#define WORD_SIZE 4
+
+/* Defines non-negative integer division wherein the result is always rounded
+   up. */
+#define DIV_CEIL(x, y) ((x + (y - 1)) / y)
+
+/* Keeps track of the position of pointers to user program arguments
+   within a linked list. */
+struct arg_elem
+  {
+    char* arg;
+    struct list_elem elem;
+  };
+
+/* Holds the data required to be passed from a kernel thread to a thread
+   that executes process_start for the purpose of starting a user process. */
+struct process_start_data
+  {
+    char *cmd_saveptr; /* Value pointed to by 'saveptr' argument used by
+                          successive calls to strtok_r to split 'cmd' into
+                          tokens while maintaining state. */
+    char file_name[FNAME_MAX_LEN + 1]; /* Name of the file of the process to
+                                      be started. */
+    bool success; /* Indicates whether the process was successfully loaded. */
+    struct semaphore loaded; /* Semaphore used to signal that the process has
+                                finished attempting to load. */
+  };
 
 static thread_func start_process NO_RETURN;
+static void destruct_process_result (struct hash_elem *e, void *aux UNUSED);
 static bool load (const char *cmdline, void (**eip) (void), void **esp);
 
-/* Starts a new thread running a user program loaded from
+/* Starts a new thread running a user program executed via
-   FILENAME.  The new thread may be scheduled (and may even exit)
+   CMD.  The new thread may be scheduled (and may even exit)
    before process_execute() returns.  Returns the new process's
    thread id, or TID_ERROR if the thread cannot be created. */
 tid_t
-process_execute (const char *file_name) 
+process_execute (const char *cmd) 
 {
-  char *fn_copy;
+  char *cmd_copy;
   tid_t tid;
+  struct process_start_data data;
 
-  /* Make a copy of FILE_NAME.
+  /* Make a copy of command.
      Otherwise there's a race between the caller and load(). */
-  fn_copy = palloc_get_page (0);
+  cmd_copy = palloc_get_page (0);
-  if (fn_copy == NULL)
+  if (cmd_copy == NULL)
     return TID_ERROR;
-  strlcpy (fn_copy, file_name, PGSIZE);
 
-  /* Create a new thread to execute FILE_NAME. */
+  /* Imposing implicit limit that the command line arguments
-  tid = thread_create (file_name, PRI_DEFAULT, start_process, fn_copy);
+    including the user program name fit within a single page. */
-  if (tid == TID_ERROR)
+  strlcpy (cmd_copy, cmd, PGSIZE);
-    palloc_free_page (fn_copy); 
+
+  /* Retrieve first argument of command, which is the file name
+     of the process. */
+  char *file_name = strtok_r (cmd_copy, " ", &data.cmd_saveptr);
+
+  /* Validates that the current file to be executed can be opened/exists. */
+  lock_acquire (&filesys_lock);
+  struct file *file = filesys_open (file_name);
+  lock_release (&filesys_lock);
+  if (file == NULL)
+    return TID_ERROR;
+
+  /* Create a new thread to execute the command, by initializing
+     it running the function 'start_process' with the appropriate
+     arguments. For details of arguments, see 'start_process'. */
+  strlcpy (data.file_name, file_name, FNAME_MAX_LEN + 1);
+  sema_init (&data.loaded, 0);
+  data.success = false;
+
+  tid = thread_create (file_name, PRI_DEFAULT, start_process, &data);
+
+  /* Wait until process file has finished attempting to load via the child
+     thread before reporting success of starting execution. */
+  if (tid != TID_ERROR)
+    {
+      sema_down (&data.loaded);
+      if (!data.success)
+        tid = TID_ERROR;
+    }
+
+  palloc_free_page (cmd_copy);
   return tid;
 }
 
-/* A thread function that loads a user process and starts it
+static void *get_usr_kpage (enum palloc_flags flags, void *upage);
-   running. */
+static void free_usr_kpage (void *kpage);
+bool install_page (void *upage, void *kpage, bool writable);
+
+static bool process_init_stack (char *cmd_saveptr, void **esp, char *file_name);
+static void *push_to_stack (void **esp, void *data, size_t data_size);
+#define push_var_to_stack(esp, var) (push_to_stack (esp, &var, sizeof (var)))
+
+/* Make the current thread execute 'cmd', passing in a copy of the
+   command string used for processing, the saveptr used by strtok_r
+   (in order to further tokenize the same command and retrieve its
+   arguments), the name of the file being executed, and a semaphore that
+   calls sema_up to indicate that the 'success' variable passed to it
+   has been updated to indicate whether the process file loading succeeded. 
+   This involves loading the specified file and calling its main () function
+   with the specified command arguments. */
 static void
-start_process (void *file_name_)
+start_process (void *proc_start_data)
 {
-  char *file_name = file_name_;
   struct intr_frame if_;
-  bool success;
+  struct process_start_data *data = proc_start_data;
 
   /* Initialize interrupt frame and load executable. */
   memset (&if_, 0, sizeof if_);
   if_.gs = if_.fs = if_.es = if_.ds = if_.ss = SEL_UDSEG;
   if_.cs = SEL_UCSEG;
   if_.eflags = FLAG_IF | FLAG_MBS;
-  success = load (file_name, &if_.eip, &if_.esp);
 
-  /* If load failed, quit. */
+  /* Acquire the file system lock to prevent race conditions. */
-  palloc_free_page (file_name);
+  lock_acquire (&filesys_lock);
+
+  struct file *exec_file = filesys_open (data->file_name);
+  if (exec_file == NULL)
+    {
+      /* If the executable file cannot be opened, free resources and quit. */
+      lock_release (&filesys_lock);
+      sema_up (&data->loaded);
+      thread_exit ();
+    }
+
+  /* Deny write to the executable file to prevent writing to it and release the
+     file system lock. */
+  file_deny_write (exec_file);
+  lock_release (&filesys_lock);
+
+  thread_current ()->exec_file = exec_file;
+
+  /* Load the ELF executable file, and store the success of the operation in
+     the 'success' variable in data. */
+  data->success = load (data->file_name, &if_.eip, &if_.esp);
+
+  /* If load was sucessful, initialize user process stack and free page used
+ to store the command that executed the process. */
+  if (data->success)
+    {
+      data->success =
+        process_init_stack (data->cmd_saveptr, &if_.esp, data->file_name);
+    }
+
+  /* Signal that the process has finished attempting to load. */
+  bool success = data->success;
+  sema_up (&data->loaded);
+  
+  /* If the load was unsuccessful or if it was but the stack initialization
+     failed, exit the thread. */
   if (!success)
-    thread_exit ();
+      thread_exit ();
 
   /* Start the user process by simulating a return from an
      interrupt, implemented by intr_exit (in
@@ -76,6 +195,124 @@ start_process (void *file_name_)
   NOT_REACHED ();
 }
 
+/* Helper function that initializes the stack of a newly created 
+   user process. Returns true if successful, false otherwise. */
+static bool
+process_init_stack (char *cmd_saveptr, void **esp, char *file_name)
+  {
+    ASSERT (cmd_saveptr != NULL);
+    ASSERT (esp != NULL);
+    ASSERT (file_name != NULL);
+
+    /* Load command line argument *data* to user process stack.
+       This can't cause overflow due to enforcing that the size of
+       command line input must fit in a page. Also keep track
+       of pointers to the argument data within a linked list. */
+    struct list arg_list;
+    list_init (&arg_list);
+
+    char *arg = file_name;
+    int arg_count = 0;
+    while (arg != NULL)
+      {
+        /* filename has already been validated to be a safe-to-access string,
+           so we can safely use strlen here. Filename has already been
+           split from the command line arguments. */
+        push_to_stack (esp, arg, (strlen (arg) + 1) * sizeof (char));
+
+        /* Try to allocate memory for the argument pointer. */
+        struct arg_elem *arg_elem = malloc (sizeof (struct arg_elem));
+        if (arg_elem == NULL)
+          {
+            printf("ERROR: Couldn't allocate argument pointer memory for %s!\n",
+                   thread_current ()->name);
+            return false;
+          }
+
+        /* Store the argument pointer in the linked list. */
+        arg_elem->arg = *esp;
+        list_push_front (&arg_list, &arg_elem->elem);
+
+        /* Increment the argument count and get the next argument. */
+        arg_count++;
+        arg = strtok_r (NULL, " ", &cmd_saveptr);
+      }
+
+    /* Calculate the remaining number of bytes that need to be written
+       to the user process stack in order to check for possible overflow. */
+    size_t align_size = ((unsigned int) *esp % WORD_SIZE) * sizeof (uint8_t);
+    size_t argv_data_size = (arg_count + 1) * sizeof (char *);
+    size_t argv_size = sizeof (char **);
+    size_t argc_size = sizeof (int);
+    size_t return_addr_size = sizeof (void *);
+    size_t remaining_size = align_size + argv_data_size + argv_size + argc_size
+                            + return_addr_size;
+
+    /* If pushing the rest of the data required for the stack would cause
+       overflow, allocate as many extra pages as needed to the user process
+       contiguously in the virtual address space below the initial page. */
+    int overflow_bytes = (PHYS_BASE - *esp) + remaining_size - PGSIZE;
+    if (overflow_bytes > 0)
+      {
+        /* Calculate the number of pages needed to allocate. */
+        int pages_needed = DIV_CEIL (overflow_bytes, PGSIZE);
+
+        /* Allocate the pages and map them to the user process. */
+        void *upage;
+        uint8_t *kpage;
+        for (int i = 1; i < pages_needed + 1; i++)
+          {
+            upage = ((uint8_t *) PHYS_BASE) - PGSIZE * (i + 1);
+            kpage = get_usr_kpage (PAL_ZERO, upage);
+            if (!install_page (upage, kpage, true)) return false;
+          }
+      }
+
+    /* Align stack pointer to word size before pushing argv elements for
+       performance. */
+    *esp -= align_size;
+    
+    /* Push a null pointer sentinel inside argv. */
+    char *null_sentinel = NULL;
+    push_var_to_stack (esp, null_sentinel); 
+
+    /* Push pointers to process arguments from argument linked list */
+    struct list_elem *e = list_begin (&arg_list);
+    struct list_elem *tail = list_tail (&arg_list);
+    while (e != tail)
+      {
+        struct arg_elem *arg_elem = list_entry (e, struct arg_elem, elem);
+        
+        push_var_to_stack(esp, arg_elem->arg);
+        
+        e = list_next (e);
+        free (arg_elem);
+      }
+
+    /* Push pointer to the start of argv array. */
+    char **argv = *esp;
+    push_var_to_stack(esp, argv);
+
+    /* Push the number of arguments to the stack. */
+    push_var_to_stack(esp, arg_count);
+
+    /* Push fake return address (null pointer). */
+    push_var_to_stack (esp, null_sentinel); 
+
+    return true;
+ }
+
+/* Helper function that pushes the first 'data_size' bytes stored
+   in the address '*data' into the stack given a pointer to the
+   stack pointer '**esp'. */
+static void *
+push_to_stack (void **esp, void *data, size_t data_size)
+{
+  *esp -= data_size;
+  memcpy (*esp, data, data_size);
+  return *esp;
+}
+
 /* Waits for thread TID to die and returns its exit status. 
  * If it was terminated by the kernel (i.e. killed due to an exception), 
  * returns -1.  
@@ -86,9 +323,37 @@ start_process (void *file_name_)
  * This function will be implemented in task 2.
  * For now, it does nothing. */
 int
-process_wait (tid_t child_tid UNUSED) 
+process_wait (tid_t child_tid)
 {
-  return -1;
+  struct thread *t = thread_current ();
+  struct process_result fake_result;
+  fake_result.tid = child_tid;
+  struct hash_elem *e = hash_find (&t->child_results, &fake_result.elem);
+  if (e == NULL)
+    return -1;
+
+  struct process_result *child_result
+      = hash_entry (e, struct process_result, elem);
+  /* Wait for child to die. */
+  sema_down (&child_result->sema);
+
+  /* We need lock release in process_exit, so we need to acquire (and possibly
+     wait) for it here to ensure we don't free the lock memory before it is
+     released in process_exit. */
+  lock_acquire (&child_result->lock);
+  /* To prevent waiting for child twice, remove it from the table.
+     No need to use lock since this is the only thread with access to
+     the struct process_result now. */
+  hash_delete (&t->child_results, &child_result->elem);
+
+  /* Get the exit status of the child */
+  int exit_status = child_result->exit_status;
+
+  /* Release the lock */
+  lock_release (&child_result->lock);
+  /* Result no-longer used by parent, nor child. Deallocate it. */
+  free (child_result);
+  return exit_status;
 }
 
 /* Free the current process's resources. */
@@ -98,6 +363,31 @@ process_exit (void)
   struct thread *cur = thread_current ();
   uint32_t *pd;
 
+  /* Clean up all open files */
+  hash_destroy (&cur->open_files, fd_cleanup);
+#ifdef VM
+  hash_destroy (&cur->pages, page_cleanup);
+#endif
+
+  /* Close the executable file, implicitly allowing it to be written to. */
+  if (cur->exec_file != NULL)
+    {
+      /* Acquire the file system lock to prevent race conditions. */
+      lock_acquire (&filesys_lock);
+      file_close (cur->exec_file);
+      lock_release (&filesys_lock);
+    }
+
+  if (cur->result != NULL)
+    {
+      printf ("%s: exit(%d)\n", cur->name, cur->result->exit_status);
+      /* Update own process result. */
+      destruct_process_result (&cur->result->elem, cur);
+    }
+
+  /* Free child process results or signal parent's death. */
+  hash_destroy (&cur->child_results, destruct_process_result);
+
   /* Destroy the current process's page directory and switch back
      to the kernel-only page directory. */
   pd = cur->pagedir;
@@ -116,6 +406,28 @@ process_exit (void)
     }
 }
 
+/* Destruct a process_result, with multi-thread awareness.
+   If the other thread is running, simply signals death. Otherwise
+   frees the result. */
+static void
+destruct_process_result (struct hash_elem *e, void *aux UNUSED)
+{
+  struct process_result *result = hash_entry (e, struct process_result, elem);
+  lock_acquire (&result->lock);
+  /* Other thread has died (and was not waited for). Free the result. */
+  if (sema_try_down (&result->sema))
+    {
+      lock_release (&result->lock);
+      free (result);
+    }
+  /* Other thread is still alive, signal via sema that parent has died. */
+  else
+    {
+      sema_up (&result->sema);
+      lock_release (&result->lock);
+    }
+}
+
 /* Sets up the CPU for running user code in the current
    thread.
    This function is called on every context switch. */
@@ -214,6 +526,7 @@ load (const char *file_name, void (**eip) (void), void **esp)
   off_t file_ofs;
   bool success = false;
   int i;
+  lock_acquire (&filesys_lock);
 
   /* Allocate and activate page directory. */
   t->pagedir = pagedir_create ();
@@ -312,14 +625,15 @@ 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;
 }
 
 /* load() helpers. */
 
-static bool install_page (void *upage, void *kpage, bool writable);
-
 /* Checks whether PHDR describes a valid, loadable segment in
    FILE and returns true if so, false otherwise. */
 static bool
@@ -387,6 +701,28 @@ 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.
+         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;
+
+      /* 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)
+        return false;
+
+      /* Advance. */
+      read_bytes -= page_read_bytes;
+      zero_bytes -= page_zero_bytes;
+      ofs += PGSIZE;
+      upage += PGSIZE;
+    }
+  return true;
+#else
   file_seek (file, ofs);
   while (read_bytes > 0 || zero_bytes > 0) 
     {
@@ -403,7 +739,7 @@ load_segment (struct file *file, off_t ofs, uint8_t *upage,
       if (kpage == NULL){
         
         /* Get a new page of memory. */
-        kpage = palloc_get_page (PAL_USER);
+        kpage = get_usr_kpage (0, upage);
         if (kpage == NULL){
           return false;
         }
@@ -411,7 +747,7 @@ load_segment (struct file *file, off_t ofs, uint8_t *upage,
         /* Add the page to the process's address space. */
         if (!install_page (upage, kpage, writable)) 
         {
-          palloc_free_page (kpage);
+          free_usr_kpage (kpage);
           return false; 
         }     
         
@@ -436,6 +772,7 @@ load_segment (struct file *file, off_t ofs, uint8_t *upage,
       upage += PGSIZE;
     }
   return true;
+#endif
 }
 
 /* Create a minimal stack by mapping a zeroed page at the top of
@@ -446,18 +783,53 @@ setup_stack (void **esp)
   uint8_t *kpage;
   bool success = false;
   
-  kpage = palloc_get_page (PAL_USER | PAL_ZERO);
+  void *upage = ((uint8_t *) PHYS_BASE) - PGSIZE;
+  
+  kpage = get_usr_kpage (PAL_ZERO, upage);
   if (kpage != NULL) 
     {
-      success = install_page (((uint8_t *) PHYS_BASE) - PGSIZE, kpage, true);
+      success = install_page (upage, kpage, true);
       if (success)
         *esp = PHYS_BASE;
       else
-        palloc_free_page (kpage);
+        free_usr_kpage (kpage);
     }
   return success;
 }
 
+/* Claims a page from the user pool for ownership by the current thread
+   and returns its kernel address, updating the frame table if VM
+   is enabled. Requires the intended virtual address for where the page
+   will be installed. */
+static void *
+get_usr_kpage (enum palloc_flags flags, void *upage)
+{
+  void *page;
+#ifdef VM
+  struct thread *t = thread_current ();
+  if (pagedir_get_page (t->pagedir, upage) != NULL)
+    return NULL;
+  else
+    page = frame_alloc (flags, upage, t);
+  pagedir_set_accessed (t->pagedir, upage, true);
+#else
+  page = palloc_get_page (flags | PAL_USER);
+#endif
+  return page;
+}
+
+/* Frees a page belonging to a user process given its kernel address,
+   updating the frame table if VM is enabled. */
+static void
+free_usr_kpage (void *kpage)
+{
+#ifdef VM
+  frame_free (kpage);
+#else
+  palloc_free_page (kpage);
+#endif
+}
+
 /* Adds a mapping from user virtual address UPAGE to kernel
    virtual address KPAGE to the page table.
    If WRITABLE is true, the user process may modify the page;
@@ -467,7 +839,7 @@ setup_stack (void **esp)
    with palloc_get_page().
    Returns true on success, false if UPAGE is already mapped or
    if memory allocation fails. */
-static bool
+bool
 install_page (void *upage, void *kpage, bool writable)
 {
   struct thread *t = thread_current ();

src/userprog/process.h

@@ -8,4 +8,6 @@ int process_wait (tid_t);
 void process_exit (void);
 void process_activate (void);
 
+bool install_page (void *upage, void *kpage, bool writable);
+
 #endif /* userprog/process.h */

src/userprog/syscall.c

@@ -1,20 +1,539 @@
 #include "userprog/syscall.h"
-#include <stdio.h>
+#include "devices/shutdown.h"
-#include <syscall-nr.h>
+#include "devices/input.h"
+#include "filesys/file.h"
+#include "filesys/filesys.h"
+#include "threads/vaddr.h"
 #include "threads/interrupt.h"
+#include "threads/malloc.h"
 #include "threads/thread.h"
+#include "threads/synch.h"
+#include "userprog/process.h"
+#include "userprog/pagedir.h"
+#include <stdio.h>
+#include <stdbool.h>
+#include <syscall-nr.h>
+
+#define MAX_SYSCALL_ARGS 3
+#define EXIT_FAILURE -1
+
+struct open_file
+  {
+    int fd;                     /* File Descriptor / Identifier */
+    struct file *file;          /* Pointer to the associated file */
+    struct hash_elem elem;      /* elem for a hash table */
+  };
 
 static void syscall_handler (struct intr_frame *);
 
+/* A syscall_function is a function that receives up to 3 arguments, the
+   arguments to the functions are either ints or pointers taking up to 32 bits
+   in size. */
+typedef uintptr_t (*syscall_function) (uintptr_t, uintptr_t, uintptr_t);
+
+/* System call function prototypes */
+static void syscall_halt (void);
+static void syscall_exit (int status);
+static pid_t syscall_exec (const char *cmd_line);
+static int syscall_wait (pid_t pid);
+static bool syscall_create (const char *file, unsigned initial_size);
+static bool syscall_remove (const char *file);
+static int syscall_open (const char *file);
+static int syscall_filesize (int fd);
+static int syscall_read (int fd, void *buffer, unsigned size);
+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 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);
+
+/* A struct defining a syscall_function pointer along with its arity. */
+struct syscall_arguments
+  {
+    syscall_function function;    /* Function pointer. */
+    int arity;                    /* Number of arguments of the function. */
+  };
+
+/* A look-up table mapping numbers to system call functions with their number of
+   arguments. */
+static const struct syscall_arguments syscall_lookup[] =
+{
+  [SYS_HALT] = {(syscall_function) syscall_halt, 0},
+  [SYS_EXIT] = {(syscall_function) syscall_exit, 1},
+  [SYS_EXEC] = {(syscall_function) syscall_exec, 1},
+  [SYS_WAIT] = {(syscall_function) syscall_wait, 1},
+  [SYS_CREATE] = {(syscall_function) syscall_create, 2},
+  [SYS_REMOVE] = {(syscall_function) syscall_remove, 1},
+  [SYS_OPEN] = {(syscall_function) syscall_open, 1},
+  [SYS_FILESIZE] = {(syscall_function) syscall_filesize, 1},
+  [SYS_READ] = {(syscall_function) syscall_read, 3},
+  [SYS_WRITE] = {(syscall_function) syscall_write, 3},
+  [SYS_SEEK] = {(syscall_function) syscall_seek, 2},
+  [SYS_TELL] = {(syscall_function) syscall_tell, 1},
+  [SYS_CLOSE] = {(syscall_function) syscall_close, 1},
+};
+
+/* The number of syscall functions (i.e, number of elements) within the
+   syscall_lookup table. */
+static const int LOOKUP_SIZE
+  = sizeof (syscall_lookup) / sizeof (struct syscall_arguments);
+
+/* Initialises the syscall handling system, as well as a global lock to
+   synchronise all file access between processes. */
 void
 syscall_init (void) 
 {
   intr_register_int (0x30, 3, INTR_ON, syscall_handler, "syscall");
+  lock_init (&filesys_lock);
+}
+
+/* Function that takes an interrupt frame containing a syscall and its args.
+   Validates the arguments and pointers before calling the relevant
+   high-level system call function, storing its output (if any) in f->eax */
+static void
+syscall_handler (struct intr_frame *f)
+{
+  /* First, read the system call number from the stack. */
+  validate_user_pointer (f->esp, sizeof (uintptr_t), false);
+  uintptr_t syscall_number = *(int *)f->esp;
+  thread_current ()->curr_esp = f->esp;
+
+  /* Ensures the number corresponds to a system call that can be handled. */
+  if (syscall_number >= LOOKUP_SIZE)
+    syscall_exit (EXIT_FAILURE);
+
+  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),
+                         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++)
+    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. */
+  f->eax = syscall.function (args[0], args[1], args[2]);
+}
+
+/* Called upon a "halt" syscall, resulting in a complete shutdown of the
+   process, via shutdown_power_off (); */
+static void
+syscall_halt (void)
+{
+  shutdown_power_off ();
 }
 
 static void
-syscall_handler (struct intr_frame *f UNUSED) 
+syscall_exit (int status)
 {
-  printf ("system call!\n");
+  /* Sets exit_status of the thread to status. thread_exit () will call
+     process_exit () if user programs are allowed. */
+  thread_current ()->result->exit_status = status;
   thread_exit ();
 }
+
+/* Executes a given command with the relevant args, by calling process_execute.
+   Returns PID for the process that is running the CMD_LINE. */
+static pid_t
+syscall_exec (const char *cmd_line)
+{
+  validate_user_string (cmd_line, false);
+
+  return process_execute (cmd_line); /* Returns the PID of the new process */
+}
+
+/* Handles the syscall of wait. Effectively a wrapper for process_wait as the
+   necessary validation and such all happens in process_wait anyway. */
+static int
+syscall_wait (pid_t pid)
+{
+  return process_wait (pid); /* Returns the exit status of the waited process */
+}
+
+/* Handles the syscall for file creation. First validates the user file
+   pointer. Acquires the file system lock to prevent synchronisation issues,
+   and then uses FILESYS_CREATE to create the file, returning the same status */
+static bool
+syscall_create (const char *file, unsigned initial_size)
+{
+  validate_user_string (file, false);
+
+  /* Acquire the file system lock to prevent race conditions. */
+  lock_acquire (&filesys_lock);
+  bool status = filesys_create (file, initial_size);
+  lock_release (&filesys_lock);
+
+  /* Return the status of the file creation. */
+  return status;
+}
+
+/* Handles the syscall for file removal. First validates the user file pointer.
+   Acquires the file system lock to prevent synchronisation issues, and then
+   uses FILESYS_REMOVE to remove the file, returning the same success status */
+static bool
+syscall_remove (const char *file)
+{
+  validate_user_string (file, false);
+
+  /* Acquire the file system lock to prevent race conditions. */
+  lock_acquire (&filesys_lock);
+  bool status = filesys_remove (file);
+  lock_release (&filesys_lock);
+
+  /* Return the status of the file removal. */
+  return status;
+}
+
+/* Handles the syscall for opening a file connection. First, validates the file
+   pointer. Then it acquires a lock for the file system, in order to open the
+   connection without synchronisation issues. It then maps a new fd to this file
+   in the hash table before returning the fd. */
+static int
+syscall_open (const char *file)
+{
+  validate_user_string (file, false);
+
+  /* Acquire the file system lock to prevent race conditions. */
+  lock_acquire (&filesys_lock);
+  struct file *ptr = filesys_open (file);
+  lock_release (&filesys_lock);
+
+  /* If the file could not be opened, return failure. */
+  if (ptr == NULL)
+    return EXIT_FAILURE;
+
+  /* Allocate space for a struct representing a mapping from an FD to a struct
+     file. */
+  struct open_file *file_info
+    = (struct open_file*) malloc (sizeof (struct open_file));
+  if (file_info == NULL)
+    {
+      /* If we could not allocate memory for the file_info struct, close the
+         file and return failure. */
+      file_close (ptr);
+      return EXIT_FAILURE;
+    }
+
+  /* Populate the above struct, with a unique FD and the current open file */
+  file_info->fd = thread_current ()->fd_counter++;
+  file_info->file = ptr;
+
+  /* Add the new FD->file mapping to the hashtable for the current thread */
+  hash_insert (&thread_current ()->open_files, &file_info->elem);
+
+  /* Return the new FD */
+  return file_info->fd;
+}
+
+/* Handles the syscall for getting a file's size. Converts a provided FD into
+   the asssociated file struct. Acquire the lock for the filesystem and use
+   FILE_LENGTH to calculate the length for return. */
+static int
+syscall_filesize (int fd)
+{
+  /* Try to get the file from the FD. If it does not exist, return failure. */
+  struct open_file *file_info = fd_get_file (fd);
+  if (file_info == NULL)
+      return EXIT_FAILURE;
+
+  /* Acquire the file system lock to prevent any race conditions. */
+  lock_acquire (&filesys_lock);
+  int bytes = file_length (file_info->file);
+  lock_release (&filesys_lock);
+
+  /* Return the number of bytes in the file. */
+  return bytes;
+}
+
+/* Handles the syscall for reading SIZE bytes from a file referenced by FD.
+   If the FD references the console, use input_getc (), otherwise convert the
+   FD to its associated file struct, acquire the filesystem lock, read up to
+   SIZE bytes and then return the number of bytes read.*/
+static int
+syscall_read (int fd, void *buffer, unsigned size)
+{
+  /* Only console (fd = 0) or other files, not including STDOUT, (fd > 1) are
+     allowed. */
+  if (fd < STDIN_FILENO || fd == STDOUT_FILENO)
+    return EXIT_FAILURE;
+
+  validate_user_pointer (buffer, size, true);
+
+  if (fd == STDIN_FILENO)
+    {
+      /* Reading from the console. */
+      char *write_buffer = buffer;
+      for (unsigned i = 0; i < size; i++)
+        write_buffer[i] = input_getc ();
+
+      /* In case of console, read is always (eventually) successful. So return
+         the size for the number of bytes read. */
+      return size;
+    }
+  else
+    {
+      /* Reading from a file. */
+      /* Find the file from the FD. If it does not exist, return failure. */
+      struct open_file *file_info = fd_get_file (fd);
+      if (file_info == NULL)
+        return EXIT_FAILURE;
+
+      /* Acquire the file system lock to prevent race-conditions. */
+      lock_acquire (&filesys_lock);
+      int bytes_written = file_read (file_info->file, buffer, size);
+      lock_release (&filesys_lock);
+
+      /* Return the number of bytes read. */
+      return bytes_written;
+    }
+}
+
+/* Handles the syscall for writing SIZE bytes to a file referenced by FD.
+   If the FD references the console, use put_buf (), otherwise convert the
+   FD to its associated file struct, acquire the filesystem lock, write up to
+   SIZE bytes and then return the number of bytes written.*/
+static int
+syscall_write (int fd, const void *buffer, unsigned size)
+{
+  /* Only console (fd = 1) or other files, not including STDIN, (fd > 1) are
+     allowed. */
+  if (fd <= 0)
+    return 0;
+
+  validate_user_pointer (buffer, size, false);
+
+  if (fd == STDOUT_FILENO)
+    {
+      /* Writing to the console. */
+      putbuf (buffer, size);
+
+      /* In case of console, write is always successful. So return the size for
+         the number of bytes written. */
+      return size;
+    }
+  else
+    {
+      /* Writing to a file. */
+      /* Find the file from the FD. If it does not exist, return failure. */
+      struct open_file *file_info = fd_get_file (fd);
+      if (file_info == NULL)
+        return 0;
+
+      /* Acquire the file system lock to prevent race conditions. */
+      lock_acquire (&filesys_lock);
+      int bytes = file_write (file_info->file, buffer, size);
+      lock_release (&filesys_lock);
+
+      /* Return the number of bytes written. */
+      return bytes;
+    }
+}
+
+/* Handles the syscall for seeking to POSITION bytes in a file referenced by
+   FD. Converts the FD to its associated file struct, acquires the filesystem
+   lock and then uses file_seek to adjust the cursor to a specific position in
+   the file.*/
+static void
+syscall_seek (int fd, unsigned position)
+{
+  /* Find the file from the FD. If it does not exist, do nothing. */
+  struct open_file *file_info = fd_get_file (fd);
+  if (file_info != NULL)
+    file_seek (file_info->file, position);
+}
+
+/* Handles the syscall for returning the next byte in a file referenced by
+   FD. Converts the FD to its associated file struct, acquires the filesystem
+   lock and then uses file_tell to read the next byte.*/
+static unsigned
+syscall_tell (int fd)
+{
+  /* Find the file from the FD. If it does not exist, return 0. */
+  struct open_file *file_info = fd_get_file (fd);
+  if (file_info == NULL)
+    return 0;
+
+  unsigned pos = file_tell (file_info->file);
+
+  /* Return the current position in the file. */
+  return pos;
+}
+
+/* Handles the syscall for closing a connection to a file. Converts the FD to
+   its associated file struct. If it exists, it removes it from the hash table,
+   acquires the filesystem lock, and uses file_close to close the connection.*/
+static void
+syscall_close (int fd)
+{
+  /* Find the file from the FD. If it does not exist, do nothing. */
+  struct open_file *file_info = fd_get_file (fd);
+  if (file_info != NULL)
+    {
+      /* File exists */
+      /* First, remove the file from the hash table of open files. */
+      hash_delete (&thread_current ()->open_files, &file_info->elem);
+
+      /* Then, close the file, acquiring the file system lock to prevent race
+         conditions. */
+      lock_acquire (&filesys_lock);
+      file_close (file_info->file);
+      lock_release (&filesys_lock);
+
+      /* Free the memory allocated for the file_info struct. */
+      free (file_info);
+    }
+}
+
+/* Hashing function needed for the open_file table. Returns a hash for an entry,
+   based on its FD. */
+unsigned
+fd_hash (const struct hash_elem *element, void *aux UNUSED)
+{
+  /* We use the FD as the hash value. This is because the FD is incremented
+     sequentially and is therefore unique for each file. It positively affects
+     the performance of the hash table: 1. It is unique so no need to call
+     expensive hash functions. 2. It being sequential means that the hash table
+     is more likely to be weight balanced. */
+  return hash_entry (element, struct open_file, elem)->fd;
+}
+
+/* Comparator function for the open_file table. Compares two entries based on
+   the FDs. */
+bool
+fd_less (const struct hash_elem *a_, const struct hash_elem *b_,
+        void *aux UNUSED)
+{
+  struct open_file *a = hash_entry (a_, struct open_file, elem);
+  struct open_file *b = hash_entry (b_, struct open_file, elem);
+
+  return a->fd < b->fd;
+}
+
+/* Function to clean up an open file entry. Closes the file and frees the
+   associated memory. */
+void
+fd_cleanup (struct hash_elem *e, void *aux UNUSED)
+{
+  struct open_file *file_info = hash_entry (e, struct open_file, elem);
+
+  lock_acquire (&filesys_lock);
+  file_close (file_info->file);
+  lock_release (&filesys_lock);
+
+  free (file_info);
+}
+
+/* Gets a file from its descriptor (FD number). If there is no file with the fd
+   FD it returns NULL. */
+static struct open_file *
+fd_get_file (int fd)
+{
+  /* We have to set up a fake open_file in order to be able to search the hash
+     table. See hash.h. */
+  struct open_file fake_file_info;
+  fake_file_info.fd = fd;
+
+  struct hash_elem *e
+    = hash_find (&thread_current ()->open_files, &fake_file_info.elem);
+
+  if (e == NULL)
+      return NULL;
+
+  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. */
+static void
+validate_user_pointer (const void *ptr, size_t size, bool check_write)
+{
+  if (size == 0)
+    return;
+  /* ptr < ptr + size - 1, so sufficient to check that (ptr + size -1) is a
+     valid user virtual memory address. */
+  void *last = ptr + size - 1;
+  if (!is_user_vaddr (last))
+    syscall_exit (EXIT_FAILURE);
+  ptr = pg_round_down (ptr);
+  while (ptr <= last)
+    {
+      int result;
+      /* Check read access to pointer. */
+      if ((result = get_user (ptr)) == -1)
+        syscall_exit (EXIT_FAILURE);
+      /* Check write access to pointer (if required). */
+      if (check_write && !put_user (ptr, result))
+        syscall_exit (EXIT_FAILURE);
+      ptr += PGSIZE;
+    }
+}
+
+/* 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)
+{
+  size_t offset = (uintptr_t) ptr % PGSIZE;
+
+  for (;;)
+    {
+      void *page = pg_round_down (ptr);
+
+      if (!is_user_vaddr (page))
+        syscall_exit (EXIT_FAILURE);
+      if (!is_user_vaddr (ptr))
+        syscall_exit (EXIT_FAILURE);
+      int result;
+      if ((result = get_user ((const uint8_t *)ptr)) == -1)
+        syscall_exit (EXIT_FAILURE);
+      if (check_write && !put_user ((uint8_t *)ptr, result))
+        syscall_exit (EXIT_FAILURE);
+
+      while (offset < PGSIZE)
+      {
+        if (*ptr == '\0')
+          return; /* We reached the end of the string without issues. */
+
+        ptr++;
+        offset++;
+      }
+
+      offset = 0;
+
+    }
+}
+
+/* PROVIDED BY SPEC.
+   Reads a byte at user virtual address UADDR.
+   UADDR must be below PHYS_BASE.
+   Returns the byte value if successful, -1 if a segfault occurred. */
+static int
+get_user (const uint8_t *uaddr)
+{
+  int result;
+  asm ("movl $1f, %0; movzbl %1, %0; 1:" : "=&a"(result) : "m"(*uaddr));
+  return result;
+}
+
+/* PROVIDED BY SPEC.
+   Writes BYTE to user address UDST.
+   UDST must be below PHYS_BASE.
+   Returns true if successful, false if a segfault occurred. */
+static bool
+put_user (uint8_t *udst, uint8_t byte)
+{
+  int error_code;
+  asm ("movl $1f, %0; movb %b2, %1; 1:"
+       : "=&a"(error_code), "=m"(*udst)
+       : "q"(byte));
+  return error_code != -1;
+}

src/userprog/syscall.h

@@ -1,6 +1,17 @@
 #ifndef USERPROG_SYSCALL_H
 #define USERPROG_SYSCALL_H
 
+#include <hash.h>
+#include "threads/synch.h"
+
+typedef int pid_t;
+
+struct lock filesys_lock;
+
 void syscall_init (void);
 
+unsigned fd_hash (const struct hash_elem *element, void *aux);
+bool fd_less (const struct hash_elem *a, const struct hash_elem *b, void *aux);
+void fd_cleanup (struct hash_elem *e, void *aux);
+
 #endif /* userprog/syscall.h */

src/vm/frame.c

@@ -0,0 +1,262 @@
+#include <debug.h>
+#include <hash.h>
+#include <list.h>
+#include <string.h>
+
+#include "frame.h"
+#include "page.h"
+#include "threads/malloc.h"
+#include "threads/vaddr.h"
+#include "userprog/pagedir.h"
+#include "threads/synch.h"
+#include "devices/swap.h"
+
+/* Hash table that maps every active frame's kernel virtual address
+   to its corresponding 'frame_metadata'.*/
+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;
+
+/* The next element in lru_list to be considered for eviction (oldest added
+   or referenced page in the circular queue). If this page has has an
+   'accessed' bit of 0 when considering eviction, then it will be the next
+   victim. Otherwise, the next element in the queue is similarly considered. */
+struct list_elem *next_victim = NULL;
+
+/* Synchronisation variables. */
+/* Protects access to '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 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);
+
+  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;
+  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)
+        PANIC ("Couldn't allocate a single page to main memory!\n");
+
+      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. */
+      pagedir_clear_page (victim->owner->pagedir, victim->upage);
+
+      // TODO: Lock PTE of victim page for victim process.
+
+      size_t swap_slot = swap_out (victim->frame);
+      page_set_swap (victim->owner, victim->upage, swap_slot);
+
+      /* If zero flag is set, zero out the victim page. */
+      if (flags & PAL_ZERO)
+        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_metadata->upage = upage;
+  frame_metadata->owner = owner;
+  lock_release (&lru_lock);
+
+  return frame_metadata->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. */
+void
+frame_free (void *frame)
+  {
+    struct frame_metadata key_metadata;
+    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);
+  }
+
+/* TODO: Account for page aliases when checking accessed bit. */
+/* A pre-condition for calling this function is that the calling thread
+   owns lru_lock and that lru_list is non-empty. */
+static struct frame_metadata *
+get_victim (void)
+  {
+    struct list_elem *e = next_victim;
+    struct frame_metadata *frame_metadata;
+    uint32_t *pd;
+    void *upage;
+    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))
+          break;
+
+        pagedir_set_accessed (pd, upage, false);
+      }
+
+    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)
+  {
+    struct frame_metadata *frame_metadata = 
+      hash_entry (e, struct frame_metadata, hash_elem);
+
+    return hash_bytes (&frame_metadata->frame, sizeof (frame_metadata->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_,
+                     void *aux UNUSED)
+  {
+    struct frame_metadata *a =
+      hash_entry (a_, struct frame_metadata, hash_elem);
+    struct frame_metadata *b =
+      hash_entry (b_, struct frame_metadata, hash_elem);
+
+    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

@@ -0,0 +1,11 @@
+#ifndef VM_FRAME_H
+#define VM_FRAME_H
+
+#include "threads/thread.h"
+#include "threads/palloc.h"
+
+void frame_init (void);
+void *frame_alloc (enum palloc_flags, void *, struct thread *);
+void frame_free (void *frame);
+
+#endif /* vm/frame.h */

src/vm/page.c

@@ -0,0 +1,158 @@
+#include "page.h"
+#include <string.h>
+#include <stdio.h>
+#include "filesys/file.h"
+#include "threads/pte.h"
+#include "threads/malloc.h"
+#include "threads/palloc.h"
+#include "userprog/process.h"
+#include "userprog/pagedir.h"
+#include "vm/frame.h"
+
+#define SWAP_FLAG_BIT 9
+#define ADDR_START_BIT 12
+
+/* Hashing function needed for the SPT table. Returns a hash for an entry,
+   based on its upage. */
+unsigned
+page_hash (const struct hash_elem *e, UNUSED void *aux)
+{
+  struct page_entry *page = hash_entry (e, struct page_entry, elem);
+  return hash_ptr (page->upage);
+}
+
+/* Comparator function for the SPT table. Compares two entries based on their
+   upages. */
+bool
+page_less (const struct hash_elem *a_, const struct hash_elem *b_,
+           void *aux UNUSED)
+{
+  const struct page_entry *a = hash_entry (a_, struct page_entry, elem);
+  const struct page_entry *b = hash_entry (b_, struct page_entry, elem);
+
+  return a->upage < b->upage;
+}
+
+/* Allocate and insert a new page entry into the thread's page table. */
+struct page_entry *
+page_insert (struct file *file, off_t ofs, void *upage, uint32_t read_bytes,
+             uint32_t zero_bytes, bool writable, enum page_type type)
+{
+  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->type = type;
+
+  hash_insert (&thread_current ()->pages, &page->elem);
+  return page;
+}
+
+/* Gets a page_entry from the starting address of the page. Returns NULL if no
+   such page_entry exists in the hash map.*/
+struct page_entry *
+page_get (void *upage)
+{
+  struct page_entry fake_page_entry;
+  fake_page_entry.upage = upage;
+
+  struct hash_elem *e
+    = hash_find (&thread_current ()->pages, &fake_page_entry.elem);
+
+  if (e == NULL)
+      return NULL;
+
+  return hash_entry (e, struct page_entry, elem);
+}
+
+bool
+page_load (struct page_entry *page, bool writable)
+{
+  /* Allocate a frame for the page. If a frame allocation fails, then
+     frame_alloc should try to evict a page. If it is still NULL, the OS
+     panics as this should not happen if eviction is working correctly. */
+  struct thread *t = thread_current ();
+  void *frame = frame_alloc (0, page->upage, t);
+  pagedir_set_accessed (t->pagedir, page->upage, true);
+  if (frame == NULL)
+    PANIC ("Could not allocate a frame to load page into memory.");
+
+  /* Map the page to the frame. */
+  if (!install_page (page->upage, frame, writable))
+    {
+      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)
+  {
+    frame_free (frame);
+    return false;
+  }
+
+  /* Zero out the remaining bytes in the frame. */
+  memset (frame + page->read_bytes, 0, page->zero_bytes);
+
+  /* Mark the page as loaded successfully. */
+  return true;
+}
+
+/* Function to clean up a page_entry. Given the elem of that page_entry, frees
+   the page_entry itself. */
+void
+page_cleanup (struct hash_elem *e, void *aux UNUSED)
+{
+  free (hash_entry (e, struct page_entry, elem));
+}
+
+/* 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);
+}
+
+/* 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);
+}

src/vm/page.h

@@ -0,0 +1,39 @@
+#ifndef VM_PAGE_H
+#define VM_PAGE_H
+
+#include "threads/thread.h"
+#include "filesys/off_t.h"
+
+enum page_type {
+  PAGE_EXECUTABLE,
+  PAGE_EMPTY
+};
+
+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). */
+
+  /* File Data */
+  struct file *file;   /* Pointer to the file for executables. */
+  off_t offset;        /* Offset of the page content within the file. */
+  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. */
+
+  struct hash_elem elem; /* An elem for the hash table. */
+};
+
+unsigned page_hash (const struct hash_elem *e, void *aux);
+bool page_less (const struct hash_elem *a_, const struct hash_elem *b_,
+                void *aux);
+struct page_entry *page_insert (struct file *file, off_t ofs, void *upage,
+                                uint32_t read_bytes, uint32_t zero_bytes,
+                                bool writable, enum page_type type);
+struct page_entry *page_get (void *upage);
+bool page_load (struct page_entry *page, bool writable);
+void page_cleanup (struct hash_elem *e, void *aux);
+void page_set_swap (struct thread *, void *, size_t);
+bool page_in_swap (struct thread *, void *);
+size_t page_get_swap (struct thread *, void *);
+
+#endif /* vm/frame.h */

src/vm/stackgrowth.c

@@ -0,0 +1,59 @@
+#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_free (new_page);
+    return false;
+  }
+
+  return true;
+}
+

src/vm/stackgrowth.h

@@ -0,0 +1,10 @@
+#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 */