Refactor stack growth to be helper functions in exception for easier merging

# Conflicts:
#   src/Makefile.build

.gitignore

@@ -4,8 +4,12 @@
 #ignore pdf files (just keep source files)
 *.pdf
 
-#ignore shell scripts (only used for testing)
-*.sh
+#ignore Mac OS generated files
+.DS_Store
+
+#ignore code editor generated directories
+.idea
+.vscode
 
 #ignore junk files from latex output
 *.out
@@ -27,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/pt-grow-stack|tests/vm/pt-grow-pusha|tests/vm/pt-big-stk-obj|tests/vm/pt-overflowstk|tests/vm/pt-write-code2|tests/vm/pt-grow-stk-sc|tests/vm/page-linear|tests/vm/page-parallel|tests/vm/page-merge-seq|tests/vm/page-merge-par|tests/vm/page-merge-stk|tests/vm/page-merge-mm|tests/vm/mmap-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,6 +62,8 @@ 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/file.c			# Some other file.
 

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	\
-read-zero read-stdout read-bad-fd write-normal write-bad-ptr		\
+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 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:
-- Test user stack overflow robustness of "exec" system calls.
+Full robustness of argument passing and syscall handling code:
+- 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']);
-(exec-bad-ptr) begin
-(exec-bad-ptr) end
-exec-bad-ptr: exit(0)
-EOF
+check_expected ([<<'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']);
-(open-bad-ptr) begin
-(open-bad-ptr) end
-open-bad-ptr: exit(0)
-EOF
+check_expected ([<<'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']);
-(read-bad-ptr) begin
-(read-bad-ptr) open "sample.txt"
-(read-bad-ptr) end
-read-bad-ptr: exit(0)
-EOF
+check_expected ([<<'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']);
-(write-bad-ptr) begin
-(write-bad-ptr) open "sample.txt"
-(write-bad-ptr) end
-write-bad-ptr: exit(0)
-EOF
+check_expected ([<<'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:
@@ -68,8 +72,7 @@ sema_down (struct semaphore *sema)
   old_level = intr_disable ();
   while (sema->value == 0) 
     {
-      list_insert_ordered (&sema->waiters, &thread_current ()->elem,
-                           &thread_priority_greater, NULL);
+      list_push_back (&sema->waiters, &thread_current ()->elem);
       thread_block ();
     }
   sema->value--;
@@ -107,19 +110,36 @@ sema_try_down (struct semaphore *sema)
 
    This function may be called from an interrupt handler. */
 void
-sema_up (struct semaphore *sema) 
+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));
+  if (!list_empty (&sema->waiters))
+    {
+      /* 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);
-  thread_yield ();
+
+  /* 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_);
@@ -183,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.
@@ -198,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
@@ -233,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);
 }
@@ -255,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. */
@@ -318,9 +480,14 @@ cond_signal (struct condition *cond, struct lock *lock UNUSED)
   ASSERT (!intr_context ());
   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);
+  if (!list_empty (&cond->waiters))
+    {
+      /* 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,23 @@
 #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"
 #ifdef USERPROG
 #include "userprog/process.h"
+#include "userprog/syscall.h"
 #endif
 
 /* Random value for struct thread's `magic' member.
@@ -49,9 +54,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 +71,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 +113,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 +126,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 +173,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 +249,28 @@ 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;
+
+  if (!hash_init (&t->open_files, fd_hash, fd_less, NULL)
+      || !hash_init (&t->child_results, process_result_hash,
+                     process_result_less, t))
+    {
+      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 +294,15 @@ 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);
-  thread_yield ();
+
+  /* Yield if the newly created thread has higher priority than the current
+     thread. */
+  if (t->priority > thread_get_priority ())
+    thread_yield ();
 
   return tid;
 }
@@ -257,7 +340,10 @@ thread_unblock (struct thread *t)
 
   old_level = intr_disable ();
   ASSERT (t->status == THREAD_BLOCKED);
-  list_insert_ordered (&ready_list, &t->elem, &thread_priority_greater, NULL);
+
+  /* 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);
 }
@@ -310,7 +396,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 ();
@@ -327,9 +415,13 @@ thread_yield (void)
   ASSERT (!intr_context ());
 
   old_level = intr_disable ();
-  if (cur != idle_thread) 
-    list_insert_ordered (&ready_list, &cur->elem, thread_priority_greater,
-                         NULL);
+
+  if (cur != idle_thread)
+    {
+      /* 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);
@@ -352,54 +444,161 @@ thread_foreach (thread_action_func *func, void *aux)
     }
 }
 
-/* Sets the current thread's priority to NEW_PRIORITY. */
-void
-thread_set_priority (int new_priority) 
+/* 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 higher priority than that of b_. */
+bool
+priority_more (const struct list_elem *a_, const struct list_elem *b_,
+               void *aux UNUSED)
 {
-  ASSERT (PRI_MIN <= new_priority && new_priority <= PRI_MAX);
-  int old_priority = thread_get_priority ();
+  struct thread *a = list_entry (a_, struct thread, elem);
+  struct thread *b = list_entry (b_, struct thread, elem);
+
+  return a->priority > b->priority;
 
-  thread_current ()->priority = new_priority;
-  if (new_priority < old_priority)
-    thread_yield ();
 }
 
-/* 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 0;
+  return thread_current ()->nice;
 }
 
 /* Returns 100 times the system load average. */
 int
 thread_get_load_avg (void) 
 {
-  /* Not yet implemented. */
-  return 0;
+  return fp_round (fp_mul_int (load_avg, 100));
 }
 
 /* Returns 100 times the current thread's recent_cpu value. */
 int
 thread_get_recent_cpu (void) 
 {
-  /* Not yet implemented. */
-  return 0;
+  return fp_round (fp_mul_int (thread_current ()->recent_cpu, 100));
+}
+
+/* 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.
@@ -472,10 +671,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;
 
@@ -487,9 +702,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);
@@ -568,6 +792,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
@@ -605,15 +844,27 @@ allocate_tid (void)
   return tid;
 }
 
-/* Returns true iff the priority of the first list element's thread is greater
-   than that of the second list element's thread. */
-bool 
-thread_priority_greater (const struct list_elem *a, const struct list_elem *b,
-                         void *aux UNUSED)
+/* 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)
 {
-  struct thread *ta = list_entry (a, struct thread, elem);
-  struct thread *tb = list_entry (b, struct thread, elem);
-  return ta->priority > tb->priority;
+  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'.

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,38 @@ 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
 
+    void *curr_esp;
+
     /* Owned by thread.c. */
     unsigned magic;                     /* Detects stack overflow. */
   };
@@ -131,15 +178,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);
 
-/* Returns true iff the priority of the first list element's thread is greater
-   than that of the second list element's thread. */
-list_less_func thread_priority_greater;
+void ready_list_reinsert (struct thread *t);
+
 #endif /* threads/thread.h */

src/userprog/Make.vars

@@ -1,7 +1,7 @@
 # -*- makefile -*-
 
-kernel.bin: DEFINES = -DUSERPROG -DFILESYS
-KERNEL_SUBDIRS = threads devices lib lib/kernel userprog filesys
+kernel.bin: DEFINES = -DUSERPROG -DFILESYS -DVM
+KERNEL_SUBDIRS = threads devices lib lib/kernel userprog filesys vm
 TEST_SUBDIRS = tests/userprog tests/userprog/no-vm tests/filesys/base
 GRADING_FILE = $(SRCDIR)/tests/userprog/Grading
 SIMULATOR = --qemu

src/userprog/exception.c

@@ -2,8 +2,15 @@
 #include <inttypes.h>
 #include <stdio.h>
 #include "userprog/gdt.h"
+#include "userprog/pagedir.h"
+#include "userprog/process.h"
 #include "threads/interrupt.h"
+#include "threads/palloc.h"
 #include "threads/thread.h"
+#include "threads/vaddr.h"
+
+#define MAX_STACK_SIZE (8 * 1024 * 1024) // 8MB
+#define MAX_STACK_OFFSET 32 // 32 bytes offset below stack pointer (ESP)
 
 /* Number of page faults processed. */
 static long long page_fault_cnt;
@@ -11,6 +18,9 @@ static long long page_fault_cnt;
 static void kill (struct intr_frame *);
 static void page_fault (struct intr_frame *);
 
+static bool is_valid_stack_access (const void *fault_addr, const void *esp);
+static bool grow_stack (void *upage);
+
 /* Registers handlers for interrupts that can be caused by user
    programs.
 
@@ -145,6 +155,27 @@ page_fault (struct intr_frame *f)
   write = (f->error_code & PF_W) != 0;
   user = (f->error_code & PF_U) != 0;
 
+  if (!user || !not_present)
+  {
+    f->eip = (void *)f->eax;
+    f->eax = 0xffffffff;
+    return;
+  }
+
+  /* If the fault address is in a user page that is not present, then it might
+   be just that the stack needs to grow. So we attempt to grow the stack. */
+  void *upage = pg_round_down (fault_addr);
+  if (not_present && is_user_vaddr (upage) && upage != NULL)
+    {
+      if (is_valid_stack_access (fault_addr, f->esp))
+        {
+          if (grow_stack (upage))
+            return;
+        }
+
+      /* TODO: Check SPT for the page. */
+    }
+
   /* 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 +187,50 @@ page_fault (struct intr_frame *f)
   kill (f);
 }
 
+/* Validates whether the fault address is a valid stack access. Access is a
+   valid stack access under the following two conditions:
+     1. The fault address must be within MAX_STACK_OFFSET (32) bytes below
+      the current stack pointer. (Accounts for both PUSH and PUSHA instructions)
+     2. Growing this stack to this address does not cause it to exceed the
+      MAX_STACK_SIZE (8MB) limit.
+
+   Returns true if both conditions are met, false otherwise.
+
+   Pre: fault_addr is a valid user virtual address (so also not NULL). */
+static bool
+is_valid_stack_access (const void *fault_addr, const void *esp)
+{
+  uint32_t new_stack_size = PHYS_BASE - pg_round_down (fault_addr);
+
+  uint32_t *lowest_valid_push_addr = (uint32_t *)esp - MAX_STACK_OFFSET;
+  bool is_within_push_range = (uint32_t *)fault_addr >= lowest_valid_push_addr;
+
+  return is_within_push_range && new_stack_size <= MAX_STACK_SIZE;
+}
+
+/* Attempts to grow the stack by allocating and mapping a new page.
+  This involves:
+    1. Allocating a zeroed page from the user pool
+    2. Installing it into the page table with write permissions
+
+  Returns true if the stack was successfully grown, false if either
+  allocation or installation fails.
+
+  Pre: upage is a valid page-aligned address (so also not NULL). */
+static bool
+grow_stack (void *upage)
+{
+  /* Allocate new page for stack */
+  void *kpage = palloc_get_page (PAL_USER | PAL_ZERO);
+  if (kpage == NULL)
+    return false;
+
+  /* Install the page into user page table */
+  if (!install_page (upage, kpage, true))
+    {
+      palloc_free_page (kpage);
+      return false;
+    }
+
+  return true;
+}

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,172 @@
 #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"
+#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
-   FILENAME.  The new thread may be scheduled (and may even exit)
+/* Starts a new thread running a user program executed via
+   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);
-  if (fn_copy == NULL)
+  cmd_copy = palloc_get_page (0);
+  if (cmd_copy == NULL)
     return TID_ERROR;
-  strlcpy (fn_copy, file_name, PGSIZE);
 
-  /* Create a new thread to execute FILE_NAME. */
-  tid = thread_create (file_name, PRI_DEFAULT, start_process, fn_copy);
-  if (tid == TID_ERROR)
-    palloc_free_page (fn_copy); 
+  /* Imposing implicit limit that the command line arguments
+    including the user program name fit within a single page. */
+  strlcpy (cmd_copy, cmd, PGSIZE);
+
+  /* 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
-   running. */
+static void *get_usr_kpage (enum palloc_flags flags, void *upage);
+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. */
-  palloc_free_page (file_name);
-  if (!success) 
-    thread_exit ();
+  /* Acquire the file system lock to prevent race conditions. */
+  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 ();
 
   /* Start the user process by simulating a return from an
      interrupt, implemented by intr_exit (in
@@ -76,6 +194,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 +322,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 +362,28 @@ process_exit (void)
   struct thread *cur = thread_current ();
   uint32_t *pd;
 
+  /* Clean up all open files */
+  hash_destroy (&cur->open_files, fd_cleanup);
+
+  /* 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 +402,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 +522,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 ();
@@ -313,13 +622,12 @@ load (const char *file_name, void (**eip) (void), void **esp)
  done:
   /* We arrive here whether the load is successful or not. */
   file_close (file);
+  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
@@ -403,7 +711,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 +719,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; 
         }     
         
@@ -445,19 +753,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);
+#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 +809,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 <syscall-nr.h>
+#include "devices/shutdown.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,256 @@
+#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. */
+      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,20 @@
+#include "page.h"
+
+/* Updates the 'owner' thread's page table entry for virtual address 'upage'
+   to have a present bit of 0 and stores the specified swap slot value in the
+   entry for later retrieval from disk. */
+void
+page_set_swap (struct thread *owner, void *upage, size_t swap_slot)
+{
+
+}
+
+/* Given that the page with user address 'upage' owned by 'owner' is flagged
+   to be in the swap disk via the owner's page table, returns its stored
+   swap slot. Otherwise panics the kernel. */
+size_t
+page_get_swap (struct thread *owner, void *upage)
+{
+
+}
+

src/vm/page.h

@@ -0,0 +1,9 @@
+#ifndef VM_PAGE_H
+#define VM_PAGE_H
+
+#include "threads/thread.h"
+
+void page_set_swap (struct thread *, void *, size_t);
+size_t page_get_swap (struct thread *, void *);
+
+#endif /* vm/frame.h */