[pintos-anon] / solutions / p3.patch

Index: src/Makefile.build
diff -u src/Makefile.build~ src/Makefile.build
--- src/Makefile.build~ 2005-06-18 20:20:47.000000000 -0700
+++ src/Makefile.build 2006-05-16 13:44:56.000000000 -0700
@@ -53,7 +53,9 @@ userprog_SRC += userprog/gdt.c                # GDT in
 userprog_SRC += userprog/tss.c         # TSS management.
 
 # No virtual memory code yet.
-#vm_SRC = vm/filename.c                        # Some file.
+vm_SRC = vm/page.c
+vm_SRC += vm/frame.c
+vm_SRC += vm/swap.c
 
 # Filesystem code.
 filesys_SRC  = filesys/filesys.c       # Filesystem core.
Index: src/devices/timer.c
diff -u src/devices/timer.c~ src/devices/timer.c
--- src/devices/timer.c~ 2005-07-06 13:45:36.000000000 -0700
+++ src/devices/timer.c 2006-05-16 13:44:56.000000000 -0700
@@ -23,6 +23,9 @@ static volatile int64_t ticks;
    Initialized by timer_calibrate(). */
 static unsigned loops_per_tick;
 
+/* Threads waiting in timer_sleep(). */
+static struct list wait_list;
+
 static intr_handler_func timer_interrupt;
 static bool too_many_loops (unsigned loops);
 static void busy_wait (int64_t loops);
@@ -43,6 +46,8 @@ timer_init (void) 
   outb (0x40, count >> 8);
 
   intr_register_ext (0x20, timer_interrupt, "8254 Timer");
+
+  list_init (&wait_list);
 }
 
 /* Calibrates loops_per_tick, used to implement brief delays. */
@@ -87,15 +92,36 @@ timer_elapsed (int64_t then) 
   return timer_ticks () - then;
 }
 
+/* Compares two threads based on their wake-up times. */
+static bool
+compare_threads_by_wakeup_time (const struct list_elem *a_,
+                                const struct list_elem *b_,
+                                void *aux UNUSED) 
+{
+  const struct thread *a = list_entry (a_, struct thread, timer_elem);
+  const struct thread *b = list_entry (b_, struct thread, timer_elem);
+
+  return a->wakeup_time < b->wakeup_time;
+}
+
 /* Suspends execution for approximately TICKS timer ticks. */
 void
 timer_sleep (int64_t ticks) 
 {
-  int64_t start = timer_ticks ();
+  struct thread *t = thread_current ();
+
+  /* Schedule our wake-up time. */
+  t->wakeup_time = timer_ticks () + ticks;
 
+  /* Atomically insert the current thread into the wait list. */
   ASSERT (intr_get_level () == INTR_ON);
-  while (timer_elapsed (start) < ticks) 
-    thread_yield ();
+  intr_disable ();
+  list_insert_ordered (&wait_list, &t->timer_elem,
+                       compare_threads_by_wakeup_time, NULL);
+  intr_enable ();
+
+  /* Wait. */
+  sema_down (&t->timer_sema);
 }
 
 /* Suspends execution for approximately MS milliseconds. */
@@ -132,6 +158,16 @@ timer_interrupt (struct intr_frame *args
 {
   ticks++;
   thread_tick ();
+
+  while (!list_empty (&wait_list))
+    {
+      struct thread *t = list_entry (list_front (&wait_list),
+                                     struct thread, timer_elem);
+      if (ticks < t->wakeup_time) 
+        break;
+      sema_up (&t->timer_sema);
+      list_pop_front (&wait_list);
+    }
 }
 
 /* Returns true if LOOPS iterations waits for more than one timer
Index: src/threads/init.c
diff -u src/threads/init.c~ src/threads/init.c
--- src/threads/init.c~ 2006-04-25 11:35:56.000000000 -0700
+++ src/threads/init.c 2006-05-16 13:44:56.000000000 -0700
@@ -33,6 +33,8 @@
 #include "filesys/filesys.h"
 #include "filesys/fsutil.h"
 #endif
+#include "vm/frame.h"
+#include "vm/swap.h"
 
 /* Amount of physical memory, in 4 kB pages. */
 size_t ram_pages;
@@ -124,6 +126,9 @@ main (void)
   filesys_init (format_filesys);
 #endif
 
+  frame_init ();
+  swap_init ();
+
   printf ("Boot complete.\n");
   
   /* Run actions specified on kernel command line. */
Index: src/threads/interrupt.c
diff -u src/threads/interrupt.c~ src/threads/interrupt.c
--- src/threads/interrupt.c~ 2006-04-25 11:35:56.000000000 -0700
+++ src/threads/interrupt.c 2006-05-16 13:44:56.000000000 -0700
@@ -354,6 +354,8 @@ intr_handler (struct intr_frame *frame) 
       in_external_intr = true;
       yield_on_return = false;
     }
+  else 
+    thread_current ()->user_esp = frame->esp;
 
   /* Invoke the interrupt's handler.
      If there is no handler, invoke the unexpected interrupt
Index: src/threads/thread.c
diff -u src/threads/thread.c~ src/threads/thread.c
--- src/threads/thread.c~ 2006-04-25 11:35:57.000000000 -0700
+++ src/threads/thread.c 2006-05-16 13:44:56.000000000 -0700
@@ -13,6 +13,7 @@
 #include "threads/vaddr.h"
 #ifdef USERPROG
 #include "userprog/process.h"
+#include "userprog/syscall.h"
 #endif
 
 /* Random value for struct thread's `magic' member.
@@ -55,7 +56,8 @@ static void kernel_thread (thread_func *
 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 void init_thread (struct thread *, const char *name, int priority,
+                         tid_t);
 static bool is_thread (struct thread *) UNUSED;
 static void *alloc_frame (struct thread *, size_t size);
 static void schedule (void);
@@ -82,9 +84,8 @@ thread_init (void) 
 
   /* Set up a thread structure for the running thread. */
   initial_thread = running_thread ();
-  init_thread (initial_thread, "main", PRI_DEFAULT);
+  init_thread (initial_thread, "main", PRI_DEFAULT, 0);
   initial_thread->status = THREAD_RUNNING;
-  initial_thread->tid = allocate_tid ();
 }
 
 /* Starts preemptive thread scheduling by enabling interrupts.
@@ -159,8 +160,8 @@ thread_create (const char *name, int pri
     return TID_ERROR;
 
   /* Initialize thread. */
-  init_thread (t, name, priority);
-  tid = t->tid = allocate_tid ();
+  init_thread (t, name, priority, allocate_tid ());
+  tid = t->tid;
 
   /* Stack frame for kernel_thread(). */
   kf = alloc_frame (t, sizeof *kf);
@@ -253,16 +254,19 @@ thread_tid (void) 
 void
 thread_exit (void) 
 {
+  struct thread *t = thread_current ();
+
   ASSERT (!intr_context ());
 
+  syscall_exit ();
 #ifdef USERPROG
   process_exit ();
 #endif
-
+  
   /* Just set our status to dying and schedule another process.
      We will be destroyed during the call to schedule_tail(). */
   intr_disable ();
-  thread_current ()->status = THREAD_DYING;
+  t->status = THREAD_DYING;
   schedule ();
   NOT_REACHED ();
 }
@@ -406,17 +410,28 @@ is_thread (struct thread *t)
 /* 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 priority, tid_t tid)
 {
   ASSERT (t != NULL);
   ASSERT (PRI_MIN <= priority && priority <= PRI_MAX);
   ASSERT (name != NULL);
 
   memset (t, 0, sizeof *t);
+  t->tid = tid;
   t->status = THREAD_BLOCKED;
   strlcpy (t->name, name, sizeof t->name);
   t->stack = (uint8_t *) t + PGSIZE;
   t->priority = priority;
+  t->exit_code = -1;
+  t->wait_status = NULL;
+  list_init (&t->children);
+  sema_init (&t->timer_sema, 0);
+  t->pagedir = NULL;
+  t->pages = NULL;
+  t->bin_file = NULL;
+  list_init (&t->fds);
+  list_init (&t->mappings);
+  t->next_handle = 2;
   t->magic = THREAD_MAGIC;
 }
 
Index: src/threads/thread.h
diff -u src/threads/thread.h~ src/threads/thread.h
--- src/threads/thread.h~ 2006-04-13 13:53:34.000000000 -0700
+++ src/threads/thread.h 2006-05-16 13:44:56.000000000 -0700
@@ -2,8 +2,10 @@
 #define THREADS_THREAD_H
 
 #include <debug.h>
+#include <hash.h>
 #include <list.h>
 #include <stdint.h>
+#include "threads/synch.h"
 
 /* States in a thread's life cycle. */
 enum thread_status
@@ -89,18 +91,49 @@ struct thread
     uint8_t *stack;                     /* Saved stack pointer. */
     int priority;                       /* Priority. */
 
+    /* Owned by process.c. */
+    int exit_code;                      /* Exit code. */
+    struct wait_status *wait_status;    /* This process's completion status. */
+    struct list children;               /* Completion status of children. */
+
     /* Shared between thread.c and synch.c. */
     struct list_elem elem;              /* List element. */
 
-#ifdef USERPROG
+    /* Alarm clock. */
+    int64_t wakeup_time;                /* Time to wake this thread up. */
+    struct list_elem timer_elem;        /* Element in timer_wait_list. */
+    struct semaphore timer_sema;        /* Semaphore. */
+
     /* Owned by userprog/process.c. */
     uint32_t *pagedir;                  /* Page directory. */
-#endif
+    struct hash *pages;                 /* Page table. */
+    struct file *bin_file;              /* The binary executable. */
+
+    /* Owned by syscall.c. */
+    struct list fds;                    /* List of file descriptors. */
+    struct list mappings;               /* Memory-mapped files. */
+    int next_handle;                    /* Next handle value. */
+    void *user_esp;                     /* User's stack pointer. */
 
     /* Owned by thread.c. */
     unsigned magic;                     /* Detects stack overflow. */
   };
 
+/* Tracks the completion of a process.
+   Reference held by both the parent, in its `children' list,
+   and by the child, in its `wait_status' pointer. */
+struct wait_status
+  {
+    struct list_elem elem;              /* `children' list element. */
+    struct lock lock;                   /* Protects ref_cnt. */
+    int ref_cnt;                        /* 2=child and parent both alive,
+                                           1=either child or parent alive,
+                                           0=child and parent both dead. */
+    tid_t tid;                          /* Child thread id. */
+    int exit_code;                      /* Child exit code, if dead. */
+    struct semaphore dead;              /* 1=child alive, 0=child dead. */
+  };
+
 void thread_init (void);
 void thread_start (void);
 
Index: src/userprog/exception.c
diff -u src/userprog/exception.c~ src/userprog/exception.c
--- src/userprog/exception.c~ 2006-01-29 13:32:56.000000000 -0800
+++ src/userprog/exception.c 2006-05-16 13:44:56.000000000 -0700
@@ -4,6 +4,7 @@
 #include "userprog/gdt.h"
 #include "threads/interrupt.h"
 #include "threads/thread.h"
+#include "vm/page.h"
 
 /* Number of page faults processed. */
 static long long page_fault_cnt;
@@ -148,9 +149,14 @@ page_fault (struct intr_frame *f) 
   write = (f->error_code & PF_W) != 0;
   user = (f->error_code & PF_U) != 0;
 
-  /* 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. */
+  /* Allow the pager to try to handle it. */
+  if (user && not_present)
+    {
+      if (!page_in (fault_addr))
+        thread_exit ();
+      return;
+    }
+
   printf ("Page fault at %p: %s error %s page in %s context.\n",
           fault_addr,
           not_present ? "not present" : "rights violation",
Index: src/userprog/pagedir.c
diff -u src/userprog/pagedir.c~ src/userprog/pagedir.c
--- src/userprog/pagedir.c~ 2006-04-25 11:35:58.000000000 -0700
+++ src/userprog/pagedir.c 2006-05-16 13:44:56.000000000 -0700
@@ -35,15 +35,7 @@ pagedir_destroy (uint32_t *pd) 
   ASSERT (pd != base_page_dir);
   for (pde = pd; pde < pd + pd_no (PHYS_BASE); pde++)
     if (*pde & PTE_P) 
-      {
-        uint32_t *pt = pde_get_pt (*pde);
-        uint32_t *pte;
-        
-        for (pte = pt; pte < pt + PGSIZE / sizeof *pte; pte++)
-          if (*pte & PTE_P) 
-            palloc_free_page (pte_get_page (*pte));
-        palloc_free_page (pt);
-      }
+      palloc_free_page (pde_get_pt (*pde));
   palloc_free_page (pd);
 }
 
Index: src/userprog/process.c
diff -u src/userprog/process.c~ src/userprog/process.c
--- src/userprog/process.c~ 2006-04-25 11:35:58.000000000 -0700
+++ src/userprog/process.c 2006-05-16 13:44:56.000000000 -0700
@@ -14,12 +14,26 @@
 #include "threads/flags.h"
 #include "threads/init.h"
 #include "threads/interrupt.h"
+#include "threads/malloc.h"
 #include "threads/palloc.h"
 #include "threads/thread.h"
 #include "threads/vaddr.h"
+#include "vm/page.h"
+#include "vm/frame.h"
 
 static thread_func execute_thread NO_RETURN;
-static bool load (const char *cmdline, void (**eip) (void), void **esp);
+static bool load (const char *cmd_line, void (**eip) (void), void **esp);
+
+/* Data structure shared between process_execute() in the
+   invoking thread and execute_thread() in the newly invoked
+   thread. */
+struct exec_info 
+  {
+    const char *filename;               /* Program to load. */
+    struct semaphore load_done;         /* "Up"ed when loading complete. */
+    struct wait_status *wait_status;    /* Child process. */
+    bool success;                       /* Program successfully loaded? */
+  };
 
 /* Starts a new thread running a user program loaded from
    FILENAME.  The new thread may be scheduled (and may even exit)
@@ -28,29 +42,37 @@ static bool load (const char *cmdline, v
 tid_t
 process_execute (const char *filename) 
 {
-  char *fn_copy;
+  struct exec_info exec;
+  char thread_name[16];
+  char *save_ptr;
   tid_t tid;
 
-  /* Make a copy of FILENAME.
-     Otherwise there's a race between the caller and load(). */
-  fn_copy = palloc_get_page (0);
-  if (fn_copy == NULL)
-    return TID_ERROR;
-  strlcpy (fn_copy, filename, PGSIZE);
+  /* Initialize exec_info. */
+  exec.filename = filename;
+  sema_init (&exec.load_done, 0);
 
   /* Create a new thread to execute FILENAME. */
-  tid = thread_create (filename, PRI_DEFAULT, execute_thread, fn_copy);
-  if (tid == TID_ERROR)
-    palloc_free_page (fn_copy); 
+  strlcpy (thread_name, filename, sizeof thread_name);
+  strtok_r (thread_name, " ", &save_ptr);
+  tid = thread_create (thread_name, PRI_DEFAULT, execute_thread, &exec);
+  if (tid != TID_ERROR)
+    {
+      sema_down (&exec.load_done);
+      if (exec.success)
+        list_push_back (&thread_current ()->children, &exec.wait_status->elem);
+      else 
+        tid = TID_ERROR;
+    }
+
   return tid;
 }
 
 /* A thread function that loads a user process and starts it
    running. */
 static void
-execute_thread (void *filename_)
+execute_thread (void *exec_)
 {
-  char *filename = filename_;
+  struct exec_info *exec = exec_;
   struct intr_frame if_;
   bool success;
 
@@ -59,10 +81,28 @@ execute_thread (void *filename_)
   if_.gs = if_.fs = if_.es = if_.ds = if_.ss = SEL_UDSEG;
   if_.cs = SEL_UCSEG;
   if_.eflags = FLAG_IF | FLAG_MBS;
-  success = load (filename, &if_.eip, &if_.esp);
+  success = load (exec->filename, &if_.eip, &if_.esp);
+
+  /* Allocate wait_status. */
+  if (success)
+    {
+      exec->wait_status = thread_current ()->wait_status
+        = malloc (sizeof *exec->wait_status);
+      success = exec->wait_status != NULL; 
+    }
 
-  /* If load failed, quit. */
-  palloc_free_page (filename);
+  /* Initialize wait_status. */
+  if (success) 
+    {
+      lock_init (&exec->wait_status->lock);
+      exec->wait_status->ref_cnt = 2;
+      exec->wait_status->tid = thread_current ()->tid;
+      sema_init (&exec->wait_status->dead, 0);
+    }
+  
+  /* Notify parent thread and clean up. */
+  exec->success = success;
+  sema_up (&exec->load_done);
   if (!success) 
     thread_exit ();
 
@@ -76,18 +116,47 @@ execute_thread (void *filename_)
   NOT_REACHED ();
 }
 
+/* Releases one reference to CS and, if it is now unreferenced,
+   frees it. */
+static void
+release_child (struct wait_status *cs) 
+{
+  int new_ref_cnt;
+  
+  lock_acquire (&cs->lock);
+  new_ref_cnt = --cs->ref_cnt;
+  lock_release (&cs->lock);
+
+  if (new_ref_cnt == 0)
+    free (cs);
+}
+
 /* 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.  If TID is invalid or if it was not a
    child of the calling process, or if process_wait() has already
    been successfully called for the given TID, returns -1
-   immediately, without waiting.
-
-   This function will be implemented in problem 2-2.  For now, it
-   does nothing. */
+   immediately, without waiting. */
 int
-process_wait (tid_t child_tid UNUSED) 
+process_wait (tid_t child_tid) 
 {
+  struct thread *cur = thread_current ();
+  struct list_elem *e;
+
+  for (e = list_begin (&cur->children); e != list_end (&cur->children);
+       e = list_next (e)) 
+    {
+      struct wait_status *cs = list_entry (e, struct wait_status, elem);
+      if (cs->tid == child_tid) 
+        {
+          int exit_code;
+          list_remove (e);
+          sema_down (&cs->dead);
+          exit_code = cs->exit_code;
+          release_child (cs);
+          return exit_code;
+        }
+    }
   return -1;
 }
 
@@ -96,8 +165,35 @@ void
 process_exit (void)
 {
   struct thread *cur = thread_current ();
+  struct list_elem *e, *next;
   uint32_t *pd;
 
+  printf ("%s: exit(%d)\n", cur->name, cur->exit_code);
+
+  /* Notify parent that we're dead. */
+  if (cur->wait_status != NULL) 
+    {
+      struct wait_status *cs = cur->wait_status;
+      cs->exit_code = cur->exit_code;
+      sema_up (&cs->dead);
+      release_child (cs);
+    }
+
+  /* Free entries of children list. */
+  for (e = list_begin (&cur->children); e != list_end (&cur->children);
+       e = next) 
+    {
+      struct wait_status *cs = list_entry (e, struct wait_status, elem);
+      next = list_remove (e);
+      release_child (cs);
+    }
+
+  /* Destroy the page hash table. */
+  page_exit ();
+  
+  /* Close executable (and allow writes). */
+  file_close (cur->bin_file);
+
   /* Destroy the current process's page directory and switch back
      to the kernel-only page directory. */
   pd = cur->pagedir;
@@ -194,7 +290,7 @@ struct Elf32_Phdr
 #define PF_W 2          /* Writable. */
 #define PF_R 4          /* Readable. */
 
-static bool setup_stack (void **esp);
+static bool setup_stack (const char *cmd_line, void **esp);
 static bool validate_segment (const struct Elf32_Phdr *, struct file *);
 static bool load_segment (struct file *file, off_t ofs, uint8_t *upage,
                           uint32_t read_bytes, uint32_t zero_bytes,
@@ -205,13 +301,15 @@ static bool load_segment (struct file *f
    and its initial stack pointer into *ESP.
    Returns true if successful, false otherwise. */
 bool
-load (const char *filename, void (**eip) (void), void **esp) 
+load (const char *cmd_line, void (**eip) (void), void **esp) 
 {
   struct thread *t = thread_current ();
+  char filename[NAME_MAX + 2];
   struct Elf32_Ehdr ehdr;
   struct file *file = NULL;
   off_t file_ofs;
   bool success = false;
+  char *cp;
   int i;
 
   /* Allocate and activate page directory. */
@@ -220,13 +318,28 @@ load (const char *filename, void (**eip)
     goto done;
   process_activate ();
 
+  /* Create page hash table. */
+  t->pages = malloc (sizeof *t->pages);
+  if (t->pages == NULL)
+    goto done;
+  hash_init (t->pages, page_hash, page_less, NULL);
+
+  /* Extract filename from command line. */
+  while (*cmd_line == ' ')
+    cmd_line++;
+  strlcpy (filename, cmd_line, sizeof filename);
+  cp = strchr (filename, ' ');
+  if (cp != NULL)
+    *cp = '\0';
+
   /* Open executable file. */
-  file = filesys_open (filename);
+  t->bin_file = file = filesys_open (filename);
   if (file == NULL) 
     {
       printf ("load: %s: open failed\n", filename);
       goto done; 
     }
+  file_deny_write (t->bin_file);
 
   /* Read and verify executable header. */
   if (file_read (file, &ehdr, sizeof ehdr) != sizeof ehdr
@@ -301,7 +414,7 @@ load (const char *filename, void (**eip)
     }
 
   /* Set up stack. */
-  if (!setup_stack (esp))
+  if (!setup_stack (cmd_line, esp))
     goto done;
 
   /* Start address. */
@@ -311,14 +424,11 @@ load (const char *filename, void (**eip)
 
  done:
   /* We arrive here whether the load is successful or not. */
-  file_close (file);
   return success;
 }
 \f
 /* load() helpers. */
 
-static bool install_page (void *upage, void *kpage, bool writable);
-
 /* Checks whether PHDR describes a valid, loadable segment in
    FILE and returns true if so, false otherwise. */
 static bool
@@ -387,79 +497,127 @@ load_segment (struct file *file, off_t o
   ASSERT (pg_ofs (upage) == 0);
   ASSERT (ofs % PGSIZE == 0);
 
-  file_seek (file, ofs);
   while (read_bytes > 0 || zero_bytes > 0) 
     {
-      /* Calculate how to fill this page.
-         We will read PAGE_READ_BYTES bytes from FILE
-         and zero the final PAGE_ZERO_BYTES bytes. */
       size_t page_read_bytes = read_bytes < PGSIZE ? read_bytes : PGSIZE;
       size_t page_zero_bytes = PGSIZE - page_read_bytes;
-
-      /* Get a page of memory. */
-      uint8_t *kpage = palloc_get_page (PAL_USER);
-      if (kpage == NULL)
+      struct page *p = page_allocate (upage, !writable);
+      if (p == NULL)
         return false;
-
-      /* Load this page. */
-      if (file_read (file, kpage, page_read_bytes) != (int) page_read_bytes)
-        {
-          palloc_free_page (kpage);
-          return false; 
-        }
-      memset (kpage + page_read_bytes, 0, page_zero_bytes);
-
-      /* Add the page to the process's address space. */
-      if (!install_page (upage, kpage, writable)) 
+      if (page_read_bytes > 0) 
         {
-          palloc_free_page (kpage);
-          return false; 
+          p->file = file;
+          p->file_offset = ofs;
+          p->file_bytes = page_read_bytes;
         }
-
-      /* Advance. */
       read_bytes -= page_read_bytes;
       zero_bytes -= page_zero_bytes;
+      ofs += page_read_bytes;
       upage += PGSIZE;
     }
   return true;
 }
 
-/* Create a minimal stack by mapping a zeroed page at the top of
-   user virtual memory. */
+/* Reverse the order of the ARGC pointers to char in ARGV. */
+static void
+reverse (int argc, char **argv) 
+{
+  for (; argc > 1; argc -= 2, argv++) 
+    {
+      char *tmp = argv[0];
+      argv[0] = argv[argc - 1];
+      argv[argc - 1] = tmp;
+    }
+}
+ 
+/* Pushes the SIZE bytes in BUF onto the stack in KPAGE, whose
+   page-relative stack pointer is *OFS, and then adjusts *OFS
+   appropriately.  The bytes pushed are rounded to a 32-bit
+   boundary.
+
+   If successful, returns a pointer to the newly pushed object.
+   On failure, returns a null pointer. */
+static void *
+push (uint8_t *kpage, size_t *ofs, const void *buf, size_t size) 
+{
+  size_t padsize = ROUND_UP (size, sizeof (uint32_t));
+  if (*ofs < padsize)
+    return NULL;
+
+  *ofs -= padsize;
+  memcpy (kpage + *ofs + (padsize - size), buf, size);
+  return kpage + *ofs + (padsize - size);
+}
+
+/* Sets up command line arguments in KPAGE, which will be mapped
+   to UPAGE in user space.  The command line arguments are taken
+   from CMD_LINE, separated by spaces.  Sets *ESP to the initial
+   stack pointer for the process. */
 static bool
-setup_stack (void **esp) 
+init_cmd_line (uint8_t *kpage, uint8_t *upage, const char *cmd_line,
+               void **esp) 
 {
-  uint8_t *kpage;
-  bool success = false;
+  size_t ofs = PGSIZE;
+  char *const null = NULL;
+  char *cmd_line_copy;
+  char *karg, *saveptr;
+  int argc;
+  char **argv;
+
+  /* Push command line string. */
+  cmd_line_copy = push (kpage, &ofs, cmd_line, strlen (cmd_line) + 1);
+  if (cmd_line_copy == NULL)
+    return false;
+
+  if (push (kpage, &ofs, &null, sizeof null) == NULL)
+    return false;
 
-  kpage = palloc_get_page (PAL_USER | PAL_ZERO);
-  if (kpage != NULL) 
+  /* Parse command line into arguments
+     and push them in reverse order. */
+  argc = 0;
+  for (karg = strtok_r (cmd_line_copy, " ", &saveptr); karg != NULL;
+       karg = strtok_r (NULL, " ", &saveptr))
     {
-      success = install_page (((uint8_t *) PHYS_BASE) - PGSIZE, kpage, true);
-      if (success)
-        *esp = PHYS_BASE;
-      else
-        palloc_free_page (kpage);
+      void *uarg = upage + (karg - (char *) kpage);
+      if (push (kpage, &ofs, &uarg, sizeof uarg) == NULL)
+        return false;
+      argc++;
     }
-  return success;
+
+  /* Reverse the order of the command line arguments. */
+  argv = (char **) (upage + ofs);
+  reverse (argc, (char **) (kpage + ofs));
+
+  /* Push argv, argc, "return address". */
+  if (push (kpage, &ofs, &argv, sizeof argv) == NULL
+      || push (kpage, &ofs, &argc, sizeof argc) == NULL
+      || push (kpage, &ofs, &null, sizeof null) == NULL)
+    return false;
+
+  /* Set initial stack pointer. */
+  *esp = upage + ofs;
+  return true;
 }
 
-/* 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;
-   otherwise, it is read-only.
-   UPAGE must not already be mapped.
-   KPAGE should probably be a page obtained from the user pool
-   with palloc_get_page().
-   Returns true on success, false if UPAGE is already mapped or
-   if memory allocation fails. */
+/* Create a minimal stack for T by mapping a page at the
+   top of user virtual memory.  Fills in the page using CMD_LINE
+   and sets *ESP to the stack pointer. */
 static bool
-install_page (void *upage, void *kpage, bool writable)
+setup_stack (const char *cmd_line, void **esp) 
 {
-  struct thread *t = thread_current ();
-
-  /* Verify that there's not already a page at that virtual
-     address, then map our page there. */
-  return (pagedir_get_page (t->pagedir, upage) == NULL
-          && pagedir_set_page (t->pagedir, upage, kpage, writable));
+  struct page *page = page_allocate (((uint8_t *) PHYS_BASE) - PGSIZE, false);
+  if (page != NULL) 
+    {
+      page->frame = frame_alloc_and_lock (page);
+      if (page->frame != NULL)
+        {
+          bool ok;
+          page->read_only = false;
+          page->private = false;
+          ok = init_cmd_line (page->frame->base, page->addr, cmd_line, esp);
+          frame_unlock (page->frame);
+          return ok;
+        }
+    }
+  return false;
 }
Index: src/userprog/syscall.c
diff -u src/userprog/syscall.c~ src/userprog/syscall.c
--- src/userprog/syscall.c~ 2005-06-18 20:21:21.000000000 -0700
+++ src/userprog/syscall.c 2006-05-16 14:17:02.000000000 -0700
@@ -1,20 +1,598 @@
 #include "userprog/syscall.h"
 #include <stdio.h>
+#include <string.h>
 #include <syscall-nr.h>
+#include "userprog/process.h"
+#include "userprog/pagedir.h"
+#include "devices/kbd.h"
+#include "filesys/directory.h"
+#include "filesys/filesys.h"
+#include "filesys/file.h"
+#include "threads/init.h"
 #include "threads/interrupt.h"
+#include "threads/malloc.h"
+#include "threads/palloc.h"
 #include "threads/thread.h"
-
+#include "threads/vaddr.h"
+#include "vm/page.h"
+ 
+ 
+static int sys_halt (void);
+static int sys_exit (int status);
+static int sys_exec (const char *ufile);
+static int sys_wait (tid_t);
+static int sys_create (const char *ufile, unsigned initial_size);
+static int sys_remove (const char *ufile);
+static int sys_open (const char *ufile);
+static int sys_filesize (int handle);
+static int sys_read (int handle, void *udst_, unsigned size);
+static int sys_write (int handle, void *usrc_, unsigned size);
+static int sys_seek (int handle, unsigned position);
+static int sys_tell (int handle);
+static int sys_close (int handle);
+static int sys_mmap (int handle, void *addr);
+static int sys_munmap (int mapping);
+ 
 static void syscall_handler (struct intr_frame *);
+static void copy_in (void *, const void *, size_t);
 
+static struct lock fs_lock;
+ 
 void
 syscall_init (void) 
 {
   intr_register_int (0x30, 3, INTR_ON, syscall_handler, "syscall");
+  lock_init (&fs_lock);
 }
+ 
+/* System call handler. */
+static void
+syscall_handler (struct intr_frame *f) 
+{
+  typedef int syscall_function (int, int, int);
+
+  /* A system call. */
+  struct syscall 
+    {
+      size_t arg_cnt;           /* Number of arguments. */
+      syscall_function *func;   /* Implementation. */
+    };
+
+  /* Table of system calls. */
+  static const struct syscall syscall_table[] =
+    {
+      {0, (syscall_function *) sys_halt},
+      {1, (syscall_function *) sys_exit},
+      {1, (syscall_function *) sys_exec},
+      {1, (syscall_function *) sys_wait},
+      {2, (syscall_function *) sys_create},
+      {1, (syscall_function *) sys_remove},
+      {1, (syscall_function *) sys_open},
+      {1, (syscall_function *) sys_filesize},
+      {3, (syscall_function *) sys_read},
+      {3, (syscall_function *) sys_write},
+      {2, (syscall_function *) sys_seek},
+      {1, (syscall_function *) sys_tell},
+      {1, (syscall_function *) sys_close},
+      {2, (syscall_function *) sys_mmap},
+      {1, (syscall_function *) sys_munmap},
+    };
+
+  const struct syscall *sc;
+  unsigned call_nr;
+  int args[3];
 
+  /* Get the system call. */
+  copy_in (&call_nr, f->esp, sizeof call_nr);
+  if (call_nr >= sizeof syscall_table / sizeof *syscall_table)
+    thread_exit ();
+  sc = syscall_table + call_nr;
+
+  /* Get the system call arguments. */
+  ASSERT (sc->arg_cnt <= sizeof args / sizeof *args);
+  memset (args, 0, sizeof args);
+  copy_in (args, (uint32_t *) f->esp + 1, sizeof *args * sc->arg_cnt);
+
+  /* Execute the system call,
+     and set the return value. */
+  f->eax = sc->func (args[0], args[1], args[2]);
+}
+ 
+/* Copies SIZE bytes from user address USRC to kernel address
+   DST.
+   Call thread_exit() if any of the user accesses are invalid. */
 static void
-syscall_handler (struct intr_frame *f UNUSED) 
+copy_in (void *dst_, const void *usrc_, size_t size) 
+{
+  uint8_t *dst = dst_;
+  const uint8_t *usrc = usrc_;
+
+  while (size > 0) 
+    {
+      size_t chunk_size = PGSIZE - pg_ofs (usrc);
+      if (chunk_size > size)
+        chunk_size = size;
+      
+      if (!page_lock (usrc, false))
+        thread_exit ();
+      memcpy (dst, usrc, chunk_size);
+      page_unlock (usrc);
+
+      dst += chunk_size;
+      usrc += chunk_size;
+      size -= chunk_size;
+    }
+}
+ 
+/* Creates a copy of user string US in kernel memory
+   and returns it as a page that must be freed with
+   palloc_free_page().
+   Truncates the string at PGSIZE bytes in size.
+   Call thread_exit() if any of the user accesses are invalid. */
+static char *
+copy_in_string (const char *us) 
+{
+  char *ks;
+  char *upage;
+  size_t length;
+ 
+  ks = palloc_get_page (0);
+  if (ks == NULL) 
+    thread_exit ();
+
+  length = 0;
+  for (;;) 
+    {
+      upage = pg_round_down (us);
+      if (!page_lock (upage, false))
+        goto lock_error;
+
+      for (; us < upage + PGSIZE; us++) 
+        {
+          ks[length++] = *us;
+          if (*us == '\0') 
+            {
+              page_unlock (upage);
+              return ks; 
+            }
+          else if (length >= PGSIZE) 
+            goto too_long_error;
+        }
+
+      page_unlock (upage);
+    }
+
+ too_long_error:
+  page_unlock (upage);
+ lock_error:
+  palloc_free_page (ks);
+  thread_exit ();
+}
+ 
+/* Halt system call. */
+static int
+sys_halt (void)
+{
+  power_off ();
+}
+ 
+/* Exit system call. */
+static int
+sys_exit (int exit_code) 
+{
+  thread_current ()->exit_code = exit_code;
+  thread_exit ();
+  NOT_REACHED ();
+}
+ 
+/* Exec system call. */
+static int
+sys_exec (const char *ufile) 
+{
+  tid_t tid;
+  char *kfile = copy_in_string (ufile);
+
+  lock_acquire (&fs_lock);
+  tid = process_execute (kfile);
+  lock_release (&fs_lock);
+ 
+  palloc_free_page (kfile);
+ 
+  return tid;
+}
+ 
+/* Wait system call. */
+static int
+sys_wait (tid_t child) 
+{
+  return process_wait (child);
+}
+ 
+/* Create system call. */
+static int
+sys_create (const char *ufile, unsigned initial_size) 
+{
+  char *kfile = copy_in_string (ufile);
+  bool ok;
+
+  lock_acquire (&fs_lock);
+  ok = filesys_create (kfile, initial_size);
+  lock_release (&fs_lock);
+
+  palloc_free_page (kfile);
+ 
+  return ok;
+}
+ 
+/* Remove system call. */
+static int
+sys_remove (const char *ufile) 
+{
+  char *kfile = copy_in_string (ufile);
+  bool ok;
+
+  lock_acquire (&fs_lock);
+  ok = filesys_remove (kfile);
+  lock_release (&fs_lock);
+
+  palloc_free_page (kfile);
+ 
+  return ok;
+}
+\f
+/* A file descriptor, for binding a file handle to a file. */
+struct file_descriptor
+  {
+    struct list_elem elem;      /* List element. */
+    struct file *file;          /* File. */
+    int handle;                 /* File handle. */
+  };
+ 
+/* Open system call. */
+static int
+sys_open (const char *ufile) 
+{
+  char *kfile = copy_in_string (ufile);
+  struct file_descriptor *fd;
+  int handle = -1;
+ 
+  fd = malloc (sizeof *fd);
+  if (fd != NULL)
+    {
+      lock_acquire (&fs_lock);
+      fd->file = filesys_open (kfile);
+      if (fd->file != NULL)
+        {
+          struct thread *cur = thread_current ();
+          handle = fd->handle = cur->next_handle++;
+          list_push_front (&cur->fds, &fd->elem);
+        }
+      else 
+        free (fd);
+      lock_release (&fs_lock);
+    }
+  
+  palloc_free_page (kfile);
+  return handle;
+}
+ 
+/* Returns the file descriptor associated with the given handle.
+   Terminates the process if HANDLE is not associated with an
+   open file. */
+static struct file_descriptor *
+lookup_fd (int handle) 
+{
+  struct thread *cur = thread_current ();
+  struct list_elem *e;
+   
+  for (e = list_begin (&cur->fds); e != list_end (&cur->fds);
+       e = list_next (e))
+    {
+      struct file_descriptor *fd;
+      fd = list_entry (e, struct file_descriptor, elem);
+      if (fd->handle == handle)
+        return fd;
+    }
+ 
+  thread_exit ();
+}
+ 
+/* Filesize system call. */
+static int
+sys_filesize (int handle) 
+{
+  struct file_descriptor *fd = lookup_fd (handle);
+  int size;
+ 
+  lock_acquire (&fs_lock);
+  size = file_length (fd->file);
+  lock_release (&fs_lock);
+ 
+  return size;
+}
+ 
+/* Read system call. */
+static int
+sys_read (int handle, void *udst_, unsigned size) 
 {
-  printf ("system call!\n");
+  uint8_t *udst = udst_;
+  struct file_descriptor *fd;
+  int bytes_read = 0;
+
+  fd = lookup_fd (handle);
+  while (size > 0) 
+    {
+      /* How much to read into this page? */
+      size_t page_left = PGSIZE - pg_ofs (udst);
+      size_t read_amt = size < page_left ? size : page_left;
+      off_t retval;
+
+      /* Read from file into page. */
+      if (handle != STDIN_FILENO) 
+        {
+          if (!page_lock (udst, true)) 
+            thread_exit (); 
+          lock_acquire (&fs_lock);
+          retval = file_read (fd->file, udst, read_amt);
+          lock_release (&fs_lock);
+          page_unlock (udst);
+        }
+      else 
+        {
+          size_t i;
+          
+          for (i = 0; i < read_amt; i++) 
+            {
+              char c = kbd_getc ();
+              if (!page_lock (udst, true)) 
+                thread_exit ();
+              udst[i] = c;
+              page_unlock (udst);
+            }
+          bytes_read = read_amt;
+        }
+      
+      /* Check success. */
+      if (retval < 0)
+        {
+          if (bytes_read == 0)
+            bytes_read = -1; 
+          break;
+        }
+      bytes_read += retval; 
+      if (retval != (off_t) read_amt) 
+        {
+          /* Short read, so we're done. */
+          break; 
+        }
+
+      /* Advance. */
+      udst += retval;
+      size -= retval;
+    }
+   
+  return bytes_read;
+}
+ 
+/* Write system call. */
+static int
+sys_write (int handle, void *usrc_, unsigned size) 
+{
+  uint8_t *usrc = usrc_;
+  struct file_descriptor *fd = NULL;
+  int bytes_written = 0;
+
+  /* Lookup up file descriptor. */
+  if (handle != STDOUT_FILENO)
+    fd = lookup_fd (handle);
+
+  while (size > 0) 
+    {
+      /* How much bytes to write to this page? */
+      size_t page_left = PGSIZE - pg_ofs (usrc);
+      size_t write_amt = size < page_left ? size : page_left;
+      off_t retval;
+
+      /* Write from page into file. */
+      if (!page_lock (usrc, false)) 
+        thread_exit ();
+      lock_acquire (&fs_lock);
+      if (handle == STDOUT_FILENO)
+        {
+          putbuf ((char *) usrc, write_amt);
+          retval = write_amt;
+        }
+      else
+        retval = file_write (fd->file, usrc, write_amt);
+      lock_release (&fs_lock);
+      page_unlock (usrc);
+
+      /* Handle return value. */
+      if (retval < 0) 
+        {
+          if (bytes_written == 0)
+            bytes_written = -1;
+          break;
+        }
+      bytes_written += retval;
+
+      /* If it was a short write we're done. */
+      if (retval != (off_t) write_amt)
+        break;
+
+      /* Advance. */
+      usrc += retval;
+      size -= retval;
+    }
+ 
+  return bytes_written;
+}
+ 
+/* Seek system call. */
+static int
+sys_seek (int handle, unsigned position) 
+{
+  struct file_descriptor *fd = lookup_fd (handle);
+   
+  lock_acquire (&fs_lock);
+  if ((off_t) position >= 0)
+    file_seek (fd->file, position);
+  lock_release (&fs_lock);
+
+  return 0;
+}
+ 
+/* Tell system call. */
+static int
+sys_tell (int handle) 
+{
+  struct file_descriptor *fd = lookup_fd (handle);
+  unsigned position;
+   
+  lock_acquire (&fs_lock);
+  position = file_tell (fd->file);
+  lock_release (&fs_lock);
+
+  return position;
+}
+ 
+/* Close system call. */
+static int
+sys_close (int handle) 
+{
+  struct file_descriptor *fd = lookup_fd (handle);
+  lock_acquire (&fs_lock);
+  file_close (fd->file);
+  lock_release (&fs_lock);
+  list_remove (&fd->elem);
+  free (fd);
+  return 0;
+}
+\f
+/* Binds a mapping id to a region of memory and a file. */
+struct mapping
+  {
+    struct list_elem elem;      /* List element. */
+    int handle;                 /* Mapping id. */
+    struct file *file;          /* File. */
+    uint8_t *base;              /* Start of memory mapping. */
+    size_t page_cnt;            /* Number of pages mapped. */
+  };
+
+/* Returns the file descriptor associated with the given handle.
+   Terminates the process if HANDLE is not associated with a
+   memory mapping. */
+static struct mapping *
+lookup_mapping (int handle) 
+{
+  struct thread *cur = thread_current ();
+  struct list_elem *e;
+   
+  for (e = list_begin (&cur->mappings); e != list_end (&cur->mappings);
+       e = list_next (e))
+    {
+      struct mapping *m = list_entry (e, struct mapping, elem);
+      if (m->handle == handle)
+        return m;
+    }
+ 
   thread_exit ();
 }
+
+/* Remove mapping M from the virtual address space,
+   writing back any pages that have changed. */
+static void
+unmap (struct mapping *m) 
+{
+  list_remove (&m->elem);
+  while (m->page_cnt-- > 0) 
+    {
+      page_deallocate (m->base);
+      m->base += PGSIZE;
+    }
+  file_close (m->file);
+  free (m);
+}
+ 
+/* Mmap system call. */
+static int
+sys_mmap (int handle, void *addr)
+{
+  struct file_descriptor *fd = lookup_fd (handle);
+  struct mapping *m = malloc (sizeof *m);
+  size_t offset;
+  off_t length;
+
+  if (m == NULL || addr == NULL || pg_ofs (addr) != 0)
+    return -1;
+
+  m->handle = thread_current ()->next_handle++;
+  lock_acquire (&fs_lock);
+  m->file = file_reopen (fd->file);
+  lock_release (&fs_lock);
+  if (m->file == NULL) 
+    {
+      free (m);
+      return -1;
+    }
+  m->base = addr;
+  m->page_cnt = 0;
+  list_push_front (&thread_current ()->mappings, &m->elem);
+
+  offset = 0;
+  lock_acquire (&fs_lock);
+  length = file_length (m->file);
+  lock_release (&fs_lock);
+  while (length > 0)
+    {
+      struct page *p = page_allocate ((uint8_t *) addr + offset, false);
+      if (p == NULL)
+        {
+          unmap (m);
+          return -1;
+        }
+      p->private = false;
+      p->file = m->file;
+      p->file_offset = offset;
+      p->file_bytes = length >= PGSIZE ? PGSIZE : length;
+      offset += p->file_bytes;
+      length -= p->file_bytes;
+      m->page_cnt++;
+    }
+  
+  return m->handle;
+}
+
+/* Munmap system call. */
+static int
+sys_munmap (int mapping) 
+{
+  unmap (lookup_mapping (mapping));
+  return 0;
+}
+\f 
+/* On thread exit, close all open files and unmap all mappings. */
+void
+syscall_exit (void) 
+{
+  struct thread *cur = thread_current ();
+  struct list_elem *e, *next;
+   
+  for (e = list_begin (&cur->fds); e != list_end (&cur->fds); e = next)
+    {
+      struct file_descriptor *fd = list_entry (e, struct file_descriptor, elem);
+      next = list_next (e);
+      lock_acquire (&fs_lock);
+      file_close (fd->file);
+      lock_release (&fs_lock);
+      free (fd);
+    }
+   
+  for (e = list_begin (&cur->mappings); e != list_end (&cur->mappings);
+       e = next)
+    {
+      struct mapping *m = list_entry (e, struct mapping, elem);
+      next = list_next (e);
+      unmap (m);
+    }
+}
Index: src/userprog/syscall.h
diff -u src/userprog/syscall.h~ src/userprog/syscall.h
--- src/userprog/syscall.h~ 2004-09-05 22:38:45.000000000 -0700
+++ src/userprog/syscall.h 2006-05-16 13:44:56.000000000 -0700
@@ -2,5 +2,6 @@
 #define USERPROG_SYSCALL_H
 
 void syscall_init (void);
+void syscall_exit (void);
 
 #endif /* userprog/syscall.h */
Index: src/vm/frame.c
diff -u src/vm/frame.c~ src/vm/frame.c
--- src/vm/frame.c~ 1969-12-31 16:00:00.000000000 -0800
+++ src/vm/frame.c 2006-05-16 13:44:56.000000000 -0700
@@ -0,0 +1,162 @@
+#include "vm/frame.h"
+#include <stdio.h>
+#include "vm/page.h"
+#include "devices/timer.h"
+#include "threads/init.h"
+#include "threads/malloc.h"
+#include "threads/palloc.h"
+#include "threads/synch.h"
+#include "threads/vaddr.h"
+
+static struct frame *frames;
+static size_t frame_cnt;
+
+static struct lock scan_lock;
+static size_t hand;
+
+/* Initialize the frame manager. */
+void
+frame_init (void) 
+{
+  void *base;
+
+  lock_init (&scan_lock);
+  
+  frames = malloc (sizeof *frames * ram_pages);
+  if (frames == NULL)
+    PANIC ("out of memory allocating page frames");
+
+  while ((base = palloc_get_page (PAL_USER)) != NULL) 
+    {
+      struct frame *f = &frames[frame_cnt++];
+      lock_init (&f->lock);
+      f->base = base;
+      f->page = NULL;
+    }
+}
+
+/* Tries to allocate and lock a frame for PAGE.
+   Returns the frame if successful, false on failure. */
+static struct frame *
+try_frame_alloc_and_lock (struct page *page) 
+{
+  size_t i;
+
+  lock_acquire (&scan_lock);
+
+  /* Find a free frame. */
+  for (i = 0; i < frame_cnt; i++)
+    {
+      struct frame *f = &frames[i];
+      if (!lock_try_acquire (&f->lock))
+        continue;
+      if (f->page == NULL) 
+        {
+          f->page = page;
+          lock_release (&scan_lock);
+          return f;
+        } 
+      lock_release (&f->lock);
+    }
+
+  /* No free frame.  Find a frame to evict. */
+  for (i = 0; i < frame_cnt * 2; i++) 
+    {
+      /* Get a frame. */
+      struct frame *f = &frames[hand];
+      if (++hand >= frame_cnt)
+        hand = 0;
+
+      if (!lock_try_acquire (&f->lock))
+        continue;
+
+      if (f->page == NULL) 
+        {
+          f->page = page;
+          lock_release (&scan_lock);
+          return f;
+        } 
+
+      if (page_accessed_recently (f->page)) 
+        {
+          lock_release (&f->lock);
+          continue;
+        }
+          
+      lock_release (&scan_lock);
+      
+      /* Evict this frame. */
+      if (!page_out (f->page))
+        {
+          lock_release (&f->lock);
+          return NULL;
+        }
+
+      f->page = page;
+      return f;
+    }
+
+  lock_release (&scan_lock);
+  return NULL;
+}
+
+
+/* Tries really hard to allocate and lock a frame for PAGE.
+   Returns the frame if successful, false on failure. */
+struct frame *
+frame_alloc_and_lock (struct page *page) 
+{
+  size_t try;
+
+  for (try = 0; try < 3; try++) 
+    {
+      struct frame *f = try_frame_alloc_and_lock (page);
+      if (f != NULL) 
+        {
+          ASSERT (lock_held_by_current_thread (&f->lock));
+          return f; 
+        }
+      timer_msleep (1000);
+    }
+
+  return NULL;
+}
+
+/* Locks P's frame into memory, if it has one.
+   Upon return, p->frame will not change until P is unlocked. */
+void
+frame_lock (struct page *p) 
+{
+  /* A frame can be asynchronously removed, but never inserted. */
+  struct frame *f = p->frame;
+  if (f != NULL) 
+    {
+      lock_acquire (&f->lock);
+      if (f != p->frame)
+        {
+          lock_release (&f->lock);
+          ASSERT (p->frame == NULL); 
+        } 
+    }
+}
+
+/* Releases frame F for use by another page.
+   F must be locked for use by the current process.
+   Any data in F is lost. */
+void
+frame_free (struct frame *f)
+{
+  ASSERT (lock_held_by_current_thread (&f->lock));
+          
+  f->page = NULL;
+  lock_release (&f->lock);
+}
+
+/* Unlocks frame F, allowing it to be evicted.
+   F must be locked for use by the current process. */
+void
+frame_unlock (struct frame *f) 
+{
+  ASSERT (lock_held_by_current_thread (&f->lock));
+  lock_release (&f->lock);
+}
Index: src/vm/frame.h
diff -u src/vm/frame.h~ src/vm/frame.h
--- src/vm/frame.h~ 1969-12-31 16:00:00.000000000 -0800
+++ src/vm/frame.h 2006-05-16 13:44:56.000000000 -0700
@@ -0,0 +1,23 @@
+#ifndef VM_FRAME_H
+#define VM_FRAME_H
+
+#include <stdbool.h>
+#include "threads/synch.h"
+
+/* A physical frame. */
+struct frame 
+  {
+    struct lock lock;           /* Prevent simultaneous access. */
+    void *base;                 /* Kernel virtual base address. */
+    struct page *page;          /* Mapped process page, if any. */
+  };
+
+void frame_init (void);
+
+struct frame *frame_alloc_and_lock (struct page *);
+void frame_lock (struct page *);
+
+void frame_free (struct frame *);
+void frame_unlock (struct frame *);
+
+#endif /* vm/frame.h */
Index: src/vm/page.c
diff -u src/vm/page.c~ src/vm/page.c
--- src/vm/page.c~ 1969-12-31 16:00:00.000000000 -0800
+++ src/vm/page.c 2006-05-16 13:44:56.000000000 -0700
@@ -0,0 +1,293 @@
+#include "vm/page.h"
+#include <stdio.h>
+#include <string.h>
+#include "vm/frame.h"
+#include "vm/swap.h"
+#include "filesys/file.h"
+#include "threads/malloc.h"
+#include "threads/thread.h"
+#include "userprog/pagedir.h"
+#include "threads/vaddr.h"
+
+/* Maximum size of process stack, in bytes. */
+#define STACK_MAX (1024 * 1024)
+
+/* Destroys a page, which must be in the current process's
+   page table.  Used as a callback for hash_destroy(). */
+static void
+destroy_page (struct hash_elem *p_, void *aux UNUSED)
+{
+  struct page *p = hash_entry (p_, struct page, hash_elem);
+  frame_lock (p);
+  if (p->frame)
+    frame_free (p->frame);
+  free (p);
+}
+
+/* Destroys the current process's page table. */
+void
+page_exit (void) 
+{
+  struct hash *h = thread_current ()->pages;
+  if (h != NULL)
+    hash_destroy (h, destroy_page);
+}
+
+/* Returns the page containing the given virtual ADDRESS,
+   or a null pointer if no such page exists.
+   Allocates stack pages as necessary. */
+static struct page *
+page_for_addr (const void *address) 
+{
+  if (address < PHYS_BASE) 
+    {
+      struct page p;
+      struct hash_elem *e;
+
+      /* Find existing page. */
+      p.addr = (void *) pg_round_down (address);
+      e = hash_find (thread_current ()->pages, &p.hash_elem);
+      if (e != NULL)
+        return hash_entry (e, struct page, hash_elem);
+
+      /* No page.  Expand stack? */
+      if (address >= PHYS_BASE - STACK_MAX
+          && address >= thread_current ()->user_esp - 32)
+        return page_allocate ((void *) address, false);
+    }
+  return NULL;
+}
+
+/* Locks a frame for page P and pages it in.
+   Returns true if successful, false on failure. */
+static bool
+do_page_in (struct page *p)
+{
+  /* Get a frame for the page. */
+  p->frame = frame_alloc_and_lock (p);
+  if (p->frame == NULL)
+    return false;
+
+  /* Copy data into the frame. */
+  if (p->sector != (disk_sector_t) -1) 
+    {
+      /* Get data from swap. */
+      swap_in (p); 
+    }
+  else if (p->file != NULL) 
+    {
+      /* Get data from file. */
+      off_t read_bytes = file_read_at (p->file, p->frame->base,
+                                        p->file_bytes, p->file_offset);
+      off_t zero_bytes = PGSIZE - read_bytes;
+      memset (p->frame->base + read_bytes, 0, zero_bytes);
+      if (read_bytes != p->file_bytes)
+        printf ("bytes read (%"PROTd") != bytes requested (%"PROTd")\n",
+                read_bytes, p->file_bytes);
+    }
+  else 
+    {
+      /* Provide all-zero page. */
+      memset (p->frame->base, 0, PGSIZE);
+    }
+
+  return true;
+}
+
+/* Faults in the page containing FAULT_ADDR.
+   Returns true if successful, false on failure. */
+bool
+page_in (void *fault_addr) 
+{
+  struct page *p;
+  bool success;
+
+  /* Can't handle page faults without a hash table. */
+  if (thread_current ()->pages == NULL) 
+    return false;
+
+  p = page_for_addr (fault_addr);
+  if (p == NULL) 
+    return false; 
+
+  frame_lock (p);
+  if (p->frame == NULL)
+    {
+      if (!do_page_in (p))
+        return false;
+    }
+  ASSERT (lock_held_by_current_thread (&p->frame->lock));
+    
+  /* Install frame into page table. */
+  success = pagedir_set_page (thread_current ()->pagedir, p->addr,
+                              p->frame->base, !p->read_only);
+
+  /* Release frame. */
+  frame_unlock (p->frame);
+
+  return success;
+}
+
+/* Evicts page P.
+   P must have a locked frame.
+   Return true if successful, false on failure. */
+bool
+page_out (struct page *p) 
+{
+  bool dirty;
+  bool ok;
+
+  ASSERT (p->frame != NULL);
+  ASSERT (lock_held_by_current_thread (&p->frame->lock));
+
+  /* Mark page not present in page table, forcing accesses by the
+     process to fault.  This must happen before checking the
+     dirty bit, to prevent a race with the process dirtying the
+     page. */
+  pagedir_clear_page (p->thread->pagedir, p->addr);
+
+  /* Has the frame been modified? */
+  dirty = pagedir_is_dirty (p->thread->pagedir, p->addr);
+
+  /* Write frame contents to disk if necessary. */
+  if (p->file != NULL) 
+    {
+      if (dirty) 
+        {
+          if (p->private)
+            ok = swap_out (p);
+          else 
+            ok = file_write_at (p->file, p->frame->base, p->file_bytes,
+                                p->file_offset) == p->file_bytes;
+        }
+      else
+        ok = true;
+    }
+  else
+    ok = swap_out (p);
+  if (ok) 
+    {
+      //memset (p->frame->base, 0xcc, PGSIZE);
+      p->frame = NULL; 
+    }
+  return ok;
+}
+
+/* Returns true if page P's data has been accessed recently,
+   false otherwise.
+   P must have a frame locked into memory. */
+bool
+page_accessed_recently (struct page *p) 
+{
+  bool was_accessed;
+
+  ASSERT (p->frame != NULL);
+  ASSERT (lock_held_by_current_thread (&p->frame->lock));
+
+  was_accessed = pagedir_is_accessed (p->thread->pagedir, p->addr);
+  if (was_accessed)
+    pagedir_set_accessed (p->thread->pagedir, p->addr, false);
+  return was_accessed;
+}
+
+/* Adds a mapping for user virtual address VADDR to the page hash
+   table.  Fails if VADDR is already mapped or if memory
+   allocation fails. */
+struct page *
+page_allocate (void *vaddr, bool read_only)
+{
+  struct thread *t = thread_current ();
+  struct page *p = malloc (sizeof *p);
+  if (p != NULL) 
+    {
+      p->addr = pg_round_down (vaddr);
+
+      p->read_only = read_only;
+      p->private = !read_only;
+
+      p->frame = NULL;
+
+      p->sector = (disk_sector_t) -1;
+
+      p->file = NULL;
+      p->file_offset = 0;
+      p->file_bytes = 0;
+
+      p->thread = thread_current ();
+
+      if (hash_insert (t->pages, &p->hash_elem) != NULL) 
+        {
+          /* Already mapped. */
+          free (p);
+          p = NULL;
+        }
+    }
+  return p;
+}
+
+/* Evicts the page containing address VADDR
+   and removes it from the page table. */
+void
+page_deallocate (void *vaddr) 
+{
+  struct page *p = page_for_addr (vaddr);
+  ASSERT (p != NULL);
+  frame_lock (p);
+  if (p->frame)
+    {
+      struct frame *f = p->frame;
+      if (p->file && !p->private) 
+        page_out (p); 
+      frame_free (f);
+    }
+  hash_delete (thread_current ()->pages, &p->hash_elem);
+  free (p);
+}
+
+/* Returns a hash value for the page that E refers to. */
+unsigned
+page_hash (const struct hash_elem *e, void *aux UNUSED) 
+{
+  const struct page *p = hash_entry (e, struct page, hash_elem);
+  return ((uintptr_t) p->addr) >> PGBITS;
+}
+
+/* Returns true if page A precedes page B. */
+bool
+page_less (const struct hash_elem *a_, const struct hash_elem *b_,
+           void *aux UNUSED) 
+{
+  const struct page *a = hash_entry (a_, struct page, hash_elem);
+  const struct page *b = hash_entry (b_, struct page, hash_elem);
+  
+  return a->addr < b->addr;
+}
+
+/* Tries to lock the page containing ADDR into physical memory.
+   If WILL_WRITE is true, the page must be writeable;
+   otherwise it may be read-only.
+   Returns true if successful, false on failure. */
+bool
+page_lock (const void *addr, bool will_write) 
+{
+  struct page *p = page_for_addr (addr);
+  if (p == NULL || (p->read_only && will_write))
+    return false;
+  
+  frame_lock (p);
+  if (p->frame == NULL)
+    return (do_page_in (p)
+            && pagedir_set_page (thread_current ()->pagedir, p->addr,
+                                 p->frame->base, !p->read_only)); 
+  else
+    return true;
+}
+
+/* Unlocks a page locked with page_lock(). */
+void
+page_unlock (const void *addr) 
+{
+  struct page *p = page_for_addr (addr);
+  ASSERT (p != NULL);
+  frame_unlock (p->frame);
+}
Index: src/vm/page.h
diff -u src/vm/page.h~ src/vm/page.h
--- src/vm/page.h~ 1969-12-31 16:00:00.000000000 -0800
+++ src/vm/page.h 2006-05-16 13:44:56.000000000 -0700
@@ -0,0 +1,50 @@
+#ifndef VM_PAGE_H
+#define VM_PAGE_H
+
+#include <hash.h>
+#include "devices/disk.h"
+#include "filesys/off_t.h"
+#include "threads/synch.h"
+
+/* Virtual page. */
+struct page 
+  {
+    /* Immutable members. */
+    void *addr;                 /* User virtual address. */
+    bool read_only;             /* Read-only page? */
+    struct thread *thread;      /* Owning thread. */
+
+    /* Accessed only in owning process context. */
+    struct hash_elem hash_elem; /* struct thread `pages' hash element. */
+
+    /* Set only in owning process context with frame->frame_lock held.
+       Cleared only with scan_lock and frame->frame_lock held. */
+    struct frame *frame;        /* Page frame. */
+
+    /* Swap information, protected by frame->frame_lock. */
+    disk_sector_t sector;       /* Starting sector of swap area, or -1. */
+    
+    /* Memory-mapped file information, protected by frame->frame_lock. */
+    bool private;               /* False to write back to file,
+                                   true to write back to swap. */
+    struct file *file;          /* File. */
+    off_t file_offset;          /* Offset in file. */
+    off_t file_bytes;           /* Bytes to read/write, 1...PGSIZE. */
+  };
+
+void page_exit (void);
+
+struct page *page_allocate (void *, bool read_only);
+void page_deallocate (void *vaddr);
+
+bool page_in (void *fault_addr);
+bool page_out (struct page *);
+bool page_accessed_recently (struct page *);
+
+bool page_lock (const void *, bool will_write);
+void page_unlock (const void *);
+
+hash_hash_func page_hash;
+hash_less_func page_less;
+
+#endif /* vm/page.h */
Index: src/vm/swap.c
diff -u src/vm/swap.c~ src/vm/swap.c
--- src/vm/swap.c~ 1969-12-31 16:00:00.000000000 -0800
+++ src/vm/swap.c 2006-05-16 13:44:56.000000000 -0700
@@ -0,0 +1,85 @@
+#include "vm/swap.h"
+#include <bitmap.h>
+#include <debug.h>
+#include <stdio.h>
+#include "vm/frame.h"
+#include "vm/page.h"
+#include "devices/disk.h"
+#include "threads/synch.h"
+#include "threads/vaddr.h"
+
+/* The swap disk. */
+static struct disk *swap_disk;
+
+/* Used swap pages. */
+static struct bitmap *swap_bitmap;
+
+/* Protects swap_bitmap. */
+static struct lock swap_lock;
+
+/* Number of sectors per page. */
+#define PAGE_SECTORS (PGSIZE / DISK_SECTOR_SIZE)
+
+/* Sets up swap. */
+void
+swap_init (void) 
+{
+  swap_disk = disk_get (1, 1);
+  if (swap_disk == NULL) 
+    {
+      printf ("no swap disk--swap disabled\n");
+      swap_bitmap = bitmap_create (0);
+    }
+  else
+    swap_bitmap = bitmap_create (disk_size (swap_disk) / PAGE_SECTORS);
+  if (swap_bitmap == NULL)
+    PANIC ("couldn't create swap bitmap");
+  lock_init (&swap_lock);
+}
+
+/* Swaps in page P, which must have a locked frame
+   (and be swapped out). */
+void
+swap_in (struct page *p) 
+{
+  size_t i;
+  
+  ASSERT (p->frame != NULL);
+  ASSERT (lock_held_by_current_thread (&p->frame->lock));
+  ASSERT (p->sector != (disk_sector_t) -1);
+
+  for (i = 0; i < PAGE_SECTORS; i++)
+    disk_read (swap_disk, p->sector + i,
+               p->frame->base + i * DISK_SECTOR_SIZE);
+  bitmap_reset (swap_bitmap, p->sector / PAGE_SECTORS);
+  p->sector = (disk_sector_t) -1;
+}
+
+/* Swaps out page P, which must have a locked frame. */
+bool
+swap_out (struct page *p) 
+{
+  size_t slot;
+  size_t i;
+
+  ASSERT (p->frame != NULL);
+  ASSERT (lock_held_by_current_thread (&p->frame->lock));
+
+  lock_acquire (&swap_lock);
+  slot = bitmap_scan_and_flip (swap_bitmap, 0, 1, false);
+  lock_release (&swap_lock);
+  if (slot == BITMAP_ERROR) 
+    return false; 
+
+  p->sector = slot * PAGE_SECTORS;
+  for (i = 0; i < PAGE_SECTORS; i++)
+    disk_write (swap_disk, p->sector + i,
+                p->frame->base + i * DISK_SECTOR_SIZE);
+  
+  p->private = false;
+  p->file = NULL;
+  p->file_offset = 0;
+  p->file_bytes = 0;
+
+  return true;
+}
Index: src/vm/swap.h
diff -u src/vm/swap.h~ src/vm/swap.h
--- src/vm/swap.h~ 1969-12-31 16:00:00.000000000 -0800
+++ src/vm/swap.h 2006-05-16 13:44:56.000000000 -0700
@@ -0,0 +1,11 @@
+#ifndef VM_SWAP_H
+#define VM_SWAP_H 1
+
+#include <stdbool.h>
+
+struct page;
+void swap_init (void);
+void swap_in (struct page *);
+bool swap_out (struct page *);
+
+#endif /* vm/swap.h */