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