pintos-os.org Git - pintos-anon/blob - solutions/p3.patch

   1 diff -urpN pintos.orig/src/Makefile.build pintos/src/Makefile.build
   2 --- pintos.orig/src/Makefile.build      2004-09-20 20:26:41.000000000 -0700
   3 +++ pintos/src/Makefile.build   2004-09-27 13:29:43.000000000 -0700
   4 @@ -51,8 +51,9 @@ userprog_SRC += userprog/syscall.c    # Sys
   5  userprog_SRC += userprog/gdt.c         # GDT initialization.
   6  userprog_SRC += userprog/tss.c         # TSS management.
   7
   8 -# No virtual memory code yet.
   9 -#vm_SRC = vm/filename.c                        # Some file.
  10 +# Virtual memory code.
  11 +vm_SRC = vm/pageframe.c                        # Page frame management.
  12 +vm_SRC += vm/swap.c                    # Swap file management.
  13
  14  # Filesystem code.
  15  filesys_SRC  = filesys/filesys.c       # Filesystem core.
  16 diff -urpN pintos.orig/src/threads/init.c pintos/src/threads/init.c
  17 --- pintos.orig/src/threads/init.c      2004-09-26 14:15:17.000000000 -0700
  18 +++ pintos/src/threads/init.c   2004-09-27 16:08:03.000000000 -0700
  19 @@ -21,12 +21,15 @@
  20  #include "threads/test.h"
  21  #include "threads/thread.h"
  22  #ifdef USERPROG
  23 +#include "userprog/pagedir.h"
  24  #include "userprog/process.h"
  25  #include "userprog/exception.h"
  26  #include "userprog/gdt.h"
  27  #include "userprog/syscall.h"
  28  #include "userprog/tss.h"
  29  #endif
  30 +#include "vm/pageframe.h"
  31 +#include "vm/swap.h"
  32  #ifdef FILESYS
  33  #include "devices/disk.h"
  34  #include "filesys/filesys.h"
  35 @@ -78,6 +81,7 @@ main (void)
  36    /* Initialize memory system, segments, paging. */
  37    palloc_init ();
  38    paging_init ();
  39 +  pageframe_init ();
  40  #ifdef USERPROG
  41    tss_init ();
  42    gdt_init ();
  43 @@ -105,6 +109,7 @@ main (void)
  44    disk_init ();
  45    filesys_init (format_filesys);
  46    fsutil_run ();
  47 +  swap_init ();
  48  #endif
  49
  50    printf ("Boot complete.\n");
  51 diff -urpN pintos.orig/src/threads/palloc.c pintos/src/threads/palloc.c
  52 diff -urpN pintos.orig/src/threads/palloc.h pintos/src/threads/palloc.h
  53 diff -urpN pintos.orig/src/threads/synch.c pintos/src/threads/synch.c
  54 --- pintos.orig/src/threads/synch.c     2004-09-19 21:29:53.000000000 -0700
  55 +++ pintos/src/threads/synch.c  2004-09-27 13:29:43.000000000 -0700
  56 @@ -330,3 +330,35 @@ cond_name (const struct condition *cond)
  57
  58    return cond->name;
  59  }
  60 +\f
  61 +void
  62 +latch_init (struct latch *latch, const char *name)
  63 +{
  64 +  latch->released = false;
  65 +  lock_init (&latch->monitor_lock, name);
  66 +  cond_init (&latch->rel_cond, name);
  67 +}
  68 +
  69 +void
  70 +latch_acquire (struct latch *latch)
  71 +{
  72 +  lock_acquire (&latch->monitor_lock);
  73 +  if (!latch->released)
  74 +    {
  75 +      cond_wait (&latch->rel_cond, &latch->monitor_lock);
  76 +      ASSERT (latch->released);
  77 +    }
  78 +  lock_release (&latch->monitor_lock);
  79 +}
  80 +
  81 +void
  82 +latch_release (struct latch *latch)
  83 +{
  84 +  lock_acquire (&latch->monitor_lock);
  85 +  if (!latch->released)
  86 +    {
  87 +      latch->released = true;
  88 +      cond_signal (&latch->rel_cond, &latch->monitor_lock);
  89 +    }
  90 +  lock_release (&latch->monitor_lock);
  91 +}
  92 diff -urpN pintos.orig/src/threads/synch.h pintos/src/threads/synch.h
  93 --- pintos.orig/src/threads/synch.h     2004-09-19 21:29:53.000000000 -0700
  94 +++ pintos/src/threads/synch.h  2004-09-27 13:29:43.000000000 -0700
  95 @@ -44,4 +44,16 @@ void cond_signal (struct condition *, st
  96  void cond_broadcast (struct condition *, struct lock *);
  97  const char *cond_name (const struct condition *);
  98
  99 +/* Latch. */
 100 +struct latch
 101 +  {
 102 +    bool released;              /* Released yet? */
 103 +    struct lock monitor_lock;   /* Monitor lock. */
 104 +    struct condition rel_cond;  /* Signaled when released. */
 105 +  };
 106 +
 107 +void latch_init (struct latch *, const char *);
 108 +void latch_acquire (struct latch *);
 109 +void latch_release (struct latch *);
 110 +
 111  #endif /* threads/synch.h */
 112 diff -urpN pintos.orig/src/threads/thread.c pintos/src/threads/thread.c
 113 --- pintos.orig/src/threads/thread.c    2004-09-26 14:15:17.000000000 -0700
 114 +++ pintos/src/threads/thread.c 2004-09-27 13:29:43.000000000 -0700
 115 @@ -13,6 +13,7 @@
 116  #include "threads/synch.h"
 117  #ifdef USERPROG
 118  #include "userprog/process.h"
 119 +#include "userprog/syscall.h"
 120  #endif
 121
 122  /* Random value for struct thread's `magic' member.
 123 @@ -80,6 +81,7 @@ thread_init (void)
 124    init_thread (initial_thread, "main", PRI_DEFAULT);
 125    initial_thread->status = THREAD_RUNNING;
 126    initial_thread->tid = allocate_tid ();
 127 +  sema_up (&initial_thread->can_die);
 128  }
 129
 130  /* Starts preemptive thread scheduling by enabling interrupts.
 131 @@ -148,6 +150,7 @@ thread_create (const char *name, int pri
 132    /* Initialize thread. */
 133    init_thread (t, name, priority);
 134    tid = t->tid = allocate_tid ();
 135 +  list_push_back (&thread_current ()->children, &t->children_elem);
 136
 137    /* Stack frame for kernel_thread(). */
 138    kf = alloc_frame (t, sizeof *kf);
 139 @@ -224,16 +227,36 @@ thread_tid (void)
 140  void
 141  thread_exit (void)
 142  {
 143 +  struct thread *t = thread_current ();
 144 +  struct list_elem *e, *next;
 145 +
 146    ASSERT (!intr_context ());
 147
 148  #ifdef USERPROG
 149    process_exit ();
 150  #endif
 151 +  syscall_exit ();
 152 +
 153 +  /* Notify our parent that we're dying. */
 154 +  latch_release (&t->ready_to_die);
 155 +
 156 +  /* Notify our children that they can die. */
 157 +  for (e = list_begin (&t->children); e != list_end (&t->children);
 158 +       e = next)
 159 +    {
 160 +      struct thread *child = list_entry (e, struct thread, children_elem);
 161 +      next = list_next (e);
 162 +      list_remove (e);
 163 +      sema_up (&child->can_die);
 164 +    }
 165 +
 166 +  /* Wait until our parent is ready for us to die. */
 167 +  sema_down (&t->can_die);
 168
 169    /* Just set our status to dying and schedule another process.
 170       We will be destroyed during the call to schedule_tail(). */
 171    intr_disable ();
 172 -  thread_current ()->status = THREAD_DYING;
 173 +  t->status = THREAD_DYING;
 174    schedule ();
 175    NOT_REACHED ();
 176  }
 177 @@ -283,8 +290,22 @@ thread_block (void)
 178     This function will be implemented in problem 1-2.  For now, it
 179     does nothing. */
 180 -void
 181 -thread_join (tid_t child_tid UNUSED)
 182 -{
 183 +int
 184 +thread_join (tid_t child_tid)
 185 +{
 186 +  struct thread *cur = thread_current ();
 187 +  struct list_elem *e;
 188 +
 189 +  for (e = list_begin (&cur->children); e != list_end (&cur->children); )
 190 +    {
 191 +      struct thread *child = list_entry (e, struct thread, children_elem);
 192 +      e = list_next (e);
 193 +      if (child->tid == child_tid)
 194 +        {
 195 +          latch_acquire (&child->ready_to_die);
 196 +          return child->ret_code;
 197 +        }
 198 +    }
 199 +  return -1;
 200  }
 201
 202  /* Sets the current thread's priority to NEW_PRIORITY. */
 203 @@ -335,6 +378,12 @@ init_thread (struct thread *t, const cha
 204    strlcpy (t->name, name, sizeof t->name);
 205    t->stack = (uint8_t *) t + PGSIZE;
 206    t->priority = priority;
 207 +  latch_init (&t->ready_to_die, "ready-to-die");
 208 +  sema_init (&t->can_die, 0, "can-die");
 209 +  list_init (&t->children);
 210 +  t->ret_code = -1;
 211 +  list_init (&t->fds);
 212 +  t->next_handle = 2;
 213    t->magic = THREAD_MAGIC;
 214  }
 215
 216 diff -urpN pintos.orig/src/threads/thread.h pintos/src/threads/thread.h
 217 --- pintos.orig/src/threads/thread.h    2004-09-26 14:15:17.000000000 -0700
 218 +++ pintos/src/threads/thread.h 2004-09-27 13:29:43.000000000 -0700
 219 @@ -2,8 +2,10 @@
 220  #define THREADS_THREAD_H
 221
 222  #include <debug.h>
 223 +#include <hash.h>
 224  #include <list.h>
 225  #include <stdint.h>
 226 +#include "threads/synch.h"
 227
 228  /* States in a thread's life cycle. */
 229  enum thread_status
 230 @@ -89,12 +91,24 @@ struct thread
 231      uint8_t *stack;                     /* Saved stack pointer. */
 232      int priority;                       /* Priority. */
 233
 234 +    /* Members for implementing thread_join(). */
 235 +    struct latch ready_to_die;          /* Release when thread about to die. */
 236 +    struct semaphore can_die;           /* Up when thread allowed to die. */
 237 +    struct list children;               /* List of child threads. */
 238 +    struct list_elem children_elem;     /* Element of `children' list. */
 239 +    int ret_code;                       /* Return status. */
 240 +
 241      /* Shared between thread.c and synch.c. */
 242      struct list_elem elem;              /* List element. */
 243
 244  #ifdef USERPROG
 245      /* Owned by userprog/process.c. */
 246      uint32_t *pagedir;                  /* Page directory. */
 247 +    struct hash pages;                  /* Hash of `struct user_page's. */
 248 +
 249 +    /* Owned by syscall.c. */
 250 +    struct list fds;                    /* List of file descriptors. */
 251 +    int next_handle;                    /* Next handle value. */
 252  #endif
 253
 254      /* Owned by thread.c */
 255 @@ -120,7 +132,7 @@ void thread_exit (void) NO_RETURN;
 256  void thread_exit (void) NO_RETURN;
 257  void thread_yield (void);
 258
 259 -void thread_join (tid_t);
 260 +int thread_join (tid_t);
 261
 262  void thread_set_priority (int);
 263  int thread_get_priority (void);
 264 diff -urpN pintos.orig/src/userprog/exception.c pintos/src/userprog/exception.c
 265 --- pintos.orig/src/userprog/exception.c        2004-09-26 14:15:17.000000000 -0700
 266 +++ pintos/src/userprog/exception.c     2004-09-27 13:29:44.000000000 -0700
 267 @@ -1,9 +1,16 @@
 268  #include "userprog/exception.h"
 269  #include <inttypes.h>
 270  #include <stdio.h>
 271 +#include <string.h>
 272  #include "userprog/gdt.h"
 273 +#include "userprog/pagedir.h"
 274 +#include "userprog/process.h"
 275 +#include "filesys/file.h"
 276  #include "threads/interrupt.h"
 277 +#include "threads/mmu.h"
 278  #include "threads/thread.h"
 279 +#include "vm/pageframe.h"
 280 +#include "vm/swap.h"
 281
 282  /* Number of page faults processed. */
 283  static long long page_fault_cnt;
 284 @@ -124,10 +131,13 @@ kill (struct intr_frame *f)
 285  static void
 286  page_fault (struct intr_frame *f)
 287  {
 288 +  struct thread *t;
 289    bool not_present;  /* True: not-present page, false: writing r/o page. */
 290    bool write;        /* True: access was write, false: access was read. */
 291    bool user;         /* True: access by user, false: access by kernel. */
 292    void *fault_addr;  /* Fault address. */
 293 +  struct user_page tmp_up, *up;
 294 +  struct hash_elem *e;
 295
 296    /* Obtain faulting address, the virtual address that was
 297       accessed to cause the fault.  It may point to code or to
 298 @@ -147,14 +157,62 @@ page_fault (struct intr_frame *f)
 299    write = (f->error_code & PF_W) != 0;
 300    user = (f->error_code & PF_U) != 0;
 301
 302 -  /* To implement virtual memory, delete the rest of the function
 303 -     body, and replace it with code that brings in the page to
 304 -     which fault_addr refers. */
 305 -  printf ("Page fault at %p: %s error %s page in %s context.\n",
 306 -          fault_addr,
 307 -          not_present ? "not present" : "rights violation",
 308 -          write ? "writing" : "reading",
 309 -          user ? "user" : "kernel");
 310 -  kill (f);
 311 +  if (!not_present)
 312 +    goto bad_access;
 313 +
 314 +  t = thread_current ();
 315 +  if (t->pagedir == NULL)
 316 +    goto bad_access;
 317 +
 318 +  //printf ("fault %p (page=%p)\n", fault_addr, pg_round_down (fault_addr));
 319 +  tmp_up.upage = pg_round_down (fault_addr);
 320 +  e = hash_find (&t->pages, &tmp_up.elem);
 321 +  if (e == NULL)
 322 +    {
 323 +      printf ("no user_page for %p\n", fault_addr);
 324 +      goto bad_access;
 325 +    }
 326 +  up = hash_entry (e, struct user_page, elem);
 327 +
 328 +  if (up->frame == NULL)
 329 +    {
 330 +      if (!pageframe_allocate (up))
 331 +        {
 332 +          printf ("virtual memory exhausted, killing process\n");
 333 +          if (!user)
 334 +            goto bad_access;
 335 +          thread_exit ();
 336 +        }
 337 +      if (up->file != NULL)
 338 +        {
 339 +          off_t amt = file_read_at (up->file,
 340 +                                    up->frame->kpage, up->file_size,
 341 +                                    up->file_ofs);
 342 +          ASSERT (amt == (off_t) up->file_size);
 343 +          memset (up->frame->kpage + up->file_size, 0, PGSIZE - up->file_size);
 344 +        }
 345 +      else if (up->swap_page != SIZE_MAX)
 346 +        swap_read (up);
 347 +      else
 348 +        memset (up->frame->kpage, 0, PGSIZE);
 349 +    }
 350 +  pagedir_set_page (t->pagedir, up->upage, up->frame->kpage, true);
 351 +  return;
 352 +
 353 + bad_access:
 354 +  if (user || fault_addr > PHYS_BASE)
 355 +    {
 356 +      printf ("Page fault at %p: %s error %s page in %s context.\n",
 357 +              fault_addr,
 358 +              not_present ? "not present" : "rights violation",
 359 +              write ? "writing" : "reading",
 360 +              user ? "user" : "kernel");
 361 +      kill (f);
 362 +    }
 363 +  else
 364 +    {
 365 +      f->eip = (void (*) (void)) f->eax;
 366 +      f->eax = 0;
 367 +    }
 368  }
 369
 370 diff -urpN pintos.orig/src/userprog/process.c pintos/src/userprog/process.c
 371 --- pintos.orig/src/userprog/process.c  2004-09-22 17:58:29.000000000 -0700
 372 +++ pintos/src/userprog/process.c       2004-09-27 14:43:09.000000000 -0700
 373 @@ -7,15 +7,18 @@
 374  #include "userprog/gdt.h"
 375  #include "userprog/pagedir.h"
 376  #include "userprog/tss.h"
 377 +#include "vm/pageframe.h"
 378  #include "filesys/directory.h"
 379  #include "filesys/file.h"
 380  #include "filesys/filesys.h"
 381  #include "threads/flags.h"
 382  #include "threads/init.h"
 383  #include "threads/interrupt.h"
 384 +#include "threads/malloc.h"
 385  #include "threads/mmu.h"
 386  #include "threads/palloc.h"
 387  #include "threads/thread.h"
 388 +#include "vm/swap.h"
 389
 390  static thread_func execute_thread NO_RETURN;
 391  static bool load (const char *cmdline, void (**eip) (void), void **esp);
 392 @@ -100,6 +103,10 @@ process_exit (void)
 393        cur->pagedir = NULL;
 394        pagedir_activate (NULL);
 395        pagedir_destroy (pd);
 396 +
 397 +      /* We maintain the invariant that `hash' is initialized iff
 398 +         `pd != NULL'. */
 399 +      hash_destroy (&cur->pages);
 400      }
 401  }
 402
 403 @@ -182,7 +189,11 @@ struct Elf32_Phdr
 404  #define PF_R 4          /* Readable. */
 405
 406  static bool load_segment (struct file *, const struct Elf32_Phdr *);
 407 -static bool setup_stack (void **esp);
 408 +static bool setup_stack (const char *cmdline, void **esp);
 409 +static unsigned user_page_hash (const struct hash_elem *, void *);
 410 +static bool user_page_less (const struct hash_elem *, const struct hash_elem *,
 411 +                            void *);
 412 +static struct user_page *make_user_page (void *upage);
 413
 414  /* Aborts loading an executable, with an error message. */
 415  #define LOAD_ERROR(MSG)                                         \
 416 @@ -198,19 +208,35 @@ static bool setup_stack (void **esp);
 417     and its initial stack pointer into *ESP.
 418     Returns true if successful, false otherwise. */
 419  bool
 420 -load (const char *filename, void (**eip) (void), void **esp)
 421 +load (const char *cmdline, void (**eip) (void), void **esp)
 422  {
 423    struct thread *t = thread_current ();
 424 +  char filename[NAME_MAX + 2];
 425    struct Elf32_Ehdr ehdr;
 426    struct file *file = NULL;
 427    off_t file_ofs;
 428    bool success = false;
 429 +  char *cp;
 430    int i;
 431
 432 +  /* Create hash of user pages. */
 433 +  hash_init (&t->pages, user_page_hash, user_page_less, NULL);
 434 +
 435    /* Allocate page directory. */
 436    t->pagedir = pagedir_create ();
 437 -  if (t->pagedir == NULL)
 438 -    LOAD_ERROR (("page directory allocation failed"));
 439 +  if (t->pagedir == NULL)
 440 +    {
 441 +      hash_destroy (&t->pages);
 442 +      LOAD_ERROR (("page directory allocation failed"));
 443 +    }
 444 +
 445 +  /* Extract filename from command line. */
 446 +  while (*cmdline == ' ')
 447 +    cmdline++;
 448 +  strlcpy (filename, cmdline, sizeof filename);
 449 +  cp = strchr (filename, ' ');
 450 +  if (cp != NULL)
 451 +    *cp = '\0';
 452
 453    /* Open executable file. */
 454    file = filesys_open (filename);
 455 @@ -269,8 +295,23 @@ load (const char *filename, void (**eip)
 456      }
 457
 458    /* Set up stack. */
 459 -  if (!setup_stack (esp))
 460 +  if (!setup_stack (cmdline, esp))
 461      goto done;
 462 +
 463 +#if 0
 464 +  {
 465 +    struct hash_iterator i;
 466 +
 467 +    hash_first (&i, &thread_current ()->pages);
 468 +    while (hash_next (&i))
 469 +      {
 470 +        struct user_page *up = hash_entry (hash_cur (&i),
 471 +                                           struct user_page, elem);
 472 +        printf ("%08x ", up->upage);
 473 +      }
 474 +    printf ("\n");
 475 +  }
 476 +#endif
 477
 478    /* Start address. */
 479    *eip = (void (*) (void)) ehdr.e_entry;
 480 @@ -279,14 +320,12 @@ load (const char *filename, void (**eip)
 481
 482   done:
 483    /* We arrive here whether the load is successful or not. */
 484 -  file_close (file);
 485 +  //file_close (file);                  // FIXME
 486    return success;
 487  }
 488  \f
 489  /* load() helpers. */
 490
 491 -static bool install_page (void *upage, void *kpage);
 492 -
 493  /* Loads the segment described by PHDR from FILE into user
 494     address space.  Return true if successful, false otherwise. */
 495  static bool
 496 @@ -296,6 +335,7 @@ load_segment (struct file *file, const s
 497    uint8_t *upage;     /* Iterator from start to end. */
 498    off_t filesz_left;  /* Bytes left of file data (as opposed to
 499                           zero-initialized bytes). */
 500 +  off_t file_ofs;
 501
 502    /* Is this a read-only segment?  Not currently used, so it's
 503       commented out.  You'll want to use it when implementing VM
 504 @@ -340,70 +380,207 @@ load_segment (struct file *file, const s
 505
 506    /* Load the segment page-by-page into memory. */
 507    filesz_left = phdr->p_filesz + (phdr->p_vaddr & PGMASK);
 508 -  file_seek (file, ROUND_DOWN (phdr->p_offset, PGSIZE));
 509 +  file_ofs = ROUND_DOWN (phdr->p_offset, PGSIZE);
 510    for (upage = start; upage < (uint8_t *) end; upage += PGSIZE)
 511      {
 512        /* We want to read min(PGSIZE, filesz_left) bytes from the
 513           file into the page and zero the rest. */
 514        size_t read_bytes = filesz_left >= PGSIZE ? PGSIZE : filesz_left;
 515 -      size_t zero_bytes = PGSIZE - read_bytes;
 516 -      uint8_t *kpage = palloc_get_page (PAL_USER);
 517 -      if (kpage == NULL)
 518 +      struct user_page *up = make_user_page (upage);
 519 +      if (up == NULL)
 520          return false;
 521
 522 -      /* Do the reading and zeroing. */
 523 -      if (file_read (file, kpage, read_bytes) != (int) read_bytes)
 524 +      if (read_bytes > 0)
 525          {
 526 -          palloc_free_page (kpage);
 527 -          return false;
 528 +          /* Map page. */
 529 +          up->file = file;
 530 +          up->file_ofs = file_ofs;
 531 +          up->file_size = read_bytes;
 532 +          file_ofs += read_bytes;
 533          }
 534 -      memset (kpage + read_bytes, 0, zero_bytes);
 535 -      filesz_left -= read_bytes;
 536 -
 537 -      /* Add the page to the process's address space. */
 538 -      if (!install_page (upage, kpage))
 539 +      else
 540          {
 541 -          palloc_free_page (kpage);
 542 -          return false;
 543 +          /* Page is all zeros.  Nothing to do. */
 544          }
 545 +      filesz_left -= read_bytes;
 546      }
 547 +
 548 +  return true;
 549 +}
 550 +
 551 +static void
 552 +reverse (int argc, char **argv)
 553 +{
 554 +  for (; argc > 1; argc -= 2, argv++)
 555 +    {
 556 +      char *tmp = argv[0];
 557 +      argv[0] = argv[argc - 1];
 558 +      argv[argc - 1] = tmp;
 559 +    }
 560 +}
 561 +static void *
 562 +push (uint8_t *kpage, size_t *ofs, const void *buf, size_t size)
 563 +{
 564 +  size_t padsize = ROUND_UP (size, sizeof (uint32_t));
 565 +  if (*ofs < padsize)
 566 +    return NULL;
 567 +
 568 +  *ofs -= padsize;
 569 +  memcpy (kpage + *ofs + (padsize - size), buf, size);
 570 +  return kpage + *ofs + (padsize - size);
 571 +}
 572 +
 573 +static bool
 574 +init_cmdline (uint8_t *kpage, uint8_t *upage, const char *cmdline,
 575 +              void **esp)
 576 +{
 577 +  size_t ofs = PGSIZE;
 578 +  char *const null = NULL;
 579 +  char *cmdline_copy;
 580 +  char *karg, *saveptr;
 581 +  int argc;
 582 +  char **argv;
 583 +
 584 +  /* Push command line string. */
 585 +  cmdline_copy = push (kpage, &ofs, cmdline, strlen (cmdline) + 1);
 586 +  if (cmdline_copy == NULL)
 587 +    return false;
 588 +
 589 +  if (push (kpage, &ofs, &null, sizeof null) == NULL)
 590 +    return false;
 591 +
 592 +  /* Parse command line into arguments
 593 +     and push them in reverse order. */
 594 +  argc = 0;
 595 +  for (karg = strtok_r (cmdline_copy, " ", &saveptr); karg != NULL;
 596 +       karg = strtok_r (NULL, " ", &saveptr))
 597 +    {
 598 +      char *uarg = upage + (karg - (char *) kpage);
 599 +      if (push (kpage, &ofs, &uarg, sizeof uarg) == NULL)
 600 +        return false;
 601 +      argc++;
 602 +    }
 603 +
 604 +  /* Reverse the order of the command line arguments. */
 605 +  argv = (char **) (upage + ofs);
 606 +  reverse (argc, (char **) (kpage + ofs));
 607 +
 608 +  /* Push argv, argc, "return address". */
 609 +  if (push (kpage, &ofs, &argv, sizeof argv) == NULL
 610 +      || push (kpage, &ofs, &argc, sizeof argc) == NULL
 611 +      || push (kpage, &ofs, &null, sizeof null) == NULL)
 612 +    return false;
 613 +
 614 +  /* Set initial stack pointer. */
 615 +  *esp = upage + ofs;
 616
 617    return true;
 618  }
 619
 620 -/* Create a minimal stack by mapping a zeroed page at the top of
 621 -   user virtual memory. */
 622 +/* Create a minimal stack for T by mapping a page at the
 623 +   top of user virtual memory.  Fills in the page using CMDLINE
 624 +   and sets *ESP to the stack pointer. */
 625  static bool
 626 -setup_stack (void **esp)
 627 +setup_stack (const char *cmdline, void **esp)
 628  {
 629 -  uint8_t *kpage;
 630 -  bool success = false;
 631 +  struct user_page *up = make_user_page ((uint8_t *) PHYS_BASE - PGSIZE);
 632 +  return (up != NULL
 633 +          && pageframe_allocate (up)
 634 +          && init_cmdline (up->frame->kpage, up->upage, cmdline, esp));
 635 +}
 636 +
 637 +static unsigned
 638 +user_page_hash (const struct hash_elem *e, void *aux UNUSED)
 639 +{
 640 +  struct user_page *up = hash_entry (e, struct user_page, elem);
 641 +  return hash_bytes (&up->upage, sizeof up->upage);
 642 +}
 643
 644 -  kpage = palloc_get_page (PAL_USER | PAL_ZERO);
 645 -  if (kpage != NULL)
 646 +static bool
 647 +user_page_less (const struct hash_elem *a_,
 648 +                const struct hash_elem *b_, void *aux UNUSED)
 649 +{
 650 +  struct user_page *a = hash_entry (a_, struct user_page, elem);
 651 +  struct user_page *b = hash_entry (b_, struct user_page, elem);
 652 +
 653 +  return a->upage < b->upage;
 654 +}
 655 +
 656 +static struct user_page *
 657 +make_user_page (void *upage)
 658 +{
 659 +  struct user_page *up;
 660 +
 661 +  up = malloc (sizeof *up);
 662 +  if (up != NULL)
 663      {
 664 -      success = install_page (((uint8_t *) PHYS_BASE) - PGSIZE, kpage);
 665 -      if (success)
 666 -        *esp = PHYS_BASE;
 667 +      memset (up, 0, sizeof *up);
 668 +      up->swap_page = SIZE_MAX;
 669 +
 670 +      up->upage = upage;
 671 +      if (hash_insert (&thread_current ()->pages, &up->elem) != NULL)
 672 +        {
 673 +          free (up);
 674 +          up = NULL;
 675 +        }
 676 +#if 0
 677        else
 678 -        palloc_free_page (kpage);
 679 +        printf ("make_user_page(%p) okay\n", upage);
 680 +#endif
 681      }
 682 -  else
 683 -    printf ("failed to allocate process stack\n");
 684
 685 -  return success;
 686 +  return up;
 687  }
 688
 689 -/* Adds a mapping from user virtual address UPAGE to kernel
 690 -   virtual address KPAGE to the page table.  Fails if UPAGE is
 691 -   already mapped or if memory allocation fails. */
 692 -static bool
 693 -install_page (void *upage, void *kpage)
 694 +static void
 695 +dump_page (struct user_page *up)
 696  {
 697 -  struct thread *t = thread_current ();
 698 +  off_t amt;
 699
 700 -  /* Verify that there's not already a page at that virtual
 701 -     address, then map our page there. */
 702 -  return (pagedir_get_page (t->pagedir, upage) == NULL
 703 -          && pagedir_set_page (t->pagedir, upage, kpage, true));
 704 +  ASSERT (up->file != NULL);
 705 +  up->file_size = PGSIZE;
 706 +  amt = file_write_at (up->file, up->frame->kpage,
 707 +                       up->file_size, up->file_ofs);
 708 +  ASSERT (amt == (off_t) up->file_size);
 709  }
 710 +
 711 +bool
 712 +process_evict_page (struct thread *t, struct user_page *up)
 713 +{
 714 +  ASSERT (up->frame != NULL);
 715 +
 716 +  if (pagedir_test_accessed (t->pagedir, up->upage))
 717 +    {
 718 +      pagedir_clear_accessed (t->pagedir, up->upage);
 719 +      return false;
 720 +    }
 721 +
 722 +  if (up->file == NULL)
 723 +    {
 724 +      if (!swap_write (up))
 725 +        return false;
 726 +    }
 727 +  else if (pagedir_test_dirty (t->pagedir, up->upage))
 728 +    {
 729 +      /* Need to write out. */
 730 +      if (up->private)
 731 +        {
 732 +          up->file = NULL; // FIXME
 733 +          up->private = false;
 734 +          if (!swap_write (up))
 735 +            return false;
 736 +        }
 737 +
 738 +      dump_page (up);
 739 +    }
 740 +  else
 741 +    {
 742 +      /* Already on disk, not dirty.
 743 +         Nothing to do. */
 744 +    }
 745 +
 746 +  pagedir_clear_page (t->pagedir, up->upage);
 747 +  pageframe_free (up->frame);
 748 +  return true;
 749 +}
 750 +
 751 diff -urpN pintos.orig/src/userprog/process.h pintos/src/userprog/process.h
 752 --- pintos.orig/src/userprog/process.h  2004-09-21 22:42:17.000000000 -0700
 753 +++ pintos/src/userprog/process.h       2004-09-27 14:43:13.000000000 -0700
 754 @@ -2,9 +2,32 @@
 755  #define USERPROG_PROCESS_H
 756
 757  #include "threads/thread.h"
 758 +#include "filesys/off_t.h"
 759 +
 760 +struct user_page
 761 +  {
 762 +    struct hash_elem elem;
 763 +    void *upage;                /* Virtual address of mapping. */
 764 +
 765 +    /* If FRAME is nonnull, the page is in memory.
 766 +       If FILE is nonnull, the page is on disk.
 767 +       If both are null, the page is all zeroes.
 768 +       If both are nonnull, the page is in memory and backed by a
 769 +       file mapping (not the swap file). */
 770 +    struct page_frame *frame;
 771 +    size_t swap_page;
 772 +    struct file *file;
 773 +    off_t file_ofs;
 774 +    size_t file_size;           /* Number of bytes on disk, <= PGSIZE. */
 775 +
 776 +    bool dirty : 1;
 777 +    bool accessed : 1;
 778 +    bool private : 1;           /* Write dirty pages to swap or to FILE? */
 779 +  };
 780
 781  tid_t process_execute (const char *filename);
 782  void process_exit (void);
 783  void process_activate (void);
 784 +bool process_evict_page (struct thread *, struct user_page *);
 785
 786  #endif /* userprog/process.h */
 787 diff -urpN pintos.orig/src/userprog/syscall.c pintos/src/userprog/syscall.c
 788 --- pintos.orig/src/userprog/syscall.c  2004-09-26 14:15:17.000000000 -0700
 789 +++ pintos/src/userprog/syscall.c       2004-09-27 14:42:01.000000000 -0700
 790 @@ -1,20 +1,429 @@
 791  #include "userprog/syscall.h"
 792  #include <stdio.h>
 793 +#include <string.h>
 794  #include <syscall-nr.h>
 795 +#include "threads/init.h"
 796  #include "threads/interrupt.h"
 797 +#include "threads/malloc.h"
 798 +#include "threads/mmu.h"
 799 +#include "threads/palloc.h"
 800  #include "threads/thread.h"
 801 +#include "userprog/pagedir.h"
 802 +#include "userprog/process.h"
 803 +#include "filesys/filesys.h"
 804 +#include "filesys/file.h"
 805 +#include "devices/kbd.h"
 806 +
 807 +typedef int syscall_function (int, int, int);
 808 +
 809 +static int sys_halt (void);
 810 +static int sys_exit (int status);
 811 +static int sys_exec (const char *ufile);
 812 +static int sys_join (tid_t);
 813 +static int sys_create (const char *ufile, unsigned initial_size);
 814 +static int sys_remove (const char *ufile);
 815 +static int sys_open (const char *ufile);
 816 +static int sys_filesize (int handle);
 817 +static int sys_read (int handle, void *udst_, unsigned size);
 818 +static int sys_write (int handle, void *usrc_, unsigned size);
 819 +static int sys_seek (int handle, unsigned position);
 820 +static int sys_tell (int handle);
 821 +static int sys_close (int handle);
 822 +
 823 +struct syscall
 824 +  {
 825 +    size_t arg_cnt;
 826 +    syscall_function *func;
 827 +  };
 828 +
 829 +struct syscall syscall_table[] =
 830 +  {
 831 +    {0, (syscall_function *) sys_halt},
 832 +    {1, (syscall_function *) sys_exit},
 833 +    {1, (syscall_function *) sys_exec},
 834 +    {1, (syscall_function *) sys_join},
 835 +    {2, (syscall_function *) sys_create},
 836 +    {1, (syscall_function *) sys_remove},
 837 +    {1, (syscall_function *) sys_open},
 838 +    {1, (syscall_function *) sys_filesize},
 839 +    {3, (syscall_function *) sys_read},
 840 +    {3, (syscall_function *) sys_write},
 841 +    {2, (syscall_function *) sys_seek},
 842 +    {1, (syscall_function *) sys_tell},
 843 +    {1, (syscall_function *) sys_close},
 844 +  };
 845 +static const int syscall_cnt = sizeof syscall_table / sizeof *syscall_table;
 846
 847  static void syscall_handler (struct intr_frame *);
 848 +static void copy_in (void *, const void *, size_t);
 849 +
 850 +static struct lock fs_lock;
 851
 852  void
 853  syscall_init (void)
 854  {
 855    intr_register (0x30, 3, INTR_ON, syscall_handler, "syscall");
 856 +  lock_init (&fs_lock, "fs");
 857  }
 858
 859  static void
 860 -syscall_handler (struct intr_frame *f UNUSED)
 861 +syscall_handler (struct intr_frame *f)
 862 +{
 863 +  struct syscall *s;
 864 +  int call_nr;
 865 +  int args[3];
 866 +
 867 +  copy_in (&call_nr, f->esp, sizeof call_nr);
 868 +  if (call_nr < 0 || call_nr >= syscall_cnt)
 869 +    {
 870 +      printf ("bad syscall number %d\n", call_nr);
 871 +      thread_exit ();
 872 +    }
 873 +
 874 +  s = syscall_table + call_nr;
 875 +  ASSERT (s->arg_cnt <= sizeof args / sizeof *args);
 876 +  memset (args, 0, sizeof args);
 877 +  copy_in (args, (uint32_t *) f->esp + 1, sizeof *args * s->arg_cnt);
 878 +  f->eax = s->func (args[0], args[1], args[2]);
 879 +}
 880 +
 881 +static bool
 882 +verify_user (const void *uaddr)
 883 +{
 884 +  return pagedir_get_page (thread_current ()->pagedir, uaddr) != NULL;
 885 +}
 886 +
 887 +static inline bool get_user (uint8_t *dst, const uint8_t *usrc) {
 888 +  int eax;
 889 +  asm ("movl $1f, %%eax; movb %2, %%al; movb %%al, %0; 1:"
 890 +       : "=m" (*dst), "=&a" (eax) : "m" (*usrc));
 891 +  return eax != 0;
 892 +}
 893 +
 894 +static inline bool put_user (uint8_t *udst, uint8_t byte) {
 895 +  int eax;
 896 +  asm ("movl $1f, %%eax; movb %b2, %0; 1:"
 897 +       : "=m" (*udst), "=&a" (eax) : "r" (byte));
 898 +  return eax != 0;
 899 +}
 900 +
 901 +static void
 902 +copy_in (void *dst_, const void *usrc_, size_t size)
 903 +{
 904 +  uint8_t *dst = dst_;
 905 +  const uint8_t *usrc = usrc_;
 906 +
 907 +  for (; size > 0; size--, dst++, usrc++)
 908 +    if (usrc >= (uint8_t *) PHYS_BASE || !get_user (dst, usrc))
 909 +      thread_exit ();
 910 +}
 911 +
 912 +static char *
 913 +copy_in_string (const char *us)
 914 +{
 915 +  char *ks;
 916 +  size_t length;
 917 +
 918 +  ks = palloc_get_page (0);
 919 +  if (ks == NULL)
 920 +    {
 921 +      printf ("copy_in_string: out of memory\n");
 922 +      thread_exit ();
 923 +    }
 924 +
 925 +  for (length = 0; length < PGSIZE; length++)
 926 +    {
 927 +      if (us >= (char *) PHYS_BASE || !get_user (ks + length, us++))
 928 +        {
 929 +          printf ("bad user reference (%p)\n", us + length);
 930 +          thread_exit ();
 931 +        }
 932 +
 933 +      if (ks[length] == '\0')
 934 +        return ks;
 935 +    }
 936 +
 937 +  printf ("copy_in_string: string too long\n");
 938 +  palloc_free_page (ks);
 939 +  thread_exit ();
 940 +}
 941 +
 942 +static int
 943 +sys_halt (void)
 944 +{
 945 +  power_off ();
 946 +}
 947 +
 948 +static int
 949 +sys_exit (int ret_code)
 950  {
 951 -  printf ("system call!\n");
 952 +  thread_current ()->ret_code = ret_code;
 953    thread_exit ();
 954 +  NOT_REACHED ();
 955 +}
 956 +
 957 +static int
 958 +sys_exec (const char *ufile)
 959 +{
 960 +  tid_t tid;
 961 +  char *kfile = copy_in_string (ufile);
 962 +
 963 +  lock_acquire (&fs_lock);
 964 +  tid = process_execute (kfile);
 965 +  lock_release (&fs_lock);
 966 +
 967 +  palloc_free_page (kfile);
 968 +
 969 +  return tid;
 970 +}
 971 +
 972 +static int
 973 +sys_join (tid_t child)
 974 +{
 975 +  return thread_join (child);
 976 +}
 977 +
 978 +static int
 979 +sys_create (const char *ufile, unsigned initial_size)
 980 +{
 981 +  char *kfile = copy_in_string (ufile);
 982 +  bool ok;
 983 +
 984 +  lock_acquire (&fs_lock);
 985 +  ok = filesys_create (kfile, initial_size);
 986 +  lock_release (&fs_lock);
 987 +
 988 +  palloc_free_page (kfile);
 989 +
 990 +  return ok;
 991 +}
 992 +
 993 +static int
 994 +sys_remove (const char *ufile)
 995 +{
 996 +  char *kfile = copy_in_string (ufile);
 997 +  bool ok;
 998 +
 999 +  lock_acquire (&fs_lock);
1000 +  ok = filesys_remove (kfile);
1001 +  lock_release (&fs_lock);
1002 +
1003 +  palloc_free_page (kfile);
1004 +
1005 +  return ok;
1006 +}
1007 +
1008 +struct fildes
1009 +  {
1010 +    struct list_elem elem;
1011 +    struct file *file;
1012 +    int handle;
1013 +  };
1014 +
1015 +static int
1016 +sys_open (const char *ufile)
1017 +{
1018 +  char *kfile = copy_in_string (ufile);
1019 +  struct fildes *fd;
1020 +  int handle = -1;
1021 +
1022 +  fd = malloc (sizeof *fd);
1023 +  if (fd == NULL)
1024 +    goto exit;
1025 +
1026 +  lock_acquire (&fs_lock);
1027 +  fd->file = filesys_open (kfile);
1028 +  if (fd->file != NULL)
1029 +    {
1030 +      struct thread *cur = thread_current ();
1031 +      handle = fd->handle = cur->next_handle++;
1032 +      list_push_front (&cur->fds, &fd->elem);
1033 +    }
1034 +  else
1035 +    free (fd);
1036 +  lock_release (&fs_lock);
1037 +
1038 + exit:
1039 +  palloc_free_page (kfile);
1040 +  return handle;
1041 +}
1042 +
1043 +static struct fildes *
1044 +lookup_fd (int handle)
1045 +{
1046 +  struct thread *cur = thread_current ();
1047 +  struct list_elem *e;
1048 +
1049 +  for (e = list_begin (&cur->fds); e != list_end (&cur->fds);
1050 +       e = list_next (e))
1051 +    {
1052 +      struct fildes *fd = list_entry (e, struct fildes, elem);
1053 +      if (fd->handle == handle)
1054 +        return fd;
1055 +    }
1056 +
1057 +  printf ("no handle %d\n", handle);
1058 +thread_exit ();
1059 +}
1060 +
1061 +static int
1062 +sys_filesize (int handle)
1063 +{
1064 +  struct fildes *fd = lookup_fd (handle);
1065 +  int size;
1066 +
1067 +  lock_acquire (&fs_lock);
1068 +  size = file_length (fd->file);
1069 +  lock_release (&fs_lock);
1070 +
1071 +  return size;
1072 +}
1073 +
1074 +static int
1075 +sys_read (int handle, void *udst_, unsigned size)
1076 +{
1077 +  uint8_t *udst = udst_;
1078 +  struct fildes *fd;
1079 +  int bytes_read = 0;
1080 +
1081 +  if (handle == STDIN_FILENO)
1082 +    {
1083 +      for (bytes_read = 0; (size_t) bytes_read < size; bytes_read++)
1084 +        if (udst >= (uint8_t *) PHYS_BASE || !put_user (udst++, kbd_getc ()))
1085 +          thread_exit ();
1086 +      return bytes_read;
1087 +    }
1088 +
1089 +  lock_acquire (&fs_lock);
1090 +  fd = lookup_fd (handle);
1091 +  while (size > 0)
1092 +    {
1093 +      size_t page_left = PGSIZE - pg_ofs (udst);
1094 +      size_t read_amt = size < page_left ? size : page_left;
1095 +      off_t retval;
1096 +
1097 +      if (!verify_user (udst))
1098 +        {
1099 +          lock_release (&fs_lock);
1100 +          thread_exit ();
1101 +        }
1102 +
1103 +      retval = file_read (fd->file, udst, read_amt);
1104 +      if (retval < 0)
1105 +        {
1106 +          if (bytes_read == 0)
1107 +            bytes_read = -1;
1108 +          break;
1109 +        }
1110 +
1111 +      bytes_read += retval;
1112 +      if (retval != (off_t) read_amt)
1113 +        break;
1114 +
1115 +      udst += retval;
1116 +      size -= retval;
1117 +    }
1118 +  lock_release (&fs_lock);
1119 +
1120 +  return bytes_read;
1121 +}
1122 +
1123 +static int
1124 +sys_write (int handle, void *usrc_, unsigned size)
1125 +{
1126 +  uint8_t *usrc = usrc_;
1127 +  struct fildes *fd = NULL;
1128 +  int bytes_written = 0;
1129 +
1130 +  lock_acquire (&fs_lock);
1131 +  if (handle != STDOUT_FILENO)
1132 +    fd = lookup_fd (handle);
1133 +  while (size > 0)
1134 +    {
1135 +      size_t page_left = PGSIZE - pg_ofs (usrc);
1136 +      size_t write_amt = size < page_left ? size : page_left;
1137 +      off_t retval;
1138 +
1139 +      if (!verify_user (usrc))
1140 +        {
1141 +          lock_release (&fs_lock);
1142 +          thread_exit ();
1143 +        }
1144 +
1145 +      if (handle == STDOUT_FILENO)
1146 +        {
1147 +          putbuf (usrc, write_amt);
1148 +          retval = write_amt;
1149 +        }
1150 +      else
1151 +        retval = file_write (fd->file, usrc, write_amt);
1152 +      if (retval < 0)
1153 +        {
1154 +          if (bytes_written == 0)
1155 +            bytes_written = -1;
1156 +          break;
1157 +        }
1158 +
1159 +      bytes_written += retval;
1160 +      if (retval != (off_t) write_amt)
1161 +        break;
1162 +
1163 +      usrc += retval;
1164 +      size -= retval;
1165 +    }
1166 +  lock_release (&fs_lock);
1167 +
1168 +  return bytes_written;
1169 +}
1170 +
1171 +static int
1172 +sys_seek (int handle, unsigned position)
1173 +{
1174 +  struct fildes *fd = lookup_fd (handle);
1175 +
1176 +  lock_acquire (&fs_lock);
1177 +  file_seek (fd->file, position);
1178 +  lock_release (&fs_lock);
1179 +
1180 +  return 0;
1181 +}
1182 +
1183 +static int
1184 +sys_tell (int handle)
1185 +{
1186 +  struct fildes *fd = lookup_fd (handle);
1187 +  unsigned position;
1188 +
1189 +  lock_acquire (&fs_lock);
1190 +  position = file_tell (fd->file);
1191 +  lock_release (&fs_lock);
1192 +
1193 +  return position;
1194 +}
1195 +
1196 +static int
1197 +sys_close (int handle)
1198 +{
1199 +  struct fildes *fd = lookup_fd (handle);
1200 +  lock_acquire (&fs_lock);
1201 +  file_close (fd->file);
1202 +  lock_release (&fs_lock);
1203 +  list_remove (&fd->elem);
1204 +  free (fd);
1205 +  return 0;
1206 +}
1207 +
1208 +void
1209 +syscall_exit (void)
1210 +{
1211 +  struct thread *cur = thread_current ();
1212 +  struct list_elem *e, *next;
1213 +
1214 +  for (e = list_begin (&cur->fds); e != list_end (&cur->fds); e = next)
1215 +    {
1216 +      struct fildes *fd = list_entry (e, struct fildes, elem);
1217 +      next = list_next (e);
1218 +      file_close (fd->file);
1219 +      free (fd);
1220 +    }
1221  }
1222 diff -urpN pintos.orig/src/userprog/syscall.h pintos/src/userprog/syscall.h
1223 --- pintos.orig/src/userprog/syscall.h  2004-09-05 22:38:45.000000000 -0700
1224 +++ pintos/src/userprog/syscall.h       2004-09-27 13:29:44.000000000 -0700
1225 @@ -2,5 +2,6 @@
1226  #define USERPROG_SYSCALL_H
1227
1228  void syscall_init (void);
1229 +void syscall_exit (void);
1230
1231  #endif /* userprog/syscall.h */
1232 diff -urpN pintos.orig/src/vm/pageframe.c pintos/src/vm/pageframe.c
1233 --- pintos.orig/src/vm/pageframe.c      1969-12-31 16:00:00.000000000 -0800
1234 +++ pintos/src/vm/pageframe.c   2004-09-27 13:29:44.000000000 -0700
1235 @@ -0,0 +1,75 @@
1236 +#include "vm/pageframe.h"
1237 +#include <stdint.h>
1238 +#include "threads/init.h"
1239 +#include "threads/malloc.h"
1240 +#include "threads/mmu.h"
1241 +#include "threads/palloc.h"
1242 +#include "userprog/process.h"
1243 +
1244 +static struct page_frame *frames;
1245 +static size_t frame_cnt;
1246 +
1247 +static struct page_frame *next_frame;
1248 +
1249 +static inline bool
1250 +in_use (const struct page_frame *pf)
1251 +{
1252 +  ASSERT ((pf->owner != NULL) == (pf->user_page != NULL));
1253 +  return pf->owner != NULL;
1254 +}
1255 +
1256 +void
1257 +pageframe_init (void)
1258 +{
1259 +  uint8_t *kpage;
1260 +
1261 +  frame_cnt = ram_pages;
1262 +  frames = calloc (sizeof *frames, frame_cnt);
1263 +  if (frames == NULL)
1264 +    PANIC ("can't allocate page frames");
1265 +
1266 +  while ((kpage = palloc_get_page (PAL_USER)) != NULL)
1267 +    {
1268 +      struct page_frame *pf = frames + (vtop (kpage) >> PGBITS);
1269 +      pf->kpage = kpage;
1270 +    }
1271 +
1272 +  next_frame = frames;
1273 +}
1274 +
1275 +bool
1276 +pageframe_allocate (struct user_page *up)
1277 +{
1278 +  struct page_frame *pf;
1279 +  size_t loops;
1280 +
1281 +  ASSERT (up->frame == NULL);
1282 +
1283 +  loops = 0;
1284 +  do
1285 +    {
1286 +      pf = next_frame++;
1287 +      if (next_frame >= frames + frame_cnt)
1288 +        next_frame = frames;
1289 +      if (loops++ > 2 * frame_cnt)
1290 +        return false;
1291 +    }
1292 +  while (pf->kpage == NULL
1293 +         || (in_use (pf) && !process_evict_page (pf->owner, pf->user_page)));
1294 +
1295 +  ASSERT (!in_use (pf));
1296 +  pf->owner = thread_current ();
1297 +  pf->user_page = up;
1298 +  up->frame = pf;
1299 +  return true;
1300 +}
1301 +
1302 +void
1303 +pageframe_free (struct page_frame *pf)
1304 +{
1305 +  ASSERT (in_use (pf));
1306 +
1307 +  pf->owner = NULL;
1308 +  pf->user_page->frame = NULL;
1309 +  pf->user_page = NULL;
1310 +}
1311 diff -urpN pintos.orig/src/vm/pageframe.h pintos/src/vm/pageframe.h
1312 --- pintos.orig/src/vm/pageframe.h      1969-12-31 16:00:00.000000000 -0800
1313 +++ pintos/src/vm/pageframe.h   2004-09-27 13:29:44.000000000 -0700
1314 @@ -0,0 +1,17 @@
1315 +#ifndef VM_PAGEFRAME_H
1316 +#define VM_PAGEFRAME_H 1
1317 +
1318 +#include <stdbool.h>
1319 +
1320 +struct page_frame
1321 +  {
1322 +    void *kpage;
1323 +    struct thread *owner;
1324 +    struct user_page *user_page;
1325 +  };
1326 +
1327 +void pageframe_init (void);
1328 +bool pageframe_allocate (struct user_page *);
1329 +void pageframe_free (struct page_frame *);
1330 +
1331 +#endif /* vm/pageframe.h */
1332 diff -urpN pintos.orig/src/vm/swap.c pintos/src/vm/swap.c
1333 --- pintos.orig/src/vm/swap.c   1969-12-31 16:00:00.000000000 -0800
1334 +++ pintos/src/vm/swap.c        2004-09-27 13:29:44.000000000 -0700
1335 @@ -0,0 +1,66 @@
1336 +#include "vm/swap.h"
1337 +#include <bitmap.h>
1338 +#include <stdio.h>
1339 +#include "vm/pageframe.h"
1340 +#include "threads/mmu.h"
1341 +#include "filesys/file.h"
1342 +#include "filesys/filesys.h"
1343 +#include "userprog/process.h"
1344 +
1345 +static size_t swap_pages;
1346 +static struct disk *swap_disk;
1347 +static struct bitmap *used_pages;
1348 +
1349 +void
1350 +swap_init (void)
1351 +{
1352 +  swap_disk = disk_get (1, 1);
1353 +  if (swap_disk == NULL)
1354 +    PANIC ("no swap disk");
1355 +  swap_pages = disk_size (swap_disk) / (PGSIZE / DISK_SECTOR_SIZE);
1356 +  printf ("swap disk has room for %zu pages\n", swap_pages);
1357 +
1358 +  used_pages = bitmap_create (swap_pages);
1359 +  if (used_pages == NULL)
1360 +    PANIC ("couldn't create swap bitmap");
1361 +}
1362 +
1363 +bool
1364 +swap_write (struct user_page *up)
1365 +{
1366 +  size_t page;
1367 +  disk_sector_t sector;
1368 +  int i;
1369 +
1370 +  ASSERT (up->frame != NULL);
1371 +  ASSERT (up->file == NULL);
1372 +
1373 +  page = bitmap_scan_and_flip (used_pages, 0, 1, false);
1374 +  if (page == BITMAP_ERROR)
1375 +    return false;
1376 +
1377 +  up->swap_page = page;
1378 +  sector = (disk_sector_t) page * (PGSIZE / DISK_SECTOR_SIZE);
1379 +  for (i = 0; i < PGSIZE / DISK_SECTOR_SIZE; i++)
1380 +    disk_write (swap_disk, sector++, up->frame->kpage + i * DISK_SECTOR_SIZE);
1381 +
1382 +  return true;
1383 +}
1384 +
1385 +void
1386 +swap_read (struct user_page *up)
1387 +{
1388 +  disk_sector_t sector;
1389 +  int i;
1390 +
1391 +  ASSERT (up->frame != NULL);
1392 +
1393 +  ASSERT (bitmap_test (used_pages, up->swap_page));
1394 +  bitmap_reset (used_pages, up->swap_page);
1395 +
1396 +  sector = (disk_sector_t) up->swap_page * (PGSIZE / DISK_SECTOR_SIZE);
1397 +  for (i = 0; i < PGSIZE / DISK_SECTOR_SIZE; i++)
1398 +    disk_read (swap_disk, sector++, up->frame->kpage + i * DISK_SECTOR_SIZE);
1399 +
1400 +  up->swap_page = SIZE_MAX;
1401 +}
1402 diff -urpN pintos.orig/src/vm/swap.h pintos/src/vm/swap.h
1403 --- pintos.orig/src/vm/swap.h   1969-12-31 16:00:00.000000000 -0800
1404 +++ pintos/src/vm/swap.h        2004-09-27 13:29:44.000000000 -0700
1405 @@ -0,0 +1,11 @@
1406 +#ifndef VM_SWAP_H
1407 +#define VM_SWAP_H 1
1408 +
1409 +#include <stdbool.h>
1410 +
1411 +struct user_page;
1412 +void swap_init (void);
1413 +bool swap_write (struct user_page *);
1414 +void swap_read (struct user_page *);
1415 +
1416 +#endif /* vm/swap.h */