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

   1 diff -u src/Makefile.build~ src/Makefile.build
   2 --- src/Makefile.build~ 2005-06-16 21:50:20.000000000 -0700
   3 +++ src/Makefile.build 2005-06-16 15:09:31.000000000 -0700
   4 @@ -53,7 +53,9 @@ userprog_SRC += userprog/gdt.c                # GDT in
   5  userprog_SRC += userprog/tss.c         # TSS management.
   6
   7  # No virtual memory code yet.
   8 -#vm_SRC = vm/filename.c                        # Some file.
   9 +vm_SRC = vm/page.c
  10 +vm_SRC += vm/frame.c
  11 +vm_SRC += vm/swap.c
  12
  13  # Filesystem code.
  14  filesys_SRC  = filesys/filesys.c       # Filesystem core.
  15 @@ -62,6 +64,7 @@ filesys_SRC += filesys/file.c         # Files.
  16  filesys_SRC += filesys/directory.c     # Directories.
  17  filesys_SRC += filesys/inode.c         # File headers.
  18  filesys_SRC += filesys/fsutil.c                # Utilities.
  19 +filesys_SRC += filesys/cache.c         # Cache.
  20
  21  SOURCES = $(foreach dir,$(KERNEL_SUBDIRS),$($(dir)_SRC))
  22  OBJECTS = $(patsubst %.c,%.o,$(patsubst %.S,%.o,$(SOURCES)))
  23 diff -u src/devices/timer.c~ src/devices/timer.c
  24 --- src/devices/timer.c~ 2005-06-15 15:21:01.000000000 -0700
  25 +++ src/devices/timer.c 2005-06-16 15:09:31.000000000 -0700
  26 @@ -23,6 +23,9 @@ static volatile int64_t ticks;
  27     Initialized by timer_calibrate(). */
  28  static unsigned loops_per_tick;
  29
  30 +/* Threads waiting in timer_sleep(). */
  31 +static struct list wait_list;
  32 +
  33  static intr_handler_func timer_interrupt;
  34  static bool too_many_loops (unsigned loops);
  35  static void busy_wait (int64_t loops);
  36 @@ -43,6 +46,8 @@ timer_init (void)
  37    outb (0x40, count >> 8);
  38
  39    intr_register_ext (0x20, timer_interrupt, "8254 Timer");
  40 +
  41 +  list_init (&wait_list);
  42  }
  43
  44  /* Calibrates loops_per_tick, used to implement brief delays. */
  45 @@ -87,15 +92,36 @@ timer_elapsed (int64_t then)
  46    return timer_ticks () - then;
  47  }
  48
  49 +/* Compares two threads based on their wake-up times. */
  50 +static bool
  51 +compare_threads_by_wakeup_time (const struct list_elem *a_,
  52 +                                const struct list_elem *b_,
  53 +                                void *aux UNUSED)
  54 +{
  55 +  const struct thread *a = list_entry (a_, struct thread, timer_elem);
  56 +  const struct thread *b = list_entry (b_, struct thread, timer_elem);
  57 +
  58 +  return a->wakeup_time < b->wakeup_time;
  59 +}
  60 +
  61  /* Suspends execution for approximately TICKS timer ticks. */
  62  void
  63  timer_sleep (int64_t ticks)
  64  {
  65 -  int64_t start = timer_ticks ();
  66 +  struct thread *t = thread_current ();
  67 +
  68 +  /* Schedule our wake-up time. */
  69 +  t->wakeup_time = timer_ticks () + ticks;
  70
  71 +  /* Atomically insert the current thread into the wait list. */
  72    ASSERT (intr_get_level () == INTR_ON);
  73 -  while (timer_elapsed (start) < ticks)
  74 -    thread_yield ();
  75 +  intr_disable ();
  76 +  list_insert_ordered (&wait_list, &t->timer_elem,
  77 +                       compare_threads_by_wakeup_time, NULL);
  78 +  intr_enable ();
  79 +
  80 +  /* Wait. */
  81 +  sema_down (&t->timer_sema);
  82  }
  83
  84  /* Suspends execution for approximately MS milliseconds. */
  85 @@ -132,6 +158,16 @@ timer_interrupt (struct intr_frame *args
  86  {
  87    ticks++;
  88    thread_tick ();
  89 +
  90 +  while (!list_empty (&wait_list))
  91 +    {
  92 +      struct thread *t = list_entry (list_front (&wait_list),
  93 +                                     struct thread, timer_elem);
  94 +      if (ticks < t->wakeup_time)
  95 +        break;
  96 +      sema_up (&t->timer_sema);
  97 +      list_pop_front (&wait_list);
  98 +    }
  99  }
 100
 101  /* Returns true if LOOPS iterations waits for more than one timer
 102 diff -u src/filesys/Make.vars~ src/filesys/Make.vars
 103 --- src/filesys/Make.vars~ 2005-05-24 14:46:45.000000000 -0700
 104 +++ src/filesys/Make.vars 2005-06-16 15:09:31.000000000 -0700
 105 @@ -6,7 +6,7 @@ KERNEL_SUBDIRS = threads devices lib lib
 106  GRADING_FILE = $(SRCDIR)/tests/filesys/Grading.no-vm
 107
 108  # Uncomment the lines below to enable VM.
 109 -#os.dsk: DEFINES += -DVM
 110 -#KERNEL_SUBDIRS += vm
 111 -#TEST_SUBDIRS += tests/vm
 112 -#GRADING_FILE = $(SRCDIR)/tests/filesys/Grading.with-vm
 113 +os.dsk: DEFINES += -DVM
 114 +KERNEL_SUBDIRS += vm
 115 +TEST_SUBDIRS += tests/vm
 116 +GRADING_FILE = $(SRCDIR)/tests/filesys/Grading.with-vm
 117 diff -u src/filesys/cache.c~ src/filesys/cache.c
 118 --- src/filesys/cache.c~ 1969-12-31 16:00:00.000000000 -0800
 119 +++ src/filesys/cache.c 2005-06-16 15:09:31.000000000 -0700
 120 @@ -0,0 +1,473 @@
 121 +#include "filesys/cache.h"
 122 +#include <debug.h>
 123 +#include <string.h>
 124 +#include "filesys/filesys.h"
 125 +#include "devices/disk.h"
 126 +#include "devices/timer.h"
 127 +#include "threads/malloc.h"
 128 +#include "threads/synch.h"
 129 +#include "threads/thread.h"
 130 +
 131 +#define INVALID_SECTOR ((disk_sector_t) -1)
 132 +
 133 +/* A cached block. */
 134 +struct cache_block
 135 +  {
 136 +    /* Locking to prevent eviction. */
 137 +    struct lock block_lock;                    /* Protects fields in group. */
 138 +    struct condition no_readers_or_writers; /* readers == 0 && writers == 0 */
 139 +    struct condition no_writers;                            /* writers == 0 */
 140 +    int readers, read_waiters;          /* # of readers, # waiting to read. */
 141 +    int writers, write_waiters; /* # of writers (<= 1), # waiting to write. */
 142 +
 143 +    /* Sector number.  INVALID_SECTOR indicates a free cache block.
 144 +
 145 +       Changing from free to allocated requires cache_sync.
 146 +
 147 +       Changing from allocated to free requires block_lock, block
 148 +       must be up-to-date and not dirty, and no one may be
 149 +       waiting on it. */
 150 +    disk_sector_t sector;
 151 +
 152 +    /* Is data[] correct?
 153 +       Requires write lock or data_lock. */
 154 +    bool up_to_date;
 155 +
 156 +    /* Does data[] need to be written back to disk?
 157 +       Valid only when up-to-date.
 158 +       Requires read lock or write lock or data_lock. */
 159 +    bool dirty;
 160 +
 161 +    /* Sector data.
 162 +       Access to data[] requires up-to-date and read or write lock.
 163 +       Bringing up-to-date requires write lock or data_lock. */
 164 +    struct lock data_lock;              /* Protects fields in group. */
 165 +    uint8_t data[DISK_SECTOR_SIZE];     /* Disk data. */
 166 +  };
 167 +
 168 +/* Cache. */
 169 +#define CACHE_CNT 64
 170 +struct cache_block cache[CACHE_CNT];
 171 +
 172 +/* Cache lock.
 173 +
 174 +   Required to allocate a cache block to a sector, to prevent a
 175 +   single sector being allocated two different cache blocks.
 176 +
 177 +   Required to search the cache for a sector, to prevent the
 178 +   sector from being added while the search is ongoing.
 179 +
 180 +   Protects hand. */
 181 +struct lock cache_sync;
 182 +
 183 +/* Cache eviction hand.
 184 +   Protected by cache_sync. */
 185 +static int hand = 0;
 186 +
 187 +static void flushd_init (void);
 188 +static void readaheadd_init (void);
 189 +static void readaheadd_submit (disk_sector_t sector);
 190 +\f
 191 +/* Initializes cache. */
 192 +void
 193 +cache_init (void)
 194 +{
 195 +  int i;
 196 +
 197 +  lock_init (&cache_sync);
 198 +  for (i = 0; i < CACHE_CNT; i++)
 199 +    {
 200 +      struct cache_block *b = &cache[i];
 201 +      lock_init (&b->block_lock);
 202 +      cond_init (&b->no_readers_or_writers);
 203 +      cond_init (&b->no_writers);
 204 +      b->readers = b->read_waiters = 0;
 205 +      b->writers = b->write_waiters = 0;
 206 +      b->sector = INVALID_SECTOR;
 207 +      lock_init (&b->data_lock);
 208 +    }
 209 +
 210 +  flushd_init ();
 211 +  readaheadd_init ();
 212 +}
 213 +
 214 +/* Flushes cache to disk. */
 215 +void
 216 +cache_flush (void)
 217 +{
 218 +  int i;
 219 +
 220 +  for (i = 0; i < CACHE_CNT; i++)
 221 +    {
 222 +      struct cache_block *b = &cache[i];
 223 +      disk_sector_t sector;
 224 +
 225 +      lock_acquire (&b->block_lock);
 226 +      sector = b->sector;
 227 +      lock_release (&b->block_lock);
 228 +
 229 +      if (sector == INVALID_SECTOR)
 230 +        continue;
 231 +
 232 +      b = cache_lock (sector, EXCLUSIVE);
 233 +      if (b->up_to_date && b->dirty)
 234 +        {
 235 +          disk_write (filesys_disk, b->sector, b->data);
 236 +          b->dirty = false;
 237 +        }
 238 +      cache_unlock (b);
 239 +    }
 240 +}
 241 +
 242 +/* Locks the given SECTOR into the cache and returns the cache
 243 +   block.
 244 +   If TYPE is EXCLUSIVE, then the block returned will be locked
 245 +   only by the caller.  The calling thread must not already
 246 +   have any lock on the block.
 247 +   If TYPE is NON_EXCLUSIVE, then block returned may be locked by
 248 +   any number of other callers.  The calling thread may already
 249 +   have any number of non-exclusive locks on the block. */
 250 +struct cache_block *
 251 +cache_lock (disk_sector_t sector, enum lock_type type)
 252 +{
 253 +  int i;
 254 +
 255 + try_again:
 256 +  lock_acquire (&cache_sync);
 257 +
 258 +  /* Is the block already in-cache? */
 259 +  for (i = 0; i < CACHE_CNT; i++)
 260 +    {
 261 +      /* Skip any blocks that don't hold SECTOR. */
 262 +      struct cache_block *b = &cache[i];
 263 +      lock_acquire (&b->block_lock);
 264 +      if (b->sector != sector)
 265 +        {
 266 +          lock_release (&b->block_lock);
 267 +          continue;
 268 +        }
 269 +      lock_release (&cache_sync);
 270 +
 271 +      /* Get read or write lock. */
 272 +      if (type == NON_EXCLUSIVE)
 273 +        {
 274 +          /* Lock for read. */
 275 +          b->read_waiters++;
 276 +          if (b->writers || b->write_waiters)
 277 +            do {
 278 +              cond_wait (&b->no_writers, &b->block_lock);
 279 +            } while (b->writers);
 280 +          b->readers++;
 281 +          b->read_waiters--;
 282 +        }
 283 +      else
 284 +        {
 285 +          /* Lock for write. */
 286 +          b->write_waiters++;
 287 +          if (b->readers || b->read_waiters || b->writers)
 288 +            do {
 289 +              cond_wait (&b->no_readers_or_writers, &b->block_lock);
 290 +            } while (b->readers || b->writers);
 291 +          b->writers++;
 292 +          b->write_waiters--;
 293 +        }
 294 +      lock_release (&b->block_lock);
 295 +
 296 +      /* Our sector should have been pinned in the cache while we
 297 +         were waiting.  Make sure. */
 298 +      ASSERT (b->sector == sector);
 299 +
 300 +      return b;
 301 +    }
 302 +
 303 +  /* Not in cache.  Find empty slot.
 304 +     We hold cache_sync. */
 305 +  for (i = 0; i < CACHE_CNT; i++)
 306 +    {
 307 +      struct cache_block *b = &cache[i];
 308 +      lock_acquire (&b->block_lock);
 309 +      if (b->sector == INVALID_SECTOR)
 310 +        {
 311 +          /* Drop block_lock, which is no longer needed because
 312 +             this is the only code that allocates free blocks,
 313 +             and we still have cache_sync.
 314 +
 315 +             We can't drop cache_sync yet because someone else
 316 +             might try to allocate this same block (or read from
 317 +             it) while we're still initializing the block. */
 318 +          lock_release (&b->block_lock);
 319 +
 320 +          b->sector = sector;
 321 +          b->up_to_date = false;
 322 +          ASSERT (b->readers == 0);
 323 +          ASSERT (b->writers == 0);
 324 +          if (type == NON_EXCLUSIVE)
 325 +            b->readers = 1;
 326 +          else
 327 +            b->writers = 1;
 328 +          lock_release (&cache_sync);
 329 +          return b;
 330 +        }
 331 +      lock_release (&b->block_lock);
 332 +    }
 333 +
 334 +  /* No empty slots.  Evict something.
 335 +     We hold cache_sync. */
 336 +  for (i = 0; i < CACHE_CNT; i++)
 337 +    {
 338 +      struct cache_block *b = &cache[hand];
 339 +      if (++hand >= CACHE_CNT)
 340 +        hand = 0;
 341 +
 342 +      /* Try to grab exclusive write access to block. */
 343 +      lock_acquire (&b->block_lock);
 344 +      if (b->readers || b->writers || b->read_waiters || b->write_waiters)
 345 +        {
 346 +          lock_release (&b->block_lock);
 347 +          continue;
 348 +        }
 349 +      b->writers = 1;
 350 +      lock_release (&b->block_lock);
 351 +
 352 +      lock_release (&cache_sync);
 353 +
 354 +      /* Write block to disk if dirty. */
 355 +      if (b->up_to_date && b->dirty)
 356 +        {
 357 +          disk_write (filesys_disk, b->sector, b->data);
 358 +          b->dirty = false;
 359 +        }
 360 +
 361 +      /* Remove block from cache, if possible: someone might have
 362 +         started waiting on it while the lock was released. */
 363 +      lock_acquire (&b->block_lock);
 364 +      b->writers = 0;
 365 +      if (!b->read_waiters && !b->write_waiters)
 366 +        {
 367 +          /* No one is waiting for it, so we can free it. */
 368 +          b->sector = INVALID_SECTOR;
 369 +        }
 370 +      else
 371 +        {
 372 +          /* There is a waiter.  Give it the block. */
 373 +          if (b->read_waiters)
 374 +            cond_broadcast (&b->no_writers, &b->block_lock);
 375 +          else
 376 +            cond_signal (&b->no_readers_or_writers, &b->block_lock);
 377 +        }
 378 +      lock_release (&b->block_lock);
 379 +
 380 +      /* Try again. */
 381 +      goto try_again;
 382 +    }
 383 +
 384 +  /* Wait for cache contention to die down. */
 385 +  lock_release (&cache_sync);
 386 +  timer_sleep (1000);
 387 +  goto try_again;
 388 +}
 389 +
 390 +/* Bring block B up-to-date, by reading it from disk if
 391 +   necessary, and return a pointer to its data.
 392 +   The caller must have an exclusive or non-exclusive lock on
 393 +   B. */
 394 +void *
 395 +cache_read (struct cache_block *b)
 396 +{
 397 +  lock_acquire (&b->data_lock);
 398 +  if (!b->up_to_date)
 399 +    {
 400 +      disk_read (filesys_disk, b->sector, b->data);
 401 +      b->up_to_date = true;
 402 +      b->dirty = false;
 403 +    }
 404 +  lock_release (&b->data_lock);
 405 +
 406 +  return b->data;
 407 +}
 408 +
 409 +/* Zero out block B, without reading it from disk, and return a
 410 +   pointer to the zeroed data.
 411 +   The caller must have an exclusive lock on B. */
 412 +void *
 413 +cache_zero (struct cache_block *b)
 414 +{
 415 +  ASSERT (b->writers);
 416 +  memset (b->data, 0, DISK_SECTOR_SIZE);
 417 +  b->up_to_date = true;
 418 +  b->dirty = true;
 419 +
 420 +  return b->data;
 421 +}
 422 +
 423 +/* Marks block B as dirty, so that it will be written back to
 424 +   disk before eviction.
 425 +   The caller must have a read or write lock on B,
 426 +   and B must be up-to-date. */
 427 +void
 428 +cache_dirty (struct cache_block *b)
 429 +{
 430 +  ASSERT (b->up_to_date);
 431 +  b->dirty = true;
 432 +}
 433 +
 434 +/* Unlocks block B.
 435 +   If B is no longer locked by any thread, then it becomes a
 436 +   candidate for immediate eviction. */
 437 +void
 438 +cache_unlock (struct cache_block *b)
 439 +{
 440 +  lock_acquire (&b->block_lock);
 441 +  if (b->readers)
 442 +    {
 443 +      ASSERT (b->writers == 0);
 444 +      if (--b->readers == 0)
 445 +        cond_signal (&b->no_readers_or_writers, &b->block_lock);
 446 +    }
 447 +  else if (b->writers)
 448 +    {
 449 +      ASSERT (b->readers == 0);
 450 +      ASSERT (b->writers == 1);
 451 +      b->writers--;
 452 +      if (b->read_waiters)
 453 +        cond_broadcast (&b->no_writers, &b->block_lock);
 454 +      else
 455 +        cond_signal (&b->no_readers_or_writers, &b->block_lock);
 456 +    }
 457 +  else
 458 +    NOT_REACHED ();
 459 +  lock_release (&b->block_lock);
 460 +}
 461 +
 462 +/* If SECTOR is in the cache, evicts it immediately without
 463 +   writing it back to disk (even if dirty).
 464 +   The block must be entirely unused. */
 465 +void
 466 +cache_free (disk_sector_t sector)
 467 +{
 468 +  int i;
 469 +
 470 +  lock_acquire (&cache_sync);
 471 +  for (i = 0; i < CACHE_CNT; i++)
 472 +    {
 473 +      struct cache_block *b = &cache[i];
 474 +
 475 +      lock_acquire (&b->block_lock);
 476 +      if (b->sector == sector)
 477 +        {
 478 +          lock_release (&cache_sync);
 479 +
 480 +          /* Only invalidate the block if it's unused.  That
 481 +             should be the normal case, but it could be part of a
 482 +             read-ahead (in readaheadd()) or write-behind (in
 483 +             cache_flush()). */
 484 +          if (b->readers == 0 && b->read_waiters == 0
 485 +              && b->writers == 0 && b->write_waiters == 0)
 486 +            b->sector = INVALID_SECTOR;
 487 +
 488 +          lock_release (&b->block_lock);
 489 +          return;
 490 +        }
 491 +      lock_release (&b->block_lock);
 492 +    }
 493 +  lock_release (&cache_sync);
 494 +}
 495 +
 496 +void
 497 +cache_readahead (disk_sector_t sector)
 498 +{
 499 +  readaheadd_submit (sector);
 500 +}
 501 +\f
 502 +/* Flush daemon. */
 503 +
 504 +static void flushd (void *aux);
 505 +
 506 +/* Initializes flush daemon. */
 507 +static void
 508 +flushd_init (void)
 509 +{
 510 +  thread_create ("flushd", PRI_MIN, flushd, NULL);
 511 +}
 512 +
 513 +/* Flush daemon thread. */
 514 +static void
 515 +flushd (void *aux UNUSED)
 516 +{
 517 +  for (;;)
 518 +    {
 519 +      timer_msleep (30 * 1000);
 520 +      cache_flush ();
 521 +    }
 522 +}
 523 +\f
 524 +/* A block to read ahead. */
 525 +struct readahead_block
 526 +  {
 527 +    struct list_elem list_elem;         /* readahead_list element. */
 528 +    disk_sector_t sector;               /* Sector to read. */
 529 +  };
 530 +
 531 +/* Protects readahead_list.
 532 +   Monitor lock for readahead_list_nonempty. */
 533 +static struct lock readahead_lock;
 534 +
 535 +/* Signaled when a block is added to readahead_list. */
 536 +static struct condition readahead_list_nonempty;
 537 +
 538 +/* List of blocks for read-ahead. */
 539 +static struct list readahead_list;
 540 +
 541 +static void readaheadd (void *aux);
 542 +
 543 +/* Initialize read-ahead daemon. */
 544 +static void
 545 +readaheadd_init (void)
 546 +{
 547 +  lock_init (&readahead_lock);
 548 +  cond_init (&readahead_list_nonempty);
 549 +  list_init (&readahead_list);
 550 +  thread_create ("readaheadd", PRI_MIN, readaheadd, NULL);
 551 +}
 552 +
 553 +/* Adds SECTOR to the read-ahead queue. */
 554 +static void
 555 +readaheadd_submit (disk_sector_t sector)
 556 +{
 557 +  /* Allocate readahead block. */
 558 +  struct readahead_block *block = malloc (sizeof *block);
 559 +  if (block == NULL)
 560 +    return;
 561 +  block->sector = sector;
 562 +
 563 +  /* Add block to list. */
 564 +  lock_acquire (&readahead_lock);
 565 +  list_push_back (&readahead_list, &block->list_elem);
 566 +  cond_signal (&readahead_list_nonempty, &readahead_lock);
 567 +  lock_release (&readahead_lock);
 568 +}
 569 +
 570 +/* Read-ahead daemon. */
 571 +static void
 572 +readaheadd (void *aux UNUSED)
 573 +{
 574 +  for (;;)
 575 +    {
 576 +      struct readahead_block *ra_block;
 577 +      struct cache_block *cache_block;
 578 +
 579 +      /* Get readahead block from list. */
 580 +      lock_acquire (&readahead_lock);
 581 +      while (list_empty (&readahead_list))
 582 +        cond_wait (&readahead_list_nonempty, &readahead_lock);
 583 +      ra_block = list_entry (list_pop_front (&readahead_list),
 584 +                             struct readahead_block, list_elem);
 585 +      lock_release (&readahead_lock);
 586 +
 587 +      /* Read block into cache. */
 588 +      cache_block = cache_lock (ra_block->sector, NON_EXCLUSIVE);
 589 +      cache_read (cache_block);
 590 +      cache_unlock (cache_block);
 591 +      free (ra_block);
 592 +    }
 593 +}
 594 diff -u src/filesys/cache.h~ src/filesys/cache.h
 595 --- src/filesys/cache.h~ 1969-12-31 16:00:00.000000000 -0800
 596 +++ src/filesys/cache.h 2005-06-16 15:09:31.000000000 -0700
 597 @@ -0,0 +1,23 @@
 598 +#ifndef FILESYS_CACHE_H
 599 +#define FILESYS_CACHE_H
 600 +
 601 +#include "devices/disk.h"
 602 +
 603 +/* Type of block lock. */
 604 +enum lock_type
 605 +  {
 606 +    NON_EXCLUSIVE,     /* Any number of lockers. */
 607 +    EXCLUSIVE          /* Only one locker. */
 608 +  };
 609 +
 610 +void cache_init (void);
 611 +void cache_flush (void);
 612 +struct cache_block *cache_lock (disk_sector_t, enum lock_type);
 613 +void *cache_read (struct cache_block *);
 614 +void *cache_zero (struct cache_block *);
 615 +void cache_dirty (struct cache_block *);
 616 +void cache_unlock (struct cache_block *);
 617 +void cache_free (disk_sector_t);
 618 +void cache_readahead (disk_sector_t);
 619 +
 620 +#endif /* filesys/cache.h */
 621 diff -u src/filesys/directory.c~ src/filesys/directory.c
 622 --- src/filesys/directory.c~ 2005-06-16 21:50:20.000000000 -0700
 623 +++ src/filesys/directory.c 2005-06-16 21:09:01.000000000 -0700
 624 @@ -3,12 +3,17 @@
 625  #include <string.h>
 626  #include <list.h>
 627  #include "filesys/filesys.h"
 628 +#include "filesys/fsutil.h"
 629  #include "filesys/inode.h"
 630  #include "threads/malloc.h"
 631 +#include "threads/synch.h"
 632
 633  /* A directory. */
 634  struct dir
 635    {
 636 +    struct list_elem list_elem;         /* open_dirs list element. */
 637 +    struct lock dir_lock;               /* Protects inode. */
 638 +    int open_cnt;                       /* Number of openers. */
 639      struct inode *inode;                /* Backing store. */
 640    };
 641
 642 @@ -20,15 +25,21 @@ struct dir_entry
 643      bool in_use;                        /* In use or free? */
 644    };
 645
 646 -/* Creates a directory with space for ENTRY_CNT entries in the
 647 -   given SECTOR.  Returns true if successful, false on failure. */
 648 -bool
 649 -dir_create (disk_sector_t sector, size_t entry_cnt)
 650 +/* List of all open directories. */
 651 +static struct list open_dirs;
 652 +
 653 +/* Protects open_dirs additions or removals. */
 654 +static struct lock open_dirs_lock;
 655 +
 656 +/* Initializes directory modules. */
 657 +void
 658 +dir_init (void)
 659  {
 660 -  return inode_create (sector, entry_cnt * sizeof (struct dir_entry));
 661 +  list_init (&open_dirs);
 662 +  lock_init (&open_dirs_lock);
 663  }
 664
 665 -/* Opens the directory in the given INODE, of which it takes
 666 +/* Opens the directory for the given INODE, of which it takes
 667     ownership, and sets *DIRP to the new directory or a null
 668     pointer on failure.  Return true if successful, false on
 669     failure. */
 670 @@ -36,19 +47,46 @@ bool
 671  dir_open (struct inode *inode, struct dir **dirp)
 672  {
 673    struct dir *dir = NULL;
 674 +  struct list_elem *e;
 675
 676    ASSERT (dirp != NULL);
 677
 678 -  if (inode != NULL)
 679 +  lock_acquire (&open_dirs_lock);
 680 +
 681 +  if (inode == NULL)
 682 +    goto done;
 683 +
 684 +  /* Inode must refer to directory. */
 685 +  if (inode_get_type (inode) != DIR_INODE)
 686 +    goto done;
 687 +
 688 +  /* Check whether this directory is already open. */
 689 +  for (e = list_begin (&open_dirs); e != list_end (&open_dirs);
 690 +       e = list_next (e))
 691      {
 692 -      dir = malloc (sizeof *dir);
 693 -      if (dir != NULL)
 694 -        dir->inode = inode;
 695 +      dir = list_entry (e, struct dir, list_elem);
 696 +      if (dir->inode == inode)
 697 +        {
 698 +          dir->open_cnt++;
 699 +          goto done;
 700 +        }
 701 +    }
 702 +
 703 +  /* Create new directory. */
 704 +  dir = calloc (1, sizeof *dir);
 705 +  if (dir != NULL)
 706 +    {
 707 +      list_push_front (&open_dirs, &dir->list_elem);
 708 +      lock_init (&dir->dir_lock);
 709 +      dir->open_cnt = 1;
 710 +      dir->inode = inode;
 711 +      inode_reopen (dir->inode);
 712      }
 713
 714 + done:
 715    *dirp = dir;
 716 -  if (dir == NULL)
 717 -    inode_close (inode);
 718 +  inode_close (inode);
 719 +  lock_release (&open_dirs_lock);
 720    return dir != NULL;
 721  }
 722
 723 @@ -61,22 +99,34 @@ dir_open_root (struct dir **dirp)
 724    return dir_open (inode_open (ROOT_DIR_SECTOR), dirp);
 725  }
 726
 727 +/* Re-opens DIR and returns true. */
 728 +bool
 729 +dir_reopen (struct dir *dir)
 730 +{
 731 +  dir->open_cnt++;
 732 +  return true;
 733 +}
 734 +
 735  /* Destroys DIR and frees associated resources. */
 736  void
 737  dir_close (struct dir *dir)
 738  {
 739 -  if (dir != NULL)
 740 +  if (dir == NULL)
 741 +    return;
 742 +
 743 +  lock_acquire (&open_dirs_lock);
 744 +  if (--dir->open_cnt == 0)
 745      {
 746 +      list_remove (&dir->list_elem);
 747        inode_close (dir->inode);
 748        free (dir);
 749      }
 750 +  lock_release (&open_dirs_lock);
 751  }
 752
 753  /* Searches DIR for a file with the given NAME.
 754 -   If successful, returns true, sets *EP to the directory entry
 755 -   if EP is non-null, and sets *OFSP to the byte offset of the
 756 -   directory entry if OFSP is non-null.
 757 -   otherwise, returns false and ignores EP and OFSP. */
 758 +   If successful, returns the file's entry;
 759 +   otherwise, returns a null pointer. */
 760  static bool
 761  lookup (const struct dir *dir, const char *name,
 762          struct dir_entry *ep, off_t *ofsp)
 763 @@ -113,10 +163,12 @@ dir_lookup (const struct dir *dir, const
 764    ASSERT (dir != NULL);
 765    ASSERT (name != NULL);
 766
 767 +  lock_acquire ((struct lock *) &dir->dir_lock);
 768    if (lookup (dir, name, &e, NULL))
 769      *inode = inode_open (e.inode_sector);
 770    else
 771      *inode = NULL;
 772 +  lock_release ((struct lock *)&dir->dir_lock);
 773
 774    return *inode != NULL;
 775  }
 776 @@ -138,10 +190,11 @@ dir_add (struct dir *dir, const char *na
 777    ASSERT (name != NULL);
 778
 779    /* Check NAME for validity. */
 780 -  if (*name == '\0' || strlen (name) > NAME_MAX)
 781 +  if (*name == '\0' || strchr (name, '/') || strlen (name) > NAME_MAX)
 782      return false;
 783
 784    /* Check that NAME is not in use. */
 785 +  lock_acquire (&dir->dir_lock);
 786    if (lookup (dir, name, NULL, NULL))
 787      goto done;
 788
 789 @@ -164,6 +217,7 @@ dir_add (struct dir *dir, const char *na
 790    success = inode_write_at (dir->inode, &e, sizeof e, ofs) == sizeof e;
 791
 792   done:
 793 +  lock_release (&dir->dir_lock);
 794    return success;
 795  }
 796
 797 @@ -182,12 +236,14 @@ dir_remove (struct dir *dir, const char
 798    ASSERT (name != NULL);
 799
 800    /* Find directory entry. */
 801 +  lock_acquire (&dir->dir_lock);
 802    if (!lookup (dir, name, &e, &ofs))
 803      goto done;
 804
 805 -  /* Open inode. */
 806 +  /* Open inode and verify that it is not an in-use directory. */
 807    inode = inode_open (e.inode_sector);
 808 -  if (inode == NULL)
 809 +  if (inode == NULL
 810 +      || (inode_get_type (inode) == DIR_INODE && inode_open_cnt (inode) != 1))
 811      goto done;
 812
 813    /* Erase directory entry. */
 814 @@ -201,6 +257,7 @@ dir_remove (struct dir *dir, const char
 815
 816   done:
 817    inode_close (inode);
 818 +  lock_release (&dir->dir_lock);
 819    return success;
 820  }
 821
 822 @@ -211,8 +268,10 @@ dir_list (const struct dir *dir)
 823    struct dir_entry e;
 824    size_t ofs;
 825
 826 +  lock_acquire ((struct lock *) &dir->dir_lock);
 827    for (ofs = 0; inode_read_at (dir->inode, &e, sizeof e, ofs) == sizeof e;
 828         ofs += sizeof e)
 829      if (e.in_use)
 830        printf ("%s\n", e.name);
 831 +  lock_release ((struct lock *) &dir->dir_lock);
 832  }
 833 diff -u src/filesys/directory.h~ src/filesys/directory.h
 834 --- src/filesys/directory.h~ 2005-06-16 21:50:20.000000000 -0700
 835 +++ src/filesys/directory.h 2005-06-16 15:09:31.000000000 -0700
 836 @@ -13,9 +13,10 @@
 837
 838  struct inode;
 839  struct dir;
 840 -bool dir_create (disk_sector_t sector, size_t entry_cnt);
 841 +void dir_init (void);
 842  bool dir_open (struct inode *, struct dir **);
 843  bool dir_open_root (struct dir **);
 844 +bool dir_reopen (struct dir *);
 845  void dir_close (struct dir *);
 846  bool dir_lookup (const struct dir *, const char *name, struct inode **);
 847  bool dir_add (struct dir *, const char *name, disk_sector_t);
 848 diff -u src/filesys/file.c~ src/filesys/file.c
 849 --- src/filesys/file.c~ 2005-06-16 21:50:20.000000000 -0700
 850 +++ src/filesys/file.c 2005-06-16 21:02:34.000000000 -0700
 851 @@ -1,6 +1,8 @@
 852  #include "filesys/file.h"
 853  #include <debug.h>
 854 +#include "filesys/directory.h"
 855  #include "filesys/inode.h"
 856 +#include "filesys/filesys.h"
 857  #include "threads/malloc.h"
 858
 859  /* An open file. */
 860 @@ -18,7 +20,7 @@ struct file *
 861  file_open (struct inode *inode)
 862  {
 863    struct file *file = calloc (1, sizeof *file);
 864 -  if (inode != NULL && file != NULL)
 865 +  if (inode != NULL && file != NULL && inode_get_type (inode) == FILE_INODE)
 866      {
 867        file->inode = inode;
 868        file->pos = 0;
 869 diff -u src/filesys/filesys.c~ src/filesys/filesys.c
 870 --- src/filesys/filesys.c~ 2005-06-16 21:50:20.000000000 -0700
 871 +++ src/filesys/filesys.c 2005-06-16 21:03:07.000000000 -0700
 872 @@ -2,11 +2,13 @@
 873  #include <debug.h>
 874  #include <stdio.h>
 875  #include <string.h>
 876 +#include "filesys/cache.h"
 877  #include "filesys/file.h"
 878  #include "filesys/free-map.h"
 879  #include "filesys/inode.h"
 880  #include "filesys/directory.h"
 881  #include "devices/disk.h"
 882 +#include "threads/thread.h"
 883
 884  /* The disk that contains the filesystem. */
 885  struct disk *filesys_disk;
 886 @@ -23,6 +24,8 @@ filesys_init (bool format)
 887      PANIC ("hd0:1 (hdb) not present, filesystem initialization failed");
 888
 889    inode_init ();
 890 +  dir_init ();
 891 +  cache_init ();
 892    free_map_init ();
 893
 894    if (format)
 895 @@ -37,6 +40,103 @@ void
 896  filesys_done (void)
 897  {
 898    free_map_close ();
 899 +  cache_flush ();
 900 +}
 901 +\f
 902 +/* Extracts a file name part from *SRCP into PART,
 903 +   and updates *SRCP so that the next call will return the next
 904 +   file name part.
 905 +   Returns 1 if successful, 0 at end of string, -1 for a too-long
 906 +   file name part. */
 907 +static int
 908 +get_next_part (char part[NAME_MAX], const char **srcp)
 909 +{
 910 +  const char *src = *srcp;
 911 +  char *dst = part;
 912 +
 913 +  /* Skip leading slashes.
 914 +     If it's all slashes, we're done. */
 915 +  while (*src == '/')
 916 +    src++;
 917 +  if (*src == '\0')
 918 +    return 0;
 919 +
 920 +  /* Copy up to NAME_MAX character from SRC to DST.
 921 +     Add null terminator. */
 922 +  while (*src != '/' && *src != '\0')
 923 +    {
 924 +      if (dst < part + NAME_MAX)
 925 +        *dst++ = *src;
 926 +      else
 927 +        return -1;
 928 +      src++;
 929 +    }
 930 +  *dst = '\0';
 931 +
 932 +  /* Advance source pointer. */
 933 +  *srcp = src;
 934 +  return 1;
 935 +}
 936 +
 937 +/* Resolves relative or absolute file NAME.
 938 +   Returns true if successful, false on failure.
 939 +   Stores the directory corresponding to the name into *DIRP,
 940 +   and the file name part into BASENAME. */
 941 +static bool
 942 +resolve_name (const char *name,
 943 +              struct dir **dirp, char basename[NAME_MAX + 1])
 944 +{
 945 +  struct dir *dir = NULL;
 946 +  struct inode *inode;
 947 +  const char *cp;
 948 +  char part[NAME_MAX + 1], next_part[NAME_MAX + 1];
 949 +  int ok;
 950 +
 951 +  /* Find starting directory. */
 952 +  if (name[0] == '/' || thread_current ()->wd == NULL)
 953 +    {
 954 +      if (!dir_open_root (&dir))
 955 +        goto error;
 956 +    }
 957 +  else
 958 +    {
 959 +      if (!dir_reopen (thread_current ()->wd))
 960 +        goto error;
 961 +      dir = thread_current ()->wd;
 962 +    }
 963 +
 964 +  /* Get first name part. */
 965 +  cp = name;
 966 +  if (get_next_part (part, &cp) <= 0)
 967 +    goto error;
 968 +
 969 +  /* As long as another part follows the current one,
 970 +     traverse down another directory. */
 971 +  while ((ok = get_next_part (next_part, &cp)) > 0)
 972 +    {
 973 +      if (!dir_lookup (dir, part, &inode))
 974 +        goto error;
 975 +
 976 +      dir_close (dir);
 977 +      if (!dir_open (inode, &dir))
 978 +        goto error;
 979 +
 980 +      strlcpy (part, next_part, NAME_MAX + 1);
 981 +    }
 982 +  if (ok < 0)
 983 +    goto error;
 984 +
 985 +  /* Return our results. */
 986 +  *dirp = dir;
 987 +  strlcpy (basename, part, NAME_MAX + 1);
 988 +  return true;
 989 +
 990 + error:
 991 +  /* Return failure. */
 992 +  dir_close (dir);
 993 +  *dirp = NULL;
 994 +  basename[0] = '\0';
 995 +  return false;
 996  }
 997  \f
 998  /* Creates a file named NAME with the given INITIAL_SIZE.
 999 @@ -44,16 +144,17 @@ filesys_done (void)
1000     Fails if a file named NAME already exists,
1001     or if internal memory allocation fails. */
1002  bool
1003 -filesys_create (const char *name, off_t initial_size)
1004 +filesys_create (const char *name, off_t initial_size, enum inode_type type)
1005  {
1006    struct dir *dir;
1007 +  char basename[NAME_MAX + 1];
1008    disk_sector_t inode_sector = 0;
1009 -  bool success = (dir_open_root (&dir)
1010 -                  && free_map_allocate (1, &inode_sector)
1011 -                  && inode_create (inode_sector, initial_size)
1012 -                  && dir_add (dir, name, inode_sector));
1013 -  if (!success && inode_sector != 0)
1014 -    free_map_release (inode_sector, 1);
1015 +  bool success = (resolve_name (name, &dir, basename)
1016 +                  && free_map_allocate (&inode_sector)
1017 +                  && inode_create (inode_sector, initial_size, type)
1018 +                  && dir_add (dir, basename, inode_sector));
1019 +  if (!success && inode_sector)
1020 +    free_map_release (inode_sector);
1021    dir_close (dir);
1022
1023    return success;
1024 @@ -64,17 +165,18 @@ filesys_create (const char *name, off_t
1025     otherwise.
1026     Fails if no file named NAME exists,
1027     or if an internal memory allocation fails. */
1028 -struct file *
1029 +struct inode *
1030  filesys_open (const char *name)
1031  {
1032    struct dir *dir;
1033 +  char basename[NAME_MAX + 1];
1034    struct inode *inode = NULL;
1035
1036 -  if (dir_open_root (&dir))
1037 -    dir_lookup (dir, name, &inode);
1038 +  if (resolve_name (name, &dir, basename))
1039 +    dir_lookup (dir, basename, &inode);
1040    dir_close (dir);
1041
1042 -  return file_open (inode);
1043 +  return inode;
1044  }
1045
1046  /* Deletes the file named NAME.
1047 @@ -85,13 +187,54 @@ bool
1048  filesys_remove (const char *name)
1049  {
1050    struct dir *dir = NULL;
1051 -  bool success = (dir_open_root (&dir)
1052 -                  && dir_remove (dir, name));
1053 +  char basename[NAME_MAX + 1];
1054 +  bool success = false;
1055 +
1056 +  if (resolve_name (name, &dir, basename))
1057 +    success = dir_remove (dir, basename);
1058    dir_close (dir);
1059
1060    return success;
1061  }
1062
1063 +/* Change current directory to NAME.
1064 +   Return true if successful, false on failure. */
1065 +bool
1066 +filesys_chdir (const char *name)
1067 +{
1068 +  struct dir *dir;
1069 +
1070 +  /* Find new directory. */
1071 +  if (*name == '\0')
1072 +    return false;
1073 +  else if (name[strspn (name, "/")] == '\0')
1074 +    {
1075 +      if (!dir_open_root (&dir))
1076 +        return false;
1077 +    }
1078 +  else
1079 +    {
1080 +      char basename[NAME_MAX + 1];
1081 +      struct inode *base_inode;
1082 +      struct dir *base_dir;
1083 +      if (!resolve_name (name, &dir, basename)
1084 +          || !dir_lookup (dir, basename, &base_inode)
1085 +          || !dir_open (base_inode, &base_dir))
1086 +        {
1087 +          dir_close (dir);
1088 +          return false;
1089 +        }
1090 +      dir_close (dir);
1091 +      dir = base_dir;
1092 +    }
1093 +
1094 +  /* Change current directory. */
1095 +  dir_close (thread_current ()->wd);
1096 +  thread_current ()->wd = dir;
1097 +
1098 +  return true;
1099 +}
1100 +
1101  /* Prints a list of files in the filesystem to the system
1102     console.
1103     Returns true if successful, false on failure,
1104 @@ -99,13 +242,9 @@ filesys_remove (const char *name)
1105  bool
1106  filesys_list (void)
1107  {
1108 -  struct dir *dir = NULL;
1109 -  bool success = dir_open_root (&dir);
1110 -  if (success)
1111 -    dir_list (dir);
1112 -  dir_close (dir);
1113 +  dir_list (thread_current ()->wd);
1114
1115 -  return success;
1116 +  return true;
1117  }
1118  \f
1119  static void must_succeed_function (int, bool) NO_INLINE;
1120 @@ -128,8 +267,8 @@ filesys_self_test (void)
1121      {
1122        /* Create file and check that it contains zeros
1123           throughout the created length. */
1124 -      MUST_SUCCEED (filesys_create ("foo", sizeof s));
1125 -      MUST_SUCCEED ((file = filesys_open ("foo")) != NULL);
1126 +      MUST_SUCCEED (filesys_create ("foo", sizeof s, FILE_INODE));
1127 +      MUST_SUCCEED ((file = file_open (filesys_open ("foo"))) != NULL);
1128        MUST_SUCCEED (file_read (file, s2, sizeof s2) == sizeof s2);
1129        MUST_SUCCEED (memcmp (s2, zeros, sizeof s) == 0);
1130        MUST_SUCCEED (file_tell (file) == sizeof s);
1131 @@ -137,7 +276,7 @@ filesys_self_test (void)
1132        file_close (file);
1133
1134        /* Reopen file and write to it. */
1135 -      MUST_SUCCEED ((file = filesys_open ("foo")) != NULL);
1136 +      MUST_SUCCEED ((file = file_open (filesys_open ("foo"))) != NULL);
1137        MUST_SUCCEED (file_write (file, s, sizeof s) == sizeof s);
1138        MUST_SUCCEED (file_tell (file) == sizeof s);
1139        MUST_SUCCEED (file_length (file) == sizeof s);
1140 @@ -145,7 +284,7 @@ filesys_self_test (void)
1141
1142        /* Reopen file and verify that it reads back correctly.
1143           Delete file while open to check proper semantics. */
1144 -      MUST_SUCCEED ((file = filesys_open ("foo")) != NULL);
1145 +      MUST_SUCCEED ((file = file_open (filesys_open ("foo"))) != NULL);
1146        MUST_SUCCEED (filesys_remove ("foo"));
1147        MUST_SUCCEED (filesys_open ("foo") == NULL);
1148        MUST_SUCCEED (file_read (file, s2, sizeof s) == sizeof s);
1149 @@ -172,9 +311,13 @@ static void
1150  do_format (void)
1151  {
1152    printf ("Formatting filesystem...");
1153 +
1154 +  /* Set up free map. */
1155    free_map_create ();
1156 -  if (!dir_create (ROOT_DIR_SECTOR, 16))
1157 +
1158 +  /* Set up root directory. */
1159 +  if (!inode_create (ROOT_DIR_SECTOR, 0, DIR_INODE))
1160      PANIC ("root directory creation failed");
1161 -  free_map_close ();
1162 +
1163    printf ("done.\n");
1164  }
1165 diff -u src/filesys/filesys.h~ src/filesys/filesys.h
1166 --- src/filesys/filesys.h~ 2005-06-16 21:50:20.000000000 -0700
1167 +++ src/filesys/filesys.h 2005-06-16 20:55:14.000000000 -0700
1168 @@ -3,6 +3,7 @@
1169
1170  #include <stdbool.h>
1171  #include "filesys/off_t.h"
1172 +#include "filesys/inode.h"
1173
1174  /* Sectors of system file inodes. */
1175  #define FREE_MAP_SECTOR 0       /* Free map file inode sector. */
1176 @@ -13,8 +14,8 @@ extern struct disk *filesys_disk;
1177
1178  void filesys_init (bool format);
1179  void filesys_done (void);
1180 -bool filesys_create (const char *name, off_t initial_size);
1181 -struct file *filesys_open (const char *name);
1182 +bool filesys_create (const char *name, off_t initial_size, enum inode_type);
1183 +struct inode *filesys_open (const char *name);
1184  bool filesys_remove (const char *name);
1185  bool filesys_chdir (const char *name);
1186  bool filesys_list (void);
1187 diff -u src/filesys/free-map.c~ src/filesys/free-map.c
1188 --- src/filesys/free-map.c~ 2005-06-16 21:50:20.000000000 -0700
1189 +++ src/filesys/free-map.c 2005-06-16 20:57:13.000000000 -0700
1190 @@ -3,15 +3,18 @@
1191  #include <debug.h>
1192  #include "filesys/file.h"
1193  #include "filesys/filesys.h"
1194 -#include "filesys/inode.h"
1195 +#include "threads/synch.h"
1196
1197  static struct file *free_map_file;   /* Free map file. */
1198  static struct bitmap *free_map;      /* Free map, one bit per disk sector. */
1199 +static struct lock free_map_lock;    /* Mutual exclusion. */
1200
1201  /* Initializes the free map. */
1202  void
1203  free_map_init (void)
1204  {
1205 +  lock_init (&free_map_lock);
1206 +
1207    free_map = bitmap_create (disk_size (filesys_disk));
1208    if (free_map == NULL)
1209      PANIC ("bitmap creation failed--disk is too large");
1210 @@ -19,33 +22,32 @@ free_map_init (void)
1211    bitmap_mark (free_map, ROOT_DIR_SECTOR);
1212  }
1213
1214 -/* Allocates CNT consecutive sectors from the free map and stores
1215 -   the first into *SECTORP.
1216 -   Returns true if successful, false if all sectors were
1217 +/* Allocates a sector from the free map and stores it into
1218 +   *SECTORP.
1219 +   Return true if successful, false if all sectors were
1220     available. */
1221  bool
1222 -free_map_allocate (size_t cnt, disk_sector_t *sectorp)
1223 +free_map_allocate (disk_sector_t *sectorp)
1224  {
1225 -  disk_sector_t sector = bitmap_scan_and_flip (free_map, 0, cnt, false);
1226 -  if (sector != BITMAP_ERROR
1227 -      && free_map_file != NULL
1228 -      && !bitmap_write (free_map, free_map_file))
1229 -    {
1230 -      bitmap_set_multiple (free_map, sector, cnt, false);
1231 -      sector = BITMAP_ERROR;
1232 -    }
1233 -  if (sector != BITMAP_ERROR)
1234 +  size_t sector;
1235 +
1236 +  lock_acquire (&free_map_lock);
1237 +  sector = bitmap_scan_and_flip (free_map, 0, 1, false);
1238 +  lock_release (&free_map_lock);
1239 +
1240 +  if (sector != BITMAP_ERROR)
1241      *sectorp = sector;
1242    return sector != BITMAP_ERROR;
1243  }
1244
1245 -/* Makes CNT sectors starting at SECTOR available for use. */
1246 +/* Makes SECTOR available for use. */
1247  void
1248 -free_map_release (disk_sector_t sector, size_t cnt)
1249 +free_map_release (disk_sector_t sector)
1250  {
1251 -  ASSERT (bitmap_all (free_map, sector, cnt));
1252 -  bitmap_set_multiple (free_map, sector, cnt, false);
1253 -  bitmap_write (free_map, free_map_file);
1254 +  lock_acquire (&free_map_lock);
1255 +  ASSERT (bitmap_test (free_map, sector));
1256 +  bitmap_reset (free_map, sector);
1257 +  lock_release (&free_map_lock);
1258  }
1259
1260  /* Opens the free map file and reads it from disk. */
1261 @@ -63,6 +65,8 @@ free_map_open (void)
1262  void
1263  free_map_close (void)
1264  {
1265 +  if (!bitmap_write (free_map, free_map_file))
1266 +    PANIC ("can't write free map");
1267    file_close (free_map_file);
1268  }
1269
1270 @@ -72,7 +76,7 @@ void
1271  free_map_create (void)
1272  {
1273    /* Create inode. */
1274 -  if (!inode_create (FREE_MAP_SECTOR, bitmap_file_size (free_map)))
1275 +  if (!inode_create (FREE_MAP_SECTOR, bitmap_file_size (free_map), FILE_INODE))
1276      PANIC ("free map creation failed");
1277
1278    /* Write bitmap to file. */
1279 @@ -81,4 +85,5 @@ free_map_create (void)
1280      PANIC ("can't open free map");
1281    if (!bitmap_write (free_map, free_map_file))
1282      PANIC ("can't write free map");
1283 +  file_close (free_map_file);
1284  }
1285 diff -u src/filesys/free-map.h~ src/filesys/free-map.h
1286 --- src/filesys/free-map.h~ 2005-06-16 21:50:20.000000000 -0700
1287 +++ src/filesys/free-map.h 2005-06-16 20:48:04.000000000 -0700
1288 @@ -11,7 +11,7 @@ void free_map_create (void);
1289  void free_map_open (void);
1290  void free_map_close (void);
1291
1292 -bool free_map_allocate (size_t, disk_sector_t *);
1293 -void free_map_release (disk_sector_t, size_t);
1294 +bool free_map_allocate (disk_sector_t *);
1295 +void free_map_release (disk_sector_t);
1296
1297  #endif /* filesys/free-map.h */
1298 diff -u src/filesys/fsutil.c~ src/filesys/fsutil.c
1299 --- src/filesys/fsutil.c~ 2005-06-16 21:50:20.000000000 -0700
1300 +++ src/filesys/fsutil.c 2005-06-16 20:55:13.000000000 -0700
1301 @@ -30,7 +30,7 @@ fsutil_cat (char **argv)
1302    char *buffer;
1303
1304    printf ("Printing '%s' to the console...\n", filename);
1305 -  file = filesys_open (filename);
1306 +  file = file_open (filesys_open (filename));
1307    if (file == NULL)
1308      PANIC ("%s: open failed", filename);
1309    buffer = palloc_get_page (PAL_ASSERT);
1310 @@ -102,9 +102,9 @@ fsutil_put (char **argv)
1311      PANIC ("%s: invalid file size %d", filename, size);
1312
1313    /* Create destination file. */
1314 -  if (!filesys_create (filename, size))
1315 +  if (!filesys_create (filename, size, FILE_INODE))
1316      PANIC ("%s: create failed", filename);
1317 -  dst = filesys_open (filename);
1318 +  dst = file_open (filesys_open (filename));
1319    if (dst == NULL)
1320      PANIC ("%s: open failed", filename);
1321
1322 @@ -154,7 +154,7 @@ fsutil_get (char **argv)
1323      PANIC ("couldn't allocate buffer");
1324
1325    /* Open source file. */
1326 -  src = filesys_open (filename);
1327 +  src = file_open (filesys_open (filename));
1328    if (src == NULL)
1329      PANIC ("%s: open failed", filename);
1330    size = file_length (src);
1331 diff -u src/filesys/inode.c~ src/filesys/inode.c
1332 --- src/filesys/inode.c~ 2005-06-16 21:50:20.000000000 -0700
1333 +++ src/filesys/inode.c 2005-06-16 21:11:24.000000000 -0700
1334 @@ -1,26 +1,41 @@
1335  #include "filesys/inode.h"
1336 +#include <bitmap.h>
1337  #include <list.h>
1338  #include <debug.h>
1339  #include <round.h>
1340 +#include <stdio.h>
1341  #include <string.h>
1342 +#include "filesys/cache.h"
1343  #include "filesys/filesys.h"
1344  #include "filesys/free-map.h"
1345  #include "threads/malloc.h"
1346 +#include "threads/synch.h"
1347
1348  /* Identifies an inode. */
1349  #define INODE_MAGIC 0x494e4f44
1350
1351 +#define DIRECT_CNT 123
1352 +#define INDIRECT_CNT 1
1353 +#define DBL_INDIRECT_CNT 1
1354 +#define SECTOR_CNT (DIRECT_CNT + INDIRECT_CNT + DBL_INDIRECT_CNT)
1355 +
1356 +#define PTRS_PER_SECTOR ((off_t) (DISK_SECTOR_SIZE / sizeof (disk_sector_t)))
1357 +#define INODE_SPAN ((DIRECT_CNT                                              \
1358 +                     + PTRS_PER_SECTOR * INDIRECT_CNT                        \
1359 +                     + PTRS_PER_SECTOR * PTRS_PER_SECTOR * DBL_INDIRECT_CNT) \
1360 +                    * DISK_SECTOR_SIZE)
1361 +
1362  /* On-disk inode.
1363     Must be exactly DISK_SECTOR_SIZE bytes long. */
1364  struct inode_disk
1365    {
1366 -    disk_sector_t start;                /* First data sector. */
1367 +    disk_sector_t sectors[SECTOR_CNT];  /* Sectors. */
1368 +    enum inode_type type;               /* FILE_INODE or DIR_INODE. */
1369      off_t length;                       /* File size in bytes. */
1370      unsigned magic;                     /* Magic number. */
1371 -    uint32_t unused[125];               /* Not used. */
1372    };
1373
1374 -/* Returns the number of sectors to allocate for an inode SIZE
1375 +/* Returns the number of sectors to allocate for an indoe SIZE
1376     bytes long. */
1377  static inline size_t
1378  bytes_to_sectors (off_t size)
1379 @@ -35,33 +49,29 @@ struct inode
1380      disk_sector_t sector;               /* Sector number of disk location. */
1381      int open_cnt;                       /* Number of openers. */
1382      bool removed;                       /* True if deleted, false otherwise. */
1383 +
1384 +    /* Denying writes. */
1385 +    struct lock deny_write_lock;        /* Protects members below. */
1386 +    struct condition no_writers_cond;   /* Signaled when no writers. */
1387      int deny_write_cnt;                 /* 0: writes ok, >0: deny writes. */
1388 -    struct inode_disk data;             /* Inode content. */
1389 +    int writer_cnt;                     /* Number of writers. */
1390    };
1391
1392 -/* Returns the disk sector that contains byte offset POS within
1393 -   INODE.
1394 -   Returns -1 if INODE does not contain data for a byte at offset
1395 -   POS. */
1396 -static disk_sector_t
1397 -byte_to_sector (const struct inode *inode, off_t pos)
1398 -{
1399 -  ASSERT (inode != NULL);
1400 -  if (pos < inode->data.length)
1401 -    return inode->data.start + pos / DISK_SECTOR_SIZE;
1402 -  else
1403 -    return -1;
1404 -}
1405 -
1406  /* List of open inodes, so that opening a single inode twice
1407     returns the same `struct inode'. */
1408  static struct list open_inodes;
1409
1410 +/* Controls access to open_inodes list. */
1411 +static struct lock open_inodes_lock;
1412 +
1413 +static void deallocate_inode (const struct inode *);
1414 +
1415  /* Initializes the inode module. */
1416  void
1417  inode_init (void)
1418  {
1419    list_init (&open_inodes);
1420 +  lock_init (&open_inodes_lock);
1421  }
1422
1423  /* Initializes an inode with LENGTH bytes of data and
1424 @@ -70,35 +80,32 @@ inode_init (void)
1425     Returns true if successful.
1426     Returns false if memory or disk allocation fails. */
1427  bool
1428 -inode_create (disk_sector_t sector, off_t length)
1429 +inode_create (disk_sector_t sector, off_t length, enum inode_type type)
1430  {
1431 -  struct inode_disk *disk_inode = NULL;
1432 -  bool success = false;
1433 +  struct cache_block *block;
1434 +  struct inode_disk *disk_inode;
1435 +  bool success;
1436
1437    ASSERT (length >= 0);
1438 +
1439 +  block = cache_lock (sector, EXCLUSIVE);
1440    ASSERT (sizeof *disk_inode == DISK_SECTOR_SIZE);
1441 +  disk_inode = cache_zero (block);
1442 +  disk_inode->type = type;
1443 +  disk_inode->length = 0;
1444 +  disk_inode->magic = INODE_MAGIC;
1445 +  cache_dirty (block);
1446 +  cache_unlock (block);
1447
1448 -  disk_inode = calloc (1, sizeof *disk_inode);
1449 -  if (disk_inode != NULL)
1450 +  if (length > 0)
1451      {
1452 -      size_t sectors = bytes_to_sectors (length);
1453 -      disk_inode->length = length;
1454 -      disk_inode->magic = INODE_MAGIC;
1455 -      if (free_map_allocate (sectors, &disk_inode->start))
1456 -        {
1457 -          disk_write (filesys_disk, sector, disk_inode);
1458 -          if (sectors > 0)
1459 -            {
1460 -              static char zeros[DISK_SECTOR_SIZE];
1461 -              size_t i;
1462 -
1463 -              for (i = 0; i < sectors; i++)
1464 -                disk_write (filesys_disk, disk_inode->start + i, zeros);
1465 -            }
1466 -          success = true;
1467 -        }
1468 -      free (disk_inode);
1469 +      struct inode *inode = inode_open (sector);
1470 +      success = inode != NULL && inode_write_at (inode, "", 1, length - 1);
1471 +      inode_close (inode);
1472      }
1473 +  else
1474 +    success = true;
1475 +
1476    return success;
1477  }
1478
1479 @@ -112,6 +119,7 @@ inode_open (disk_sector_t sector)
1480    struct inode *inode;
1481
1482    /* Check whether this inode is already open. */
1483 +  lock_acquire (&open_inodes_lock);
1484    for (e = list_begin (&open_inodes); e != list_end (&open_inodes);
1485         e = list_next (e))
1486      {
1487 @@ -119,22 +127,26 @@ inode_open (disk_sector_t sector)
1488        if (inode->sector == sector)
1489          {
1490            inode_reopen (inode);
1491 -          return inode;
1492 +          goto done;
1493          }
1494      }
1495
1496    /* Allocate memory. */
1497    inode = malloc (sizeof *inode);
1498    if (inode == NULL)
1499 -    return NULL;
1500 +    goto done;
1501
1502    /* Initialize. */
1503    list_push_front (&open_inodes, &inode->elem);
1504    inode->sector = sector;
1505    inode->open_cnt = 1;
1506    inode->deny_write_cnt = 0;
1507 +  lock_init (&inode->deny_write_lock);
1508 +  cond_init (&inode->no_writers_cond);
1509    inode->removed = false;
1510 -  disk_read (filesys_disk, inode->sector, &inode->data);
1511 +
1512 + done:
1513 +  lock_release (&open_inodes_lock);
1514    return inode;
1515  }
1516
1517 @@ -147,6 +159,17 @@ inode_reopen (struct inode *inode)
1518    return inode;
1519  }
1520
1521 +/* Returns the type of INODE. */
1522 +enum inode_type
1523 +inode_get_type (const struct inode *inode)
1524 +{
1525 +  struct cache_block *inode_block = cache_lock (inode->sector, NON_EXCLUSIVE);
1526 +  struct inode_disk *disk_inode = cache_read (inode_block);
1527 +  enum inode_type type = disk_inode->type;
1528 +  cache_unlock (inode_block);
1529 +  return type;
1530 +}
1531 +
1532  /* Closes INODE and writes it to disk.
1533     If this was the last reference to INODE, frees its memory.
1534     If INODE was also a removed inode, frees its blocks. */
1535 @@ -158,21 +181,60 @@ inode_close (struct inode *inode)
1536      return;
1537
1538    /* Release resources if this was the last opener. */
1539 +  lock_acquire (&open_inodes_lock);
1540    if (--inode->open_cnt == 0)
1541      {
1542        /* Remove from inode list and release lock. */
1543        list_remove (&inode->elem);
1544 +      lock_release (&open_inodes_lock);
1545
1546        /* Deallocate blocks if removed. */
1547        if (inode->removed)
1548 -        {
1549 -          free_map_release (inode->sector, 1);
1550 -          free_map_release (inode->data.start,
1551 -                            bytes_to_sectors (inode->data.length));
1552 -        }
1553 +        deallocate_inode (inode);
1554
1555        free (inode);
1556      }
1557 +  else
1558 +    lock_release (&open_inodes_lock);
1559 +}
1560 +
1561 +/* Deallocates SECTOR and anything it points to recursively.
1562 +   LEVEL is 2 if SECTOR is doubly indirect,
1563 +   or 1 if SECTOR is indirect,
1564 +   or 0 if SECTOR is a data sector. */
1565 +static void
1566 +deallocate_recursive (disk_sector_t sector, int level)
1567 +{
1568 +  if (level > 0)
1569 +    {
1570 +      struct cache_block *block = cache_lock (sector, EXCLUSIVE);
1571 +      disk_sector_t *pointers = cache_read (block);
1572 +      int i;
1573 +      for (i = 0; i < PTRS_PER_SECTOR; i++)
1574 +        if (pointers[i])
1575 +          deallocate_recursive (sector, level - 1);
1576 +      cache_unlock (block);
1577 +    }
1578 +
1579 +  cache_free (sector);
1580 +  free_map_release (sector);
1581 +}
1582 +
1583 +/* Deallocates the blocks allocated for INODE. */
1584 +static void
1585 +deallocate_inode (const struct inode *inode)
1586 +{
1587 +  struct cache_block *block = cache_lock (inode->sector, EXCLUSIVE);
1588 +  struct inode_disk *disk_inode = cache_read (block);
1589 +  int i;
1590 +  for (i = 0; i < SECTOR_CNT; i++)
1591 +    if (disk_inode->sectors[i])
1592 +      {
1593 +        int level = (i >= DIRECT_CNT) + (i >= DIRECT_CNT + INDIRECT_CNT);
1594 +        deallocate_recursive (disk_inode->sectors[i], level);
1595 +      }
1596 +  cache_unlock (block);
1597 +  deallocate_recursive (inode->sector, 0);
1598  }
1599
1600  /* Marks INODE to be deleted when it is closed by the last caller who
1601 @@ -181,6 +245,156 @@ inode_remove (struct inode *inode)
1602    inode->removed = true;
1603  }
1604
1605 +/* Translates SECTOR_IDX into a sequence of block indexes in
1606 +   OFFSETS and sets *OFFSET_CNT to the number of offsets. */
1607 +static void
1608 +calculate_indices (off_t sector_idx, size_t offsets[], size_t *offset_cnt)
1609 +{
1610 +  /* Handle direct blocks. */
1611 +  if (sector_idx < DIRECT_CNT)
1612 +    {
1613 +      offsets[0] = sector_idx;
1614 +      *offset_cnt = 1;
1615 +      return;
1616 +    }
1617 +  sector_idx -= DIRECT_CNT;
1618 +
1619 +  /* Handle indirect blocks. */
1620 +  if (sector_idx < PTRS_PER_SECTOR * INDIRECT_CNT)
1621 +    {
1622 +      offsets[0] = DIRECT_CNT + sector_idx / PTRS_PER_SECTOR;
1623 +      offsets[1] = sector_idx % PTRS_PER_SECTOR;
1624 +      *offset_cnt = 2;
1625 +      return;
1626 +    }
1627 +  sector_idx -= PTRS_PER_SECTOR * INDIRECT_CNT;
1628 +
1629 +  /* Handle doubly indirect blocks. */
1630 +  if (sector_idx < DBL_INDIRECT_CNT * PTRS_PER_SECTOR * PTRS_PER_SECTOR)
1631 +    {
1632 +      offsets[0] = (DIRECT_CNT + INDIRECT_CNT
1633 +                    + sector_idx / (PTRS_PER_SECTOR * PTRS_PER_SECTOR));
1634 +      offsets[1] = sector_idx / PTRS_PER_SECTOR;
1635 +      offsets[2] = sector_idx % PTRS_PER_SECTOR;
1636 +      *offset_cnt = 3;
1637 +      return;
1638 +    }
1639 +  NOT_REACHED ();
1640 +}
1641 +
1642 +/* Retrieves the data block for the given byte OFFSET in INODE,
1643 +   setting *DATA_BLOCK to the block.
1644 +   Returns true if successful, false on failure.
1645 +   If ALLOCATE is false, then missing blocks will be successful
1646 +   with *DATA_BLOCk set to a null pointer.
1647 +   If ALLOCATE is true, then missing blocks will be allocated.
1648 +   The block returned will be locked, normally non-exclusively,
1649 +   but a newly allocated block will have an exclusive lock. */
1650 +static bool
1651 +get_data_block (struct inode *inode, off_t offset, bool allocate,
1652 +                struct cache_block **data_block)
1653 +{
1654 +  disk_sector_t this_level_sector;
1655 +  size_t offsets[3];
1656 +  size_t offset_cnt;
1657 +  size_t level;
1658 +
1659 +  ASSERT (offset >= 0);
1660 +
1661 +  calculate_indices (offset / DISK_SECTOR_SIZE, offsets, &offset_cnt);
1662 +  level = 0;
1663 +  this_level_sector = inode->sector;
1664 +  for (;;)
1665 +    {
1666 +      struct cache_block *this_level_block;
1667 +      uint32_t *this_level_data;
1668 +
1669 +      struct cache_block *next_level_block;
1670 +
1671 +      /* Check whether the block for the next level is allocated. */
1672 +      this_level_block = cache_lock (this_level_sector, NON_EXCLUSIVE);
1673 +      this_level_data = cache_read (this_level_block);
1674 +      if (this_level_data[offsets[level]] != 0)
1675 +        {
1676 +          /* Yes, it's allocated.  Advance to next level. */
1677 +          this_level_sector = this_level_data[offsets[level]];
1678 +
1679 +          if (++level == offset_cnt)
1680 +            {
1681 +              /* We hit the data block.
1682 +                 Do read-ahead. */
1683 +              if ((level == 0 && offsets[level] + 1 < DIRECT_CNT)
1684 +                  || (level > 0 && offsets[level] + 1 < PTRS_PER_SECTOR))
1685 +                {
1686 +                  uint32_t next_sector = this_level_data[offsets[level] + 1];
1687 +                  if (next_sector && next_sector < disk_size (filesys_disk))
1688 +                    cache_readahead (next_sector);
1689 +                }
1690 +              cache_unlock (this_level_block);
1691 +
1692 +              /* Return block. */
1693 +              *data_block = cache_lock (this_level_sector, NON_EXCLUSIVE);
1694 +              return true;
1695 +            }
1696 +          cache_unlock (this_level_block);
1697 +          continue;
1698 +        }
1699 +      cache_unlock (this_level_block);
1700 +
1701 +      /* No block is allocated.  Nothing is locked.
1702 +         If we're not allocating new blocks, then this is
1703 +         "success" (with all-zero data). */
1704 +      if (!allocate)
1705 +        {
1706 +          *data_block = NULL;
1707 +          return true;
1708 +        }
1709 +
1710 +      /* We need to allocate a new block.
1711 +         Grab an exclusive lock on this level's block so we can
1712 +         insert the new block. */
1713 +      this_level_block = cache_lock (this_level_sector, EXCLUSIVE);
1714 +      this_level_data = cache_read (this_level_block);
1715 +
1716 +      /* Since we released this level's block, someone else might
1717 +         have allocated the block in the meantime.  Recheck. */
1718 +      if (this_level_data[offsets[level]] != 0)
1719 +        {
1720 +          cache_unlock (this_level_block);
1721 +          continue;
1722 +        }
1723 +
1724 +      /* Allocate the new block. */
1725 +      if (!free_map_allocate (&this_level_data[offsets[level]]))
1726 +        {
1727 +          cache_unlock (this_level_block);
1728 +          *data_block = NULL;
1729 +          return false;
1730 +        }
1731 +      cache_dirty (this_level_block);
1732 +
1733 +      /* Lock and clear the new block. */
1734 +      next_level_block = cache_lock (this_level_data[offsets[level]],
1735 +                                     EXCLUSIVE);
1736 +      cache_zero (next_level_block);
1737 +
1738 +      /* Release this level's block.  No one else can access the
1739 +         new block yet, because we have an exclusive lock on it. */
1740 +      cache_unlock (this_level_block);
1741 +
1742 +      /* If this is the final level, then return the new block. */
1743 +      if (level == offset_cnt - 1)
1744 +        {
1745 +          *data_block = next_level_block;
1746 +          return true;
1747 +        }
1748 +
1749 +      /* Otherwise, release the new block and go around again to
1750 +         follow the new pointer. */
1751 +      cache_unlock (next_level_block);
1752 +    }
1753 +}
1754 +
1755  /* Reads SIZE bytes from INODE into BUFFER, starting at position OFFSET.
1756     Returns the number of bytes actually read, which may be less
1757     than SIZE if an error occurs or end of file is reached. */
1758 @@ -189,13 +403,12 @@ inode_read_at (struct inode *inode, void
1759  {
1760    uint8_t *buffer = buffer_;
1761    off_t bytes_read = 0;
1762 -  uint8_t *bounce = NULL;
1763
1764    while (size > 0)
1765      {
1766 -      /* Disk sector to read, starting byte offset within sector. */
1767 -      disk_sector_t sector_idx = byte_to_sector (inode, offset);
1768 +      /* Sector to read, starting byte offset within sector, sector data. */
1769        int sector_ofs = offset % DISK_SECTOR_SIZE;
1770 +      struct cache_block *block;
1771
1772        /* Bytes left in inode, bytes left in sector, lesser of the two. */
1773        off_t inode_left = inode_length (inode) - offset;
1774 @@ -204,26 +417,16 @@ inode_read_at (struct inode *inode, void
1775
1776        /* Number of bytes to actually copy out of this sector. */
1777        int chunk_size = size < min_left ? size : min_left;
1778 -      if (chunk_size <= 0)
1779 +      if (chunk_size <= 0 || !get_data_block (inode, offset, false, &block))
1780          break;
1781
1782 -      if (sector_ofs == 0 && chunk_size == DISK_SECTOR_SIZE)
1783 -        {
1784 -          /* Read full sector directly into caller's buffer. */
1785 -          disk_read (filesys_disk, sector_idx, buffer + bytes_read);
1786 -        }
1787 +      if (block == NULL)
1788 +        memset (buffer + bytes_read, 0, chunk_size);
1789        else
1790          {
1791 -          /* Read sector into bounce buffer, then partially copy
1792 -             into caller's buffer. */
1793 -          if (bounce == NULL)
1794 -            {
1795 -              bounce = malloc (DISK_SECTOR_SIZE);
1796 -              if (bounce == NULL)
1797 -                break;
1798 -            }
1799 -          disk_read (filesys_disk, sector_idx, bounce);
1800 -          memcpy (buffer + bytes_read, bounce + sector_ofs, chunk_size);
1801 +          const uint8_t *sector_data = cache_read (block);
1802 +          memcpy (buffer + bytes_read, sector_data + sector_ofs, chunk_size);
1803 +          cache_unlock (block);
1804          }
1805
1806        /* Advance. */
1807 @@ -231,75 +434,84 @@ inode_read_at (struct inode *inode, void
1808        offset += chunk_size;
1809        bytes_read += chunk_size;
1810      }
1811 -  free (bounce);
1812
1813    return bytes_read;
1814  }
1815
1816 +/* Extends INODE to be at least LENGTH bytes long. */
1817 +static void
1818 +extend_file (struct inode *inode, off_t length)
1819 +{
1820 +  if (length > inode_length (inode))
1821 +    {
1822 +      struct cache_block *inode_block = cache_lock (inode->sector, EXCLUSIVE);
1823 +      struct inode_disk *disk_inode = cache_read (inode_block);
1824 +      if (length > disk_inode->length)
1825 +        {
1826 +          disk_inode->length = length;
1827 +          cache_dirty (inode_block);
1828 +        }
1829 +      cache_unlock (inode_block);
1830 +    }
1831 +}
1832 +
1833  /* Writes SIZE bytes from BUFFER into INODE, starting at OFFSET.
1834     Returns the number of bytes actually written, which may be
1835     less than SIZE if end of file is reached or an error occurs.
1836 -   (Normally a write at end of file would extend the inode, but
1837 -   growth is not yet implemented.) */
1838 +   (Normally a write at end of file would extend the file, but
1839 +   file growth is not yet implemented.) */
1840  off_t
1841  inode_write_at (struct inode *inode, const void *buffer_, off_t size,
1842                  off_t offset)
1843  {
1844    const uint8_t *buffer = buffer_;
1845    off_t bytes_written = 0;
1846 -  uint8_t *bounce = NULL;
1847
1848 -  if (inode->deny_write_cnt)
1849 -    return 0;
1850 +  /* Don't write if writes are denied. */
1851 +  lock_acquire (&inode->deny_write_lock);
1852 +  if (inode->deny_write_cnt)
1853 +    {
1854 +      lock_release (&inode->deny_write_lock);
1855 +      return 0;
1856 +    }
1857 +  inode->writer_cnt++;
1858 +  lock_release (&inode->deny_write_lock);
1859
1860    while (size > 0)
1861      {
1862 -      /* Sector to write, starting byte offset within sector. */
1863 -      off_t sector_idx = byte_to_sector (inode, offset);
1864 +      /* Sector to write, starting byte offset within sector, sector data. */
1865        int sector_ofs = offset % DISK_SECTOR_SIZE;
1866 +      struct cache_block *block;
1867 +      uint8_t *sector_data;
1868
1869 -      /* Bytes left in inode, bytes left in sector, lesser of the two. */
1870 -      off_t inode_left = inode_length (inode) - offset;
1871 +      /* Bytes to max inode size, bytes left in sector, lesser of the two. */
1872 +      off_t inode_left = INODE_SPAN - offset;
1873        int sector_left = DISK_SECTOR_SIZE - sector_ofs;
1874        int min_left = inode_left < sector_left ? inode_left : sector_left;
1875
1876        /* Number of bytes to actually write into this sector. */
1877        int chunk_size = size < min_left ? size : min_left;
1878 -      if (chunk_size <= 0)
1879 -        break;
1880
1881 -      if (sector_ofs == 0 && chunk_size == DISK_SECTOR_SIZE)
1882 -        {
1883 -          /* Write full sector directly to disk. */
1884 -          disk_write (filesys_disk, sector_idx, buffer + bytes_written);
1885 -        }
1886 -      else
1887 -        {
1888 -          /* We need a bounce buffer. */
1889 -          if (bounce == NULL)
1890 -            {
1891 -              bounce = malloc (DISK_SECTOR_SIZE);
1892 -              if (bounce == NULL)
1893 -                break;
1894 -            }
1895 +      if (chunk_size <= 0 || !get_data_block (inode, offset, true, &block))
1896 +        break;
1897
1898 -          /* If the sector contains data before or after the chunk
1899 -             we're writing, then we need to read in the sector
1900 -             first.  Otherwise we start with a sector of all zeros. */
1901 -          if (sector_ofs > 0 || chunk_size < sector_left)
1902 -            disk_read (filesys_disk, sector_idx, bounce);
1903 -          else
1904 -            memset (bounce, 0, DISK_SECTOR_SIZE);
1905 -          memcpy (bounce + sector_ofs, buffer + bytes_written, chunk_size);
1906 -          disk_write (filesys_disk, sector_idx, bounce);
1907 -        }
1908 +      sector_data = cache_read (block);
1909 +      memcpy (sector_data + sector_ofs, buffer + bytes_written, chunk_size);
1910 +      cache_dirty (block);
1911 +      cache_unlock (block);
1912
1913        /* Advance. */
1914        size -= chunk_size;
1915        offset += chunk_size;
1916        bytes_written += chunk_size;
1917      }
1918 -  free (bounce);
1919 +
1920 +  extend_file (inode, offset);
1921 +
1922 +  lock_acquire (&inode->deny_write_lock);
1923 +  if (--inode->writer_cnt == 0)
1924 +    cond_signal (&inode->no_writers_cond, &inode->deny_write_lock);
1925 +  lock_release (&inode->deny_write_lock);
1926
1927    return bytes_written;
1928  }
1929 @@ -309,8 +521,12 @@ inode_write_at (struct inode *inode, con
1930  void
1931  inode_deny_write (struct inode *inode)
1932  {
1933 +  lock_acquire (&inode->deny_write_lock);
1934 +  while (inode->writer_cnt > 0)
1935 +    cond_wait (&inode->no_writers_cond, &inode->deny_write_lock);
1936 +  ASSERT (inode->deny_write_cnt < inode->open_cnt);
1937    inode->deny_write_cnt++;
1938 -  ASSERT (inode->deny_write_cnt <= inode->open_cnt);
1939 +  lock_release (&inode->deny_write_lock);
1940  }
1941
1942  /* Re-enables writes to INODE.
1943 @@ -319,14 +535,33 @@ inode_deny_write (struct inode *inode)
1944  void
1945  inode_allow_write (struct inode *inode)
1946  {
1947 +  lock_acquire (&inode->deny_write_lock);
1948    ASSERT (inode->deny_write_cnt > 0);
1949    ASSERT (inode->deny_write_cnt <= inode->open_cnt);
1950    inode->deny_write_cnt--;
1951 +  lock_release (&inode->deny_write_lock);
1952  }
1953
1954  /* Returns the length, in bytes, of INODE's data. */
1955  off_t
1956  inode_length (const struct inode *inode)
1957  {
1958 -  return inode->data.length;
1959 +  struct cache_block *inode_block = cache_lock (inode->sector, NON_EXCLUSIVE);
1960 +  struct inode_disk *disk_inode = cache_read (inode_block);
1961 +  off_t length = disk_inode->length;
1962 +  cache_unlock (inode_block);
1963 +  return length;
1964 +}
1965 +
1966 +/* Returns the number of openers. */
1967 +int
1968 +inode_open_cnt (const struct inode *inode)
1969 +{
1970 +  int open_cnt;
1971 +
1972 +  lock_acquire (&open_inodes_lock);
1973 +  open_cnt = inode->open_cnt;
1974 +  lock_release (&open_inodes_lock);
1975 +
1976 +  return open_cnt;
1977  }
1978 diff -u src/filesys/inode.h~ src/filesys/inode.h
1979 --- src/filesys/inode.h~ 2005-06-16 21:50:20.000000000 -0700
1980 +++ src/filesys/inode.h 2005-06-16 20:53:47.000000000 -0700
1981 @@ -7,10 +7,18 @@
1982
1983  struct bitmap;
1984
1985 +/* Type of an inode. */
1986 +enum inode_type
1987 +  {
1988 +    FILE_INODE,        /* Ordinary file. */
1989 +    DIR_INODE          /* Directory. */
1990 +  };
1991 +
1992  void inode_init (void);
1993 -bool inode_create (disk_sector_t, off_t);
1994 +bool inode_create (disk_sector_t, off_t, enum inode_type);
1995  struct inode *inode_open (disk_sector_t);
1996  struct inode *inode_reopen (struct inode *);
1997 +enum inode_type inode_get_type (const struct inode *);
1998  void inode_close (struct inode *);
1999  void inode_remove (struct inode *);
2000  off_t inode_read_at (struct inode *, void *, off_t size, off_t offset);
2001 @@ -18,5 +26,6 @@ off_t inode_write_at (struct inode *, co
2002  void inode_deny_write (struct inode *);
2003  void inode_allow_write (struct inode *);
2004  off_t inode_length (const struct inode *);
2005 +int inode_open_cnt (const struct inode *);
2006
2007  #endif /* filesys/inode.h */
2008 diff -u src/lib/kernel/bitmap.h~ src/lib/kernel/bitmap.h
2009 diff -u src/threads/init.c~ src/threads/init.c
2010 --- src/threads/init.c~ 2005-06-14 14:04:06.000000000 -0700
2011 +++ src/threads/init.c 2005-06-16 15:09:31.000000000 -0700
2012 @@ -33,6 +33,8 @@
2013  #include "filesys/filesys.h"
2014  #include "filesys/fsutil.h"
2015  #endif
2016 +#include "vm/frame.h"
2017 +#include "vm/swap.h"
2018
2019  /* Amount of physical memory, in 4 kB pages. */
2020  size_t ram_pages;
2021 @@ -131,6 +133,9 @@ main (void)
2022    filesys_init (format_filesys);
2023  #endif
2024
2025 +  frame_init ();
2026 +  swap_init ();
2027 +
2028    printf ("Boot complete.\n");
2029
2030    /* Run actions specified on kernel command line. */
2031 diff -u src/threads/interrupt.c~ src/threads/interrupt.c
2032 --- src/threads/interrupt.c~ 2005-06-15 15:22:43.000000000 -0700
2033 +++ src/threads/interrupt.c 2005-06-16 15:09:31.000000000 -0700
2034 @@ -343,6 +343,8 @@ intr_handler (struct intr_frame *frame)
2035        in_external_intr = true;
2036        yield_on_return = false;
2037      }
2038 +  else
2039 +    thread_current ()->user_esp = frame->esp;
2040
2041    /* Invoke the interrupt's handler.
2042       If there is no handler, invoke the unexpected interrupt
2043 diff -u src/threads/thread.c~ src/threads/thread.c
2044 --- src/threads/thread.c~ 2005-06-15 14:41:47.000000000 -0700
2045 +++ src/threads/thread.c 2005-06-16 15:09:31.000000000 -0700
2046 @@ -13,6 +13,7 @@
2047  #include "threads/synch.h"
2048  #ifdef USERPROG
2049  #include "userprog/process.h"
2050 +#include "userprog/syscall.h"
2051  #endif
2052
2053  /* Random value for struct thread's `magic' member.
2054 @@ -55,7 +56,8 @@ static void kernel_thread (thread_func *
2055  static void idle (void *aux UNUSED);
2056  static struct thread *running_thread (void);
2057  static struct thread *next_thread_to_run (void);
2058 -static void init_thread (struct thread *, const char *name, int priority);
2059 +static void init_thread (struct thread *, const char *name, int priority,
2060 +                         tid_t);
2061  static bool is_thread (struct thread *) UNUSED;
2062  static void *alloc_frame (struct thread *, size_t size);
2063  static void schedule (void);
2064 @@ -82,9 +84,8 @@ thread_init (void)
2065
2066    /* Set up a thread structure for the running thread. */
2067    initial_thread = running_thread ();
2068 -  init_thread (initial_thread, "main", PRI_DEFAULT);
2069 +  init_thread (initial_thread, "main", PRI_DEFAULT, 0);
2070    initial_thread->status = THREAD_RUNNING;
2071 -  initial_thread->tid = allocate_tid ();
2072  }
2073
2074  /* Starts preemptive thread scheduling by enabling interrupts.
2075 @@ -158,8 +159,8 @@ thread_create (const char *name, int pri
2076      return TID_ERROR;
2077
2078    /* Initialize thread. */
2079 -  init_thread (t, name, priority);
2080 -  tid = t->tid = allocate_tid ();
2081 +  init_thread (t, name, priority, allocate_tid ());
2082 +  tid = t->tid;
2083
2084    /* Stack frame for kernel_thread(). */
2085    kf = alloc_frame (t, sizeof *kf);
2086 @@ -252,16 +253,19 @@ thread_tid (void)
2087  void
2088  thread_exit (void)
2089  {
2090 +  struct thread *t = thread_current ();
2091 +
2092    ASSERT (!intr_context ());
2093
2094 +  syscall_exit ();
2095  #ifdef USERPROG
2096    process_exit ();
2097  #endif
2098 -
2099 +
2100    /* Just set our status to dying and schedule another process.
2101       We will be destroyed during the call to schedule_tail(). */
2102    intr_disable ();
2103 -  thread_current ()->status = THREAD_DYING;
2104 +  t->status = THREAD_DYING;
2105    schedule ();
2106    NOT_REACHED ();
2107  }
2108 @@ -390,17 +394,29 @@ is_thread (struct thread *t)
2109  /* Does basic initialization of T as a blocked thread named
2110     NAME. */
2111  static void
2112 -init_thread (struct thread *t, const char *name, int priority)
2113 +init_thread (struct thread *t, const char *name, int priority, tid_t tid)
2114  {
2115    ASSERT (t != NULL);
2116    ASSERT (PRI_MIN <= priority && priority <= PRI_MAX);
2117    ASSERT (name != NULL);
2118
2119    memset (t, 0, sizeof *t);
2120 +  t->tid = tid;
2121    t->status = THREAD_BLOCKED;
2122    strlcpy (t->name, name, sizeof t->name);
2123    t->stack = (uint8_t *) t + PGSIZE;
2124    t->priority = priority;
2125 +  t->exit_code = -1;
2126 +  t->wait_status = NULL;
2127 +  list_init (&t->children);
2128 +  sema_init (&t->timer_sema, 0);
2129 +  t->pagedir = NULL;
2130 +  t->pages = NULL;
2131 +  t->bin_file = NULL;
2132 +  list_init (&t->fds);
2133 +  list_init (&t->mappings);
2134 +  t->next_handle = 2;
2135 +  t->wd = NULL;
2136    t->magic = THREAD_MAGIC;
2137  }
2138
2139 diff -u src/threads/thread.h~ src/threads/thread.h
2140 --- src/threads/thread.h~ 2005-06-15 14:49:06.000000000 -0700
2141 +++ src/threads/thread.h 2005-06-16 15:09:31.000000000 -0700
2142 @@ -2,8 +2,10 @@
2143  #define THREADS_THREAD_H
2144
2145  #include <debug.h>
2146 +#include <hash.h>
2147  #include <list.h>
2148  #include <stdint.h>
2149 +#include "threads/synch.h"
2150
2151  /* States in a thread's life cycle. */
2152  enum thread_status
2153 @@ -89,18 +91,50 @@ struct thread
2154      uint8_t *stack;                     /* Saved stack pointer. */
2155      int priority;                       /* Priority. */
2156
2157 +    /* Owned by process.c. */
2158 +    int exit_code;                      /* Exit code. */
2159 +    struct wait_status *wait_status;    /* This process's completion status. */
2160 +    struct list children;               /* Completion status of children. */
2161 +
2162      /* Shared between thread.c and synch.c. */
2163      struct list_elem elem;              /* List element. */
2164
2165 -#ifdef USERPROG
2166 +    /* Alarm clock. */
2167 +    int64_t wakeup_time;                /* Time to wake this thread up. */
2168 +    struct list_elem timer_elem;        /* Element in timer_wait_list. */
2169 +    struct semaphore timer_sema;        /* Semaphore. */
2170 +
2171      /* Owned by userprog/process.c. */
2172      uint32_t *pagedir;                  /* Page directory. */
2173 -#endif
2174 +    struct hash *pages;                 /* Page table. */
2175 +    struct file *bin_file;              /* The binary executable. */
2176 +
2177 +    /* Owned by syscall.c. */
2178 +    struct list fds;                    /* List of file descriptors. */
2179 +    struct list mappings;               /* Memory-mapped files. */
2180 +    int next_handle;                    /* Next handle value. */
2181 +    void *user_esp;                     /* User's stack pointer. */
2182 +    struct dir *wd;                     /* Working directory. */
2183
2184      /* Owned by thread.c. */
2185      unsigned magic;                     /* Detects stack overflow. */
2186    };
2187
2188 +/* Tracks the completion of a process.
2189 +   Reference held by both the parent, in its `children' list,
2190 +   and by the child, in its `wait_status' pointer. */
2191 +struct wait_status
2192 +  {
2193 +    struct list_elem elem;              /* `children' list element. */
2194 +    struct lock lock;                   /* Protects ref_cnt. */
2195 +    int ref_cnt;                        /* 2=child and parent both alive,
2196 +                                           1=either child or parent alive,
2197 +                                           0=child and parent both dead. */
2198 +    tid_t tid;                          /* Child thread id. */
2199 +    int exit_code;                      /* Child exit code, if dead. */
2200 +    struct semaphore dead;              /* 1=child alive, 0=child dead. */
2201 +  };
2202 +
2203  void thread_init (void);
2204  void thread_start (void);
2205
2206 diff -u src/userprog/exception.c~ src/userprog/exception.c
2207 --- src/userprog/exception.c~ 2005-06-15 15:14:10.000000000 -0700
2208 +++ src/userprog/exception.c 2005-06-16 15:09:31.000000000 -0700
2209 @@ -4,6 +4,7 @@
2210  #include "userprog/gdt.h"
2211  #include "threads/interrupt.h"
2212  #include "threads/thread.h"
2213 +#include "vm/page.h"
2214
2215  /* Number of page faults processed. */
2216  static long long page_fault_cnt;
2217 @@ -153,9 +154,14 @@ page_fault (struct intr_frame *f)
2218    write = (f->error_code & PF_W) != 0;
2219    user = (f->error_code & PF_U) != 0;
2220
2221 -  /* To implement virtual memory, delete the rest of the function
2222 -     body, and replace it with code that brings in the page to
2223 -     which fault_addr refers. */
2224 +  /* Allow the pager to try to handle it. */
2225 +  if (user && not_present)
2226 +    {
2227 +      if (!page_in (fault_addr))
2228 +        thread_exit ();
2229 +      return;
2230 +    }
2231 +
2232    printf ("Page fault at %p: %s error %s page in %s context.\n",
2233            fault_addr,
2234            not_present ? "not present" : "rights violation",
2235 diff -u src/userprog/pagedir.c~ src/userprog/pagedir.c
2236 --- src/userprog/pagedir.c~ 2005-06-14 13:16:22.000000000 -0700
2237 +++ src/userprog/pagedir.c 2005-06-16 15:09:31.000000000 -0700
2238 @@ -35,15 +35,7 @@ pagedir_destroy (uint32_t *pd)
2239    ASSERT (pd != base_page_dir);
2240    for (pde = pd; pde < pd + pd_no (PHYS_BASE); pde++)
2241      if (*pde & PG_P)
2242 -      {
2243 -        uint32_t *pt = pde_get_pt (*pde);
2244 -        uint32_t *pte;
2245 -
2246 -        for (pte = pt; pte < pt + PGSIZE / sizeof *pte; pte++)
2247 -          if (*pte & PG_P)
2248 -            palloc_free_page (pte_get_page (*pte));
2249 -        palloc_free_page (pt);
2250 -      }
2251 +      palloc_free_page (pde_get_pt (*pde));
2252    palloc_free_page (pd);
2253  }
2254
2255 diff -u src/userprog/process.c~ src/userprog/process.c
2256 --- src/userprog/process.c~ 2005-06-14 13:09:39.000000000 -0700
2257 +++ src/userprog/process.c 2005-06-16 15:09:31.000000000 -0700
2258 @@ -14,11 +14,26 @@
2259  #include "threads/init.h"
2260  #include "threads/interrupt.h"
2261  #include "threads/mmu.h"
2262 +#include "threads/malloc.h"
2263  #include "threads/palloc.h"
2264  #include "threads/thread.h"
2265 +#include "vm/page.h"
2266 +#include "vm/frame.h"
2267
2268  static thread_func execute_thread NO_RETURN;
2269 -static bool load (const char *cmdline, void (**eip) (void), void **esp);
2270 +static bool load (const char *cmd_line, void (**eip) (void), void **esp);
2271 +
2272 +/* Data structure shared between process_execute() in the
2273 +   invoking thread and execute_thread() in the newly invoked
2274 +   thread. */
2275 +struct exec_info
2276 +  {
2277 +    const char *filename;               /* Program to load. */
2278 +    struct semaphore load_done;         /* "Up"ed when loading complete. */
2279 +    struct wait_status *wait_status;    /* Child process. */
2280 +    struct dir *wd;                     /* Working directory. */
2281 +    bool success;                       /* Program successfully loaded? */
2282 +  };
2283
2284  /* Starts a new thread running a user program loaded from
2285     FILENAME.  The new thread may be scheduled (and may even exit)
2286 @@ -27,41 +42,82 @@ static bool load (const char *cmdline, v
2287  tid_t
2288  process_execute (const char *filename)
2289  {
2290 -  char *fn_copy;
2291 +  struct dir *wd = thread_current ()->wd;
2292 +  struct exec_info exec;
2293 +  char thread_name[16];
2294 +  char *save_ptr;
2295    tid_t tid;
2296
2297 -  /* Make a copy of FILENAME.
2298 -     Otherwise there's a race between the caller and load(). */
2299 -  fn_copy = palloc_get_page (0);
2300 -  if (fn_copy == NULL)
2301 +  /* Initialize exec_info. */
2302 +  exec.filename = filename;
2303 +  if (wd)
2304 +    {
2305 +      dir_reopen (wd);
2306 +      exec.wd = wd;
2307 +    }
2308 +  else if (!dir_open_root (&exec.wd))
2309      return TID_ERROR;
2310 -  strlcpy (fn_copy, filename, PGSIZE);
2311 +  sema_init (&exec.load_done, 0);
2312
2313    /* Create a new thread to execute FILENAME. */
2314 -  tid = thread_create (filename, PRI_DEFAULT, execute_thread, fn_copy);
2315 -  if (tid == TID_ERROR)
2316 -    palloc_free_page (fn_copy);
2317 +  strlcpy (thread_name, filename, sizeof thread_name);
2318 +  strtok_r (thread_name, " ", &save_ptr);
2319 +  tid = thread_create (thread_name, PRI_DEFAULT, execute_thread, &exec);
2320 +  if (tid != TID_ERROR)
2321 +    {
2322 +      sema_down (&exec.load_done);
2323 +      if (exec.success)
2324 +        list_push_back (&thread_current ()->children, &exec.wait_status->elem);
2325 +      else
2326 +        {
2327 +          tid = TID_ERROR;
2328 +          /* Don't close exec.wd; child process will have done so. */
2329 +        }
2330 +    }
2331 +  else
2332 +    dir_close (exec.wd);
2333 +
2334    return tid;
2335  }
2336
2337  /* A thread function that loads a user process and starts it
2338     running. */
2339  static void
2340 -execute_thread (void *filename_)
2341 +execute_thread (void *exec_)
2342  {
2343 -  char *filename = filename_;
2344 +  struct exec_info *exec = exec_;
2345    struct intr_frame if_;
2346    bool success;
2347
2348 +  thread_current ()->wd = exec->wd;
2349 +
2350    /* Initialize interrupt frame and load executable. */
2351    memset (&if_, 0, sizeof if_);
2352    if_.gs = if_.fs = if_.es = if_.ds = if_.ss = SEL_UDSEG;
2353    if_.cs = SEL_UCSEG;
2354    if_.eflags = FLAG_IF | FLAG_MBS;
2355 -  success = load (filename, &if_.eip, &if_.esp);
2356 +  success = load (exec->filename, &if_.eip, &if_.esp);
2357 +
2358 +  /* Allocate wait_status. */
2359 +  if (success)
2360 +    {
2361 +      exec->wait_status = thread_current ()->wait_status
2362 +        = malloc (sizeof *exec->wait_status);
2363 +      success = exec->wait_status != NULL;
2364 +    }
2365
2366 -  /* If load failed, quit. */
2367 -  palloc_free_page (filename);
2368 +  /* Initialize wait_status. */
2369 +  if (success)
2370 +    {
2371 +      lock_init (&exec->wait_status->lock);
2372 +      exec->wait_status->ref_cnt = 2;
2373 +      exec->wait_status->tid = thread_current ()->tid;
2374 +      sema_init (&exec->wait_status->dead, 0);
2375 +    }
2376 +
2377 +  /* Notify parent thread and clean up. */
2378 +  exec->success = success;
2379 +  sema_up (&exec->load_done);
2380    if (!success)
2381      thread_exit ();
2382
2383 @@ -75,18 +131,47 @@ execute_thread (void *filename_)
2384    NOT_REACHED ();
2385  }
2386
2387 +/* Releases one reference to CS and, if it is now unreferenced,
2388 +   frees it. */
2389 +static void
2390 +release_child (struct wait_status *cs)
2391 +{
2392 +  int new_ref_cnt;
2393 +
2394 +  lock_acquire (&cs->lock);
2395 +  new_ref_cnt = --cs->ref_cnt;
2396 +  lock_release (&cs->lock);
2397 +
2398 +  if (new_ref_cnt == 0)
2399 +    free (cs);
2400 +}
2401 +
2402  /* Waits for thread TID to die and returns its exit status.  If
2403     it was terminated by the kernel (i.e. killed due to an
2404     exception), returns -1.  If TID is invalid or if it was not a
2405     child of the calling process, or if process_wait() has already
2406     been successfully called for the given TID, returns -1
2407 -   immediately, without waiting.
2408 -
2409 -   This function will be implemented in problem 2-2.  For now, it
2410 -   does nothing. */
2411 +   immediately, without waiting. */
2412  int
2413 -process_wait (tid_t child_tid UNUSED)
2414 +process_wait (tid_t child_tid)
2415  {
2416 +  struct thread *cur = thread_current ();
2417 +  struct list_elem *e;
2418 +
2419 +  for (e = list_begin (&cur->children); e != list_end (&cur->children);
2420 +       e = list_next (e))
2421 +    {
2422 +      struct wait_status *cs = list_entry (e, struct wait_status, elem);
2423 +      if (cs->tid == child_tid)
2424 +        {
2425 +          int exit_code;
2426 +          list_remove (e);
2427 +          sema_down (&cs->dead);
2428 +          exit_code = cs->exit_code;
2429 +          release_child (cs);
2430 +          return exit_code;
2431 +        }
2432 +    }
2433    return -1;
2434  }
2435
2436 @@ -95,8 +180,35 @@ void
2437  process_exit (void)
2438  {
2439    struct thread *cur = thread_current ();
2440 +  struct list_elem *e, *next;
2441    uint32_t *pd;
2442
2443 +  printf ("%s: exit(%d)\n", cur->name, cur->exit_code);
2444 +
2445 +  /* Notify parent that we're dead. */
2446 +  if (cur->wait_status != NULL)
2447 +    {
2448 +      struct wait_status *cs = cur->wait_status;
2449 +      cs->exit_code = cur->exit_code;
2450 +      sema_up (&cs->dead);
2451 +      release_child (cs);
2452 +    }
2453 +
2454 +  /* Free entries of children list. */
2455 +  for (e = list_begin (&cur->children); e != list_end (&cur->children);
2456 +       e = next)
2457 +    {
2458 +      struct wait_status *cs = list_entry (e, struct wait_status, elem);
2459 +      next = list_remove (e);
2460 +      release_child (cs);
2461 +    }
2462 +
2463 +  /* Destroy the page hash table. */
2464 +  page_exit ();
2465 +
2466 +  /* Close executable (and allow writes). */
2467 +  file_close (cur->bin_file);
2468 +
2469    /* Destroy the current process's page directory and switch back
2470       to the kernel-only page directory. */
2471    pd = cur->pagedir;
2472 @@ -194,20 +306,22 @@ struct Elf32_Phdr
2473  #define PF_R 4          /* Readable. */
2474
2475  static bool load_segment (struct file *, const struct Elf32_Phdr *);
2476 -static bool setup_stack (void **esp);
2477 +static bool setup_stack (const char *cmd_line, void **esp);
2478
2479  /* Loads an ELF executable from FILENAME into the current thread.
2480     Stores the executable's entry point into *EIP
2481     and its initial stack pointer into *ESP.
2482     Returns true if successful, false otherwise. */
2483  bool
2484 -load (const char *filename, void (**eip) (void), void **esp)
2485 +load (const char *cmd_line, void (**eip) (void), void **esp)
2486  {
2487    struct thread *t = thread_current ();
2488 +  char filename[NAME_MAX + 2];
2489    struct Elf32_Ehdr ehdr;
2490    struct file *file = NULL;
2491    off_t file_ofs;
2492    bool success = false;
2493 +  char *cp;
2494    int i;
2495
2496    /* Allocate and activate page directory. */
2497 @@ -216,13 +330,28 @@ load (const char *filename, void (**eip)
2498      goto done;
2499    process_activate ();
2500
2501 +  /* Create page hash table. */
2502 +  t->pages = malloc (sizeof *t->pages);
2503 +  if (t->pages == NULL)
2504 +    goto done;
2505 +  hash_init (t->pages, page_hash, page_less, NULL);
2506 +
2507 +  /* Extract filename from command line. */
2508 +  while (*cmd_line == ' ')
2509 +    cmd_line++;
2510 +  strlcpy (filename, cmd_line, sizeof filename);
2511 +  cp = strchr (filename, ' ');
2512 +  if (cp != NULL)
2513 +    *cp = '\0';
2514 +
2515    /* Open executable file. */
2516 -  file = filesys_open (filename);
2517 +  t->bin_file = file = file_open (filesys_open (filename));
2518    if (file == NULL)
2519      {
2520        printf ("load: %s: open failed\n", filename);
2521        goto done;
2522      }
2523 +  file_deny_write (file);
2524
2525    /* Read and verify executable header. */
2526    if (file_read (file, &ehdr, sizeof ehdr) != sizeof ehdr
2527 @@ -271,7 +400,7 @@ load (const char *filename, void (**eip)
2528      }
2529
2530    /* Set up stack. */
2531 -  if (!setup_stack (esp))
2532 +  if (!setup_stack (cmd_line, esp))
2533      goto done;
2534
2535    /* Start address. */
2536 @@ -280,15 +409,11 @@ load (const char *filename, void (**eip)
2537    success = true;
2538
2539   done:
2540 -  /* We arrive here whether the load is successful or not. */
2541 -  file_close (file);
2542    return success;
2543  }
2544  \f
2545  /* load() helpers. */
2546
2547 -static bool install_page (void *upage, void *kpage);
2548 -
2549  /* Loads the segment described by PHDR from FILE into user
2550     address space.  Return true if successful, false otherwise. */
2551  static bool
2552 @@ -296,6 +421,7 @@ load_segment (struct file *file, const s
2553  {
2554    void *start, *end;  /* Page-rounded segment start and end. */
2555    uint8_t *upage;     /* Iterator from start to end. */
2556 +  off_t file_offset;  /* Offset into file. */
2557    off_t filesz_left;  /* Bytes left of file data (as opposed to
2558                           zero-initialized bytes). */
2559
2560 @@ -303,7 +429,7 @@ load_segment (struct file *file, const s
2561       commented out.  You'll want to use it when implementing VM
2562       to decide whether to page the segment from its executable or
2563       from swap. */
2564 -  //bool read_only = (phdr->p_flags & PF_W) == 0;
2565 +  bool read_only = (phdr->p_flags & PF_W) == 0;
2566
2567    ASSERT (file != NULL);
2568    ASSERT (phdr != NULL);
2569 @@ -332,69 +458,129 @@ load_segment (struct file *file, const s
2570        || start == 0)
2571      return false;
2572
2573 -  /* Load the segment page-by-page into memory. */
2574 +  /* Add the segment page-by-page to the hash table. */
2575    filesz_left = phdr->p_filesz + (phdr->p_vaddr & PGMASK);
2576 -  file_seek (file, ROUND_DOWN (phdr->p_offset, PGSIZE));
2577 +  file_offset = ROUND_DOWN (phdr->p_offset, PGSIZE);
2578    for (upage = start; upage < (uint8_t *) end; upage += PGSIZE)
2579      {
2580 -      /* We want to read min(PGSIZE, filesz_left) bytes from the
2581 -         file into the page and zero the rest. */
2582 -      size_t read_bytes = filesz_left >= PGSIZE ? PGSIZE : filesz_left;
2583 -      size_t zero_bytes = PGSIZE - read_bytes;
2584 -      uint8_t *kpage = palloc_get_page (PAL_USER);
2585 -      if (kpage == NULL)
2586 +      struct page *p = page_allocate (upage, read_only);
2587 +      if (p == NULL)
2588          return false;
2589
2590 -      /* Do the reading and zeroing. */
2591 -      if (file_read (file, kpage, read_bytes) != (int) read_bytes)
2592 +      if (filesz_left > 0)
2593          {
2594 -          palloc_free_page (kpage);
2595 -          return false;
2596 -        }
2597 -      memset (kpage + read_bytes, 0, zero_bytes);
2598 -      filesz_left -= read_bytes;
2599 -
2600 -      /* Add the page to the process's address space. */
2601 -      if (!install_page (upage, kpage))
2602 -        {
2603 -          palloc_free_page (kpage);
2604 -          return false;
2605 +          size_t file_bytes = filesz_left >= PGSIZE ? PGSIZE : filesz_left;
2606 +          p->file = file;
2607 +          p->file_offset = file_offset;
2608 +          p->file_bytes = file_bytes;
2609 +          filesz_left -= file_bytes;
2610 +          file_offset += file_bytes;
2611          }
2612      }
2613
2614    return true;
2615  }
2616
2617 -/* Create a minimal stack by mapping a zeroed page at the top of
2618 -   user virtual memory. */
2619 +/* Reverse the order of the ARGC pointers to char in ARGV. */
2620 +static void
2621 +reverse (int argc, char **argv)
2622 +{
2623 +  for (; argc > 1; argc -= 2, argv++)
2624 +    {
2625 +      char *tmp = argv[0];
2626 +      argv[0] = argv[argc - 1];
2627 +      argv[argc - 1] = tmp;
2628 +    }
2629 +}
2630 +
2631 +/* Pushes the SIZE bytes in BUF onto the stack in KPAGE, whose
2632 +   page-relative stack pointer is *OFS, and then adjusts *OFS
2633 +   appropriately.  The bytes pushed are rounded to a 32-bit
2634 +   boundary.
2635 +
2636 +   If successful, returns a pointer to the newly pushed object.
2637 +   On failure, returns a null pointer. */
2638 +static void *
2639 +push (uint8_t *kpage, size_t *ofs, const void *buf, size_t size)
2640 +{
2641 +  size_t padsize = ROUND_UP (size, sizeof (uint32_t));
2642 +  if (*ofs < padsize)
2643 +    return NULL;
2644 +
2645 +  *ofs -= padsize;
2646 +  memcpy (kpage + *ofs + (padsize - size), buf, size);
2647 +  return kpage + *ofs + (padsize - size);
2648 +}
2649 +
2650 +/* Sets up command line arguments in KPAGE, which will be mapped
2651 +   to UPAGE in user space.  The command line arguments are taken
2652 +   from CMD_LINE, separated by spaces.  Sets *ESP to the initial
2653 +   stack pointer for the process. */
2654  static bool
2655 -setup_stack (void **esp)
2656 +init_cmd_line (uint8_t *kpage, uint8_t *upage, const char *cmd_line,
2657 +               void **esp)
2658  {
2659 -  uint8_t *kpage;
2660 -  bool success = false;
2661 +  size_t ofs = PGSIZE;
2662 +  char *const null = NULL;
2663 +  char *cmd_line_copy;
2664 +  char *karg, *saveptr;
2665 +  int argc;
2666 +  char **argv;
2667 +
2668 +  /* Push command line string. */
2669 +  cmd_line_copy = push (kpage, &ofs, cmd_line, strlen (cmd_line) + 1);
2670 +  if (cmd_line_copy == NULL)
2671 +    return false;
2672 +
2673 +  if (push (kpage, &ofs, &null, sizeof null) == NULL)
2674 +    return false;
2675
2676 -  kpage = palloc_get_page (PAL_USER | PAL_ZERO);
2677 -  if (kpage != NULL)
2678 +  /* Parse command line into arguments
2679 +     and push them in reverse order. */
2680 +  argc = 0;
2681 +  for (karg = strtok_r (cmd_line_copy, " ", &saveptr); karg != NULL;
2682 +       karg = strtok_r (NULL, " ", &saveptr))
2683      {
2684 -      success = install_page (((uint8_t *) PHYS_BASE) - PGSIZE, kpage);
2685 -      if (success)
2686 -        *esp = PHYS_BASE;
2687 -      else
2688 -        palloc_free_page (kpage);
2689 +      char *uarg = upage + (karg - (char *) kpage);
2690 +      if (push (kpage, &ofs, &uarg, sizeof uarg) == NULL)
2691 +        return false;
2692 +      argc++;
2693      }
2694 -  return success;
2695 +
2696 +  /* Reverse the order of the command line arguments. */
2697 +  argv = (char **) (upage + ofs);
2698 +  reverse (argc, (char **) (kpage + ofs));
2699 +
2700 +  /* Push argv, argc, "return address". */
2701 +  if (push (kpage, &ofs, &argv, sizeof argv) == NULL
2702 +      || push (kpage, &ofs, &argc, sizeof argc) == NULL
2703 +      || push (kpage, &ofs, &null, sizeof null) == NULL)
2704 +    return false;
2705 +
2706 +  /* Set initial stack pointer. */
2707 +  *esp = upage + ofs;
2708 +  return true;
2709  }
2710
2711 -/* Adds a mapping from user virtual address UPAGE to kernel
2712 -   virtual address KPAGE to the page table.  Fails if UPAGE is
2713 -   already mapped or if memory allocation fails. */
2714 +/* Create a minimal stack for T by mapping a page at the
2715 +   top of user virtual memory.  Fills in the page using CMD_LINE
2716 +   and sets *ESP to the stack pointer. */
2717  static bool
2718 -install_page (void *upage, void *kpage)
2719 +setup_stack (const char *cmd_line, void **esp)
2720  {
2721 -  struct thread *t = thread_current ();
2722 -
2723 -  /* Verify that there's not already a page at that virtual
2724 -     address, then map our page there. */
2725 -  return (pagedir_get_page (t->pagedir, upage) == NULL
2726 -          && pagedir_set_page (t->pagedir, upage, kpage, true));
2727 +  struct page *page = page_allocate (((uint8_t *) PHYS_BASE) - PGSIZE, false);
2728 +  if (page != NULL)
2729 +    {
2730 +      page->frame = frame_alloc_and_lock (page);
2731 +      if (page->frame != NULL)
2732 +        {
2733 +          bool ok;
2734 +          page->read_only = false;
2735 +          page->private = false;
2736 +          ok = init_cmd_line (page->frame->base, page->addr, cmd_line, esp);
2737 +          frame_unlock (page->frame);
2738 +          return ok;
2739 +        }
2740 +    }
2741 +  return false;
2742  }
2743 diff -u src/userprog/syscall.c~ src/userprog/syscall.c
2744 --- src/userprog/syscall.c~ 2005-06-16 14:56:52.000000000 -0700
2745 +++ src/userprog/syscall.c 2005-06-16 15:09:31.000000000 -0700
2746 @@ -1,20 +1,594 @@
2747  #include "userprog/syscall.h"
2748  #include <stdio.h>
2749 +#include <string.h>
2750  #include <syscall-nr.h>
2751 +#include "userprog/process.h"
2752 +#include "userprog/pagedir.h"
2753 +#include "devices/kbd.h"
2754 +#include "filesys/directory.h"
2755 +#include "filesys/filesys.h"
2756 +#include "filesys/file.h"
2757 +#include "threads/init.h"
2758  #include "threads/interrupt.h"
2759 +#include "threads/malloc.h"
2760 +#include "threads/mmu.h"
2761 +#include "threads/palloc.h"
2762  #include "threads/thread.h"
2763 -
2764 +#include "vm/page.h"
2765 +
2766 +
2767 +static int sys_halt (void);
2768 +static int sys_exit (int status);
2769 +static int sys_exec (const char *ufile);
2770 +static int sys_wait (tid_t);
2771 +static int sys_create (const char *ufile, unsigned initial_size);
2772 +static int sys_remove (const char *ufile);
2773 +static int sys_open (const char *ufile);
2774 +static int sys_filesize (int handle);
2775 +static int sys_read (int handle, void *udst_, unsigned size);
2776 +static int sys_write (int handle, void *usrc_, unsigned size);
2777 +static int sys_seek (int handle, unsigned position);
2778 +static int sys_tell (int handle);
2779 +static int sys_close (int handle);
2780 +static int sys_mmap (int handle, void *addr);
2781 +static int sys_munmap (int mapping);
2782 +static int sys_chdir (const char *udir);
2783 +static int sys_mkdir (const char *udir);
2784 +static int sys_lsdir (void);
2785 +
2786  static void syscall_handler (struct intr_frame *);
2787 -
2788 +static void copy_in (void *, const void *, size_t);
2789 +
2790  void
2791  syscall_init (void)
2792  {
2793    intr_register_int (0x30, 3, INTR_ON, syscall_handler, "syscall");
2794  }
2795 +
2796 +/* System call handler. */
2797 +static void
2798 +syscall_handler (struct intr_frame *f)
2799 +{
2800 +  typedef int syscall_function (int, int, int);
2801 +
2802 +  /* A system call. */
2803 +  struct syscall
2804 +    {
2805 +      size_t arg_cnt;           /* Number of arguments. */
2806 +      syscall_function *func;   /* Implementation. */
2807 +    };
2808 +
2809 +  /* Table of system calls. */
2810 +  static const struct syscall syscall_table[] =
2811 +    {
2812 +      {0, (syscall_function *) sys_halt},
2813 +      {1, (syscall_function *) sys_exit},
2814 +      {1, (syscall_function *) sys_exec},
2815 +      {1, (syscall_function *) sys_wait},
2816 +      {2, (syscall_function *) sys_create},
2817 +      {1, (syscall_function *) sys_remove},
2818 +      {1, (syscall_function *) sys_open},
2819 +      {1, (syscall_function *) sys_filesize},
2820 +      {3, (syscall_function *) sys_read},
2821 +      {3, (syscall_function *) sys_write},
2822 +      {2, (syscall_function *) sys_seek},
2823 +      {1, (syscall_function *) sys_tell},
2824 +      {1, (syscall_function *) sys_close},
2825 +      {2, (syscall_function *) sys_mmap},
2826 +      {1, (syscall_function *) sys_munmap},
2827 +      {1, (syscall_function *) sys_chdir},
2828 +      {1, (syscall_function *) sys_mkdir},
2829 +      {0, (syscall_function *) sys_lsdir},
2830 +    };
2831
2832 +  const struct syscall *sc;
2833 +  unsigned call_nr;
2834 +  int args[3];
2835 +
2836 +  /* Get the system call. */
2837 +  copy_in (&call_nr, f->esp, sizeof call_nr);
2838 +  if (call_nr >= sizeof syscall_table / sizeof *syscall_table)
2839 +    thread_exit ();
2840 +  sc = syscall_table + call_nr;
2841 +
2842 +  /* Get the system call arguments. */
2843 +  ASSERT (sc->arg_cnt <= sizeof args / sizeof *args);
2844 +  memset (args, 0, sizeof args);
2845 +  copy_in (args, (uint32_t *) f->esp + 1, sizeof *args * sc->arg_cnt);
2846 +
2847 +  /* Execute the system call,
2848 +     and set the return value. */
2849 +  f->eax = sc->func (args[0], args[1], args[2]);
2850 +}
2851 +
2852 +/* Copies SIZE bytes from user address USRC to kernel address
2853 +   DST.
2854 +   Call thread_exit() if any of the user accesses are invalid. */
2855  static void
2856 -syscall_handler (struct intr_frame *f UNUSED)
2857 +copy_in (void *dst_, const void *usrc_, size_t size)
2858 +{
2859 +  uint8_t *dst = dst_;
2860 +  const uint8_t *usrc = usrc_;
2861 +
2862 +  while (size > 0)
2863 +    {
2864 +      size_t chunk_size = PGSIZE - pg_ofs (usrc);
2865 +      if (chunk_size > size)
2866 +        chunk_size = size;
2867 +
2868 +      if (!page_lock (usrc, false))
2869 +        thread_exit ();
2870 +      memcpy (dst, usrc, chunk_size);
2871 +      page_unlock (usrc);
2872 +
2873 +      dst += chunk_size;
2874 +      usrc += chunk_size;
2875 +      size -= chunk_size;
2876 +    }
2877 +}
2878 +
2879 +/* Creates a copy of user string US in kernel memory
2880 +   and returns it as a page that must be freed with
2881 +   palloc_free_page().
2882 +   Truncates the string at PGSIZE bytes in size.
2883 +   Call thread_exit() if any of the user accesses are invalid. */
2884 +static char *
2885 +copy_in_string (const char *us)
2886 +{
2887 +  char *ks;
2888 +  char *upage;
2889 +  size_t length;
2890 +
2891 +  ks = palloc_get_page (0);
2892 +  if (ks == NULL)
2893 +    thread_exit ();
2894 +
2895 +  length = 0;
2896 +  for (;;)
2897 +    {
2898 +      upage = pg_round_down (us);
2899 +      if (!page_lock (upage, false))
2900 +        goto lock_error;
2901 +
2902 +      for (; us < upage + PGSIZE; us++)
2903 +        {
2904 +          ks[length++] = *us;
2905 +          if (*us == '\0')
2906 +            {
2907 +              page_unlock (upage);
2908 +              return ks;
2909 +            }
2910 +          else if (length >= PGSIZE)
2911 +            goto too_long_error;
2912 +        }
2913 +
2914 +      page_unlock (upage);
2915 +    }
2916 +
2917 + too_long_error:
2918 +  page_unlock (upage);
2919 + lock_error:
2920 +  palloc_free_page (ks);
2921 +  thread_exit ();
2922 +}
2923 +
2924 +/* Halt system call. */
2925 +static int
2926 +sys_halt (void)
2927 +{
2928 +  power_off ();
2929 +}
2930 +
2931 +/* Exit system call. */
2932 +static int
2933 +sys_exit (int exit_code)
2934 +{
2935 +  thread_current ()->exit_code = exit_code;
2936 +  thread_exit ();
2937 +  NOT_REACHED ();
2938 +}
2939 +
2940 +/* Exec system call. */
2941 +static int
2942 +sys_exec (const char *ufile)
2943 +{
2944 +  tid_t tid;
2945 +  char *kfile = copy_in_string (ufile);
2946 +
2947 +  tid = process_execute (kfile);
2948 +
2949 +  palloc_free_page (kfile);
2950 +
2951 +  return tid;
2952 +}
2953 +
2954 +/* Wait system call. */
2955 +static int
2956 +sys_wait (tid_t child)
2957 +{
2958 +  return process_wait (child);
2959 +}
2960 +
2961 +/* Create system call. */
2962 +static int
2963 +sys_create (const char *ufile, unsigned initial_size)
2964 +{
2965 +  char *kfile = copy_in_string (ufile);
2966 +  bool ok = filesys_create (kfile, initial_size, FILE_INODE);
2967 +  palloc_free_page (kfile);
2968 +
2969 +  return ok;
2970 +}
2971 +
2972 +/* Remove system call. */
2973 +static int
2974 +sys_remove (const char *ufile)
2975 +{
2976 +  char *kfile = copy_in_string (ufile);
2977 +  bool ok = filesys_remove (kfile);
2978 +  palloc_free_page (kfile);
2979 +
2980 +  return ok;
2981 +}
2982 +\f
2983 +/* A file descriptor, for binding a file handle to a file. */
2984 +struct file_descriptor
2985 +  {
2986 +    struct list_elem elem;      /* List element. */
2987 +    struct file *file;          /* File. */
2988 +    int handle;                 /* File handle. */
2989 +  };
2990 +
2991 +/* Open system call. */
2992 +static int
2993 +sys_open (const char *ufile)
2994 +{
2995 +  char *kfile = copy_in_string (ufile);
2996 +  struct file_descriptor *fd;
2997 +  int handle = -1;
2998 +
2999 +  fd = malloc (sizeof *fd);
3000 +  if (fd != NULL)
3001 +    {
3002 +      fd->file = file_open (filesys_open (kfile));
3003 +      if (fd->file != NULL)
3004 +        {
3005 +          struct thread *cur = thread_current ();
3006 +          handle = fd->handle = cur->next_handle++;
3007 +          list_push_front (&cur->fds, &fd->elem);
3008 +        }
3009 +      else
3010 +        free (fd);
3011 +    }
3012 +
3013 +  palloc_free_page (kfile);
3014 +  return handle;
3015 +}
3016 +
3017 +/* Returns the file descriptor associated with the given handle.
3018 +   Terminates the process if HANDLE is not associated with an
3019 +   open file. */
3020 +static struct file_descriptor *
3021 +lookup_fd (int handle)
3022 +{
3023 +  struct thread *cur = thread_current ();
3024 +  struct list_elem *e;
3025 +
3026 +  for (e = list_begin (&cur->fds); e != list_end (&cur->fds);
3027 +       e = list_next (e))
3028 +    {
3029 +      struct file_descriptor *fd;
3030 +      fd = list_entry (e, struct file_descriptor, elem);
3031 +      if (fd->handle == handle)
3032 +        return fd;
3033 +    }
3034 +
3035 +  thread_exit ();
3036 +}
3037 +
3038 +/* Filesize system call. */
3039 +static int
3040 +sys_filesize (int handle)
3041 +{
3042 +  struct file_descriptor *fd = lookup_fd (handle);
3043 +  int size;
3044 +
3045 +  size = file_length (fd->file);
3046 +
3047 +  return size;
3048 +}
3049 +
3050 +/* Read system call. */
3051 +static int
3052 +sys_read (int handle, void *udst_, unsigned size)
3053 +{
3054 +  uint8_t *udst = udst_;
3055 +  struct file_descriptor *fd;
3056 +  int bytes_read = 0;
3057 +
3058 +  /* Look up file descriptor. */
3059 +  if (handle != STDIN_FILENO)
3060 +    fd = lookup_fd (handle);
3061 +
3062 +  while (size > 0)
3063 +    {
3064 +      /* How much to read into this page? */
3065 +      size_t page_left = PGSIZE - pg_ofs (udst);
3066 +      size_t read_amt = size < page_left ? size : page_left;
3067 +      off_t retval;
3068 +
3069 +      /* Check that touching this page is okay. */
3070 +      if (!page_lock (udst, true))
3071 +        thread_exit ();
3072 +
3073 +      /* Read from file into page. */
3074 +      if (handle != STDIN_FILENO)
3075 +        {
3076 +          retval = file_read (fd->file, udst, read_amt);
3077 +          if (retval < 0)
3078 +            {
3079 +              if (bytes_read == 0)
3080 +                bytes_read = -1;
3081 +              break;
3082 +            }
3083 +          bytes_read += retval;
3084 +        }
3085 +      else
3086 +        {
3087 +          size_t i;
3088 +
3089 +          for (i = 0; i < read_amt; i++)
3090 +            udst[i] = kbd_getc ();
3091 +          bytes_read = read_amt;
3092 +        }
3093 +
3094 +      /* Release page. */
3095 +      page_unlock (udst);
3096 +
3097 +      /* If it was a short read we're done. */
3098 +      if (retval != (off_t) read_amt)
3099 +        break;
3100 +
3101 +      /* Advance. */
3102 +      udst += retval;
3103 +      size -= retval;
3104 +    }
3105 +
3106 +  return bytes_read;
3107 +}
3108 +
3109 +/* Write system call. */
3110 +static int
3111 +sys_write (int handle, void *usrc_, unsigned size)
3112  {
3113 -  printf ("system call!\n");
3114 +  uint8_t *usrc = usrc_;
3115 +  struct file_descriptor *fd = NULL;
3116 +  int bytes_written = 0;
3117 +
3118 +  /* Lookup up file descriptor. */
3119 +  if (handle != STDOUT_FILENO)
3120 +    fd = lookup_fd (handle);
3121 +
3122 +  while (size > 0)
3123 +    {
3124 +      /* How much bytes to write to this page? */
3125 +      size_t page_left = PGSIZE - pg_ofs (usrc);
3126 +      size_t write_amt = size < page_left ? size : page_left;
3127 +      off_t retval;
3128 +
3129 +      /* Check that we can touch this user page. */
3130 +      if (!page_lock (usrc, false))
3131 +        thread_exit ();
3132 +
3133 +      /* Do the write. */
3134 +      if (handle == STDOUT_FILENO)
3135 +        {
3136 +          putbuf (usrc, write_amt);
3137 +          retval = write_amt;
3138 +        }
3139 +      else
3140 +        retval = file_write (fd->file, usrc, write_amt);
3141 +
3142 +      /* Release user page. */
3143 +      page_unlock (usrc);
3144 +
3145 +      /* Handle return value. */
3146 +      if (retval < 0)
3147 +        {
3148 +          if (bytes_written == 0)
3149 +            bytes_written = -1;
3150 +          break;
3151 +        }
3152 +      bytes_written += retval;
3153 +
3154 +      /* If it was a short write we're done. */
3155 +      if (retval != (off_t) write_amt)
3156 +        break;
3157 +
3158 +      /* Advance. */
3159 +      usrc += retval;
3160 +      size -= retval;
3161 +    }
3162 +
3163 +  return bytes_written;
3164 +}
3165 +
3166 +/* Seek system call. */
3167 +static int
3168 +sys_seek (int handle, unsigned position)
3169 +{
3170 +  if ((off_t) position >= 0)
3171 +    file_seek (lookup_fd (handle)->file, position);
3172 +  return 0;
3173 +}
3174 +
3175 +/* Tell system call. */
3176 +static int
3177 +sys_tell (int handle)
3178 +{
3179 +  return file_tell (lookup_fd (handle)->file);
3180 +}
3181 +
3182 +/* Close system call. */
3183 +static int
3184 +sys_close (int handle)
3185 +{
3186 +  struct file_descriptor *fd = lookup_fd (handle);
3187 +  file_close (fd->file);
3188 +  list_remove (&fd->elem);
3189 +  free (fd);
3190 +  return 0;
3191 +}
3192 +\f
3193 +/* Binds a mapping id to a region of memory and a file. */
3194 +struct mapping
3195 +  {
3196 +    struct list_elem elem;      /* List element. */
3197 +    int handle;                 /* Mapping id. */
3198 +    struct file *file;          /* File. */
3199 +    uint8_t *base;              /* Start of memory mapping. */
3200 +    size_t page_cnt;            /* Number of pages mapped. */
3201 +  };
3202 +
3203 +/* Returns the file descriptor associated with the given handle.
3204 +   Terminates the process if HANDLE is not associated with a
3205 +   memory mapping. */
3206 +static struct mapping *
3207 +lookup_mapping (int handle)
3208 +{
3209 +  struct thread *cur = thread_current ();
3210 +  struct list_elem *e;
3211 +
3212 +  for (e = list_begin (&cur->mappings); e != list_end (&cur->mappings);
3213 +       e = list_next (e))
3214 +    {
3215 +      struct mapping *m = list_entry (e, struct mapping, elem);
3216 +      if (m->handle == handle)
3217 +        return m;
3218 +    }
3219 +
3220    thread_exit ();
3221  }
3222 +
3223 +/* Remove mapping M from the virtual address space,
3224 +   writing back any pages that have changed. */
3225 +static void
3226 +unmap (struct mapping *m)
3227 +{
3228 +  list_remove (&m->elem);
3229 +  while (m->page_cnt-- > 0)
3230 +    {
3231 +      page_deallocate (m->base);
3232 +      m->base += PGSIZE;
3233 +    }
3234 +  file_close (m->file);
3235 +  free (m);
3236 +}
3237 +
3238 +/* Mmap system call. */
3239 +static int
3240 +sys_mmap (int handle, void *addr)
3241 +{
3242 +  struct file_descriptor *fd = lookup_fd (handle);
3243 +  struct mapping *m = malloc (sizeof *m);
3244 +  size_t offset;
3245 +  off_t length;
3246 +
3247 +  if (m == NULL || addr == NULL || pg_ofs (addr) != 0)
3248 +    return -1;
3249 +
3250 +  m->handle = thread_current ()->next_handle++;
3251 +  m->file = file_reopen (fd->file);
3252 +  if (m->file == NULL)
3253 +    {
3254 +      free (m);
3255 +      return -1;
3256 +    }
3257 +  m->base = addr;
3258 +  m->page_cnt = 0;
3259 +  list_push_front (&thread_current ()->mappings, &m->elem);
3260 +
3261 +  offset = 0;
3262 +  length = file_length (m->file);
3263 +  while (length > 0)
3264 +    {
3265 +      struct page *p = page_allocate ((uint8_t *) addr + offset, false);
3266 +      if (p == NULL)
3267 +        {
3268 +          unmap (m);
3269 +          return -1;
3270 +        }
3271 +      p->private = false;
3272 +      p->file = m->file;
3273 +      p->file_offset = offset;
3274 +      p->file_bytes = length >= PGSIZE ? PGSIZE : length;
3275 +      offset += p->file_bytes;
3276 +      length -= p->file_bytes;
3277 +      m->page_cnt++;
3278 +    }
3279 +
3280 +  return m->handle;
3281 +}
3282 +
3283 +/* Munmap system call. */
3284 +static int
3285 +sys_munmap (int mapping)
3286 +{
3287 +  unmap (lookup_mapping (mapping));
3288 +  return 0;
3289 +}
3290 +
3291 +/* Chdir system call. */
3292 +static int
3293 +sys_chdir (const char *udir)
3294 +{
3295 +  char *kdir = copy_in_string (udir);
3296 +  bool ok = filesys_chdir (kdir);
3297 +  palloc_free_page (kdir);
3298 +  return ok;
3299 +}
3300 +
3301 +/* Mkdir system call. */
3302 +static int
3303 +sys_mkdir (const char *udir)
3304 +{
3305 +  char *kdir = copy_in_string (udir);
3306 +  bool ok = filesys_create (kdir, 0, DIR_INODE);
3307 +  palloc_free_page (kdir);
3308 +
3309 +  return ok;
3310 +}
3311 +
3312 +/* Lsdir system call. */
3313 +static int
3314 +sys_lsdir (void)
3315 +{
3316 +  dir_list (thread_current ()->wd);
3317 +  return 0;
3318 +}
3319 +\f
3320 +/* On thread exit, close all open files and unmap all mappings. */
3321 +void
3322 +syscall_exit (void)
3323 +{
3324 +  struct thread *cur = thread_current ();
3325 +  struct list_elem *e, *next;
3326 +
3327 +  for (e = list_begin (&cur->fds); e != list_end (&cur->fds); e = next)
3328 +    {
3329 +      struct file_descriptor *fd = list_entry (e, struct file_descriptor, elem);
3330 +      next = list_next (e);
3331 +      file_close (fd->file);
3332 +      free (fd);
3333 +    }
3334 +
3335 +  for (e = list_begin (&cur->mappings); e != list_end (&cur->mappings);
3336 +       e = next)
3337 +    {
3338 +      struct mapping *m = list_entry (e, struct mapping, elem);
3339 +      next = list_next (e);
3340 +      unmap (m);
3341 +    }
3342 +
3343 +  dir_close (cur->wd);
3344 +}
3345 diff -u src/userprog/syscall.h~ src/userprog/syscall.h
3346 --- src/userprog/syscall.h~ 2004-09-05 22:38:45.000000000 -0700
3347 +++ src/userprog/syscall.h 2005-06-16 15:09:31.000000000 -0700
3348 @@ -2,5 +2,6 @@
3349  #define USERPROG_SYSCALL_H
3350
3351  void syscall_init (void);
3352 +void syscall_exit (void);
3353
3354  #endif /* userprog/syscall.h */
3355 diff -u src/vm/frame.c~ src/vm/frame.c
3356 --- src/vm/frame.c~ 1969-12-31 16:00:00.000000000 -0800
3357 +++ src/vm/frame.c 2005-06-16 15:09:31.000000000 -0700
3358 @@ -0,0 +1,161 @@
3359 +#include "vm/frame.h"
3360 +#include <stdio.h>
3361 +#include "vm/page.h"
3362 +#include "devices/timer.h"
3363 +#include "threads/init.h"
3364 +#include "threads/malloc.h"
3365 +#include "threads/mmu.h"
3366 +#include "threads/palloc.h"
3367 +#include "threads/synch.h"
3368 +
3369 +static struct frame *frames;
3370 +static size_t frame_cnt;
3371 +
3372 +static struct lock scan_lock;
3373 +static size_t hand;
3374 +
3375 +/* Initialize the frame manager. */
3376 +void
3377 +frame_init (void)
3378 +{
3379 +  void *base;
3380 +
3381 +  lock_init (&scan_lock);
3382 +
3383 +  frames = malloc (sizeof *frames * ram_pages);
3384 +  if (frames == NULL)
3385 +    PANIC ("out of memory allocating page frames");
3386 +
3387 +  while ((base = palloc_get_page (PAL_USER)) != NULL)
3388 +    {
3389 +      struct frame *f = &frames[frame_cnt++];
3390 +      lock_init (&f->lock);
3391 +      f->base = base;
3392 +      f->page = NULL;
3393 +    }
3394 +}
3395 +
3396 +/* Tries to allocate and lock a frame for PAGE.
3397 +   Returns the frame if successful, false on failure. */
3398 +static struct frame *
3399 +try_frame_alloc_and_lock (struct page *page)
3400 +{
3401 +  size_t i;
3402 +
3403 +  lock_acquire (&scan_lock);
3404 +
3405 +  /* Find a free frame. */
3406 +  for (i = 0; i < frame_cnt; i++)
3407 +    {
3408 +      struct frame *f = &frames[i];
3409 +      if (!lock_try_acquire (&f->lock))
3410 +        continue;
3411 +      if (f->page == NULL)
3412 +        {
3413 +          f->page = page;
3414 +          lock_release (&scan_lock);
3415 +          return f;
3416 +        }
3417 +      lock_release (&f->lock);
3418 +    }
3419 +
3420 +  /* No free frame.  Find a frame to evict. */
3421 +  for (i = 0; i < frame_cnt * 2; i++)
3422 +    {
3423 +      /* Get a frame. */
3424 +      struct frame *f = &frames[hand];
3425 +      if (++hand >= frame_cnt)
3426 +        hand = 0;
3427 +
3428 +      if (!lock_try_acquire (&f->lock))
3429 +        continue;
3430 +
3431 +      if (f->page == NULL)
3432 +        {
3433 +          f->page = page;
3434 +          lock_release (&scan_lock);
3435 +          return f;
3436 +        }
3437 +
3438 +      if (page_accessed_recently (f->page))
3439 +        {
3440 +          lock_release (&f->lock);
3441 +          continue;
3442 +        }
3443 +
3444 +      lock_release (&scan_lock);
3445 +
3446 +      /* Evict this frame. */
3447 +      if (!page_out (f->page))
3448 +        {
3449 +          lock_release (&f->lock);
3450 +          return NULL;
3451 +        }
3452 +
3453 +      f->page = page;
3454 +      return f;
3455 +    }
3456 +
3457 +  lock_release (&scan_lock);
3458 +  return NULL;
3459 +}
3460 +
3461 +/* Tries really hard to allocate and lock a frame for PAGE.
3462 +   Returns the frame if successful, false on failure. */
3463 +struct frame *
3464 +frame_alloc_and_lock (struct page *page)
3465 +{
3466 +  size_t try;
3467 +
3468 +  for (try = 0; try < 3; try++)
3469 +    {
3470 +      struct frame *f = try_frame_alloc_and_lock (page);
3471 +      if (f != NULL)
3472 +        {
3473 +          ASSERT (lock_held_by_current_thread (&f->lock));
3474 +          return f;
3475 +        }
3476 +      timer_msleep (1000);
3477 +    }
3478 +
3479 +  return NULL;
3480 +}
3481 +
3482 +/* Locks P's frame into memory, if it has one.
3483 +   Upon return, p->frame will not change until P is unlocked. */
3484 +void
3485 +frame_lock (struct page *p)
3486 +{
3487 +  /* A frame can be asynchronously removed, but never inserted. */
3488 +  struct frame *f = p->frame;
3489 +  if (f != NULL)
3490 +    {
3491 +      lock_acquire (&f->lock);
3492 +      if (f != p->frame)
3493 +        {
3494 +          lock_release (&f->lock);
3495 +          ASSERT (p->frame == NULL);
3496 +        }
3497 +    }
3498 +}
3499 +
3500 +/* Releases frame F for use by another page.
3501 +   F must be locked for use by the current process.
3502 +   Any data in F is lost. */
3503 +void
3504 +frame_free (struct frame *f)
3505 +{
3506 +  ASSERT (lock_held_by_current_thread (&f->lock));
3507 +
3508 +  f->page = NULL;
3509 +  lock_release (&f->lock);
3510 +}
3511 +
3512 +/* Unlocks frame F, allowing it to be evicted.
3513 +   F must be locked for use by the current process. */
3514 +void
3515 +frame_unlock (struct frame *f)
3516 +{
3517 +  ASSERT (lock_held_by_current_thread (&f->lock));
3518 +  lock_release (&f->lock);
3519 +}
3520 diff -u src/vm/frame.h~ src/vm/frame.h
3521 --- src/vm/frame.h~ 1969-12-31 16:00:00.000000000 -0800
3522 +++ src/vm/frame.h 2005-06-16 15:09:31.000000000 -0700
3523 @@ -0,0 +1,23 @@
3524 +#ifndef VM_FRAME_H
3525 +#define VM_FRAME_H
3526 +
3527 +#include <stdbool.h>
3528 +#include "threads/synch.h"
3529 +
3530 +/* A physical frame. */
3531 +struct frame
3532 +  {
3533 +    struct lock lock;           /* Prevent simultaneous access. */
3534 +    void *base;                 /* Kernel virtual base address. */
3535 +    struct page *page;          /* Mapped process page, if any. */
3536 +  };
3537 +
3538 +void frame_init (void);
3539 +
3540 +struct frame *frame_alloc_and_lock (struct page *);
3541 +void frame_lock (struct page *);
3542 +
3543 +void frame_free (struct frame *);
3544 +void frame_unlock (struct frame *);
3545 +
3546 +#endif /* vm/frame.h */
3547 diff -u src/vm/page.c~ src/vm/page.c
3548 --- src/vm/page.c~ 1969-12-31 16:00:00.000000000 -0800
3549 +++ src/vm/page.c 2005-06-16 15:09:31.000000000 -0700
3550 @@ -0,0 +1,297 @@
3551 +#include "vm/page.h"
3552 +#include <stdio.h>
3553 +#include <string.h>
3554 +#include "vm/frame.h"
3555 +#include "vm/swap.h"
3556 +#include "filesys/file.h"
3557 +#include "threads/malloc.h"
3558 +#include "threads/mmu.h"
3559 +#include "threads/thread.h"
3560 +#include "userprog/pagedir.h"
3561 +
3562 +/* Maximum size of process stack, in bytes. */
3563 +#define STACK_MAX (1024 * 1024)
3564 +
3565 +/* Destroys the current process's page table. */
3566 +void
3567 +page_exit (void)
3568 +{
3569 +  struct hash *h;
3570 +  struct hash_iterator i;
3571 +
3572 +  h = thread_current ()->pages;
3573 +  if (h == NULL)
3574 +    return;
3575 +
3576 +  hash_first (&i, h);
3577 +  hash_next (&i);
3578 +  while (hash_cur (&i))
3579 +    {
3580 +      struct page *p = hash_entry (hash_cur (&i), struct page, hash_elem);
3581 +      hash_next (&i);
3582 +      frame_lock (p);
3583 +      if (p->frame)
3584 +        frame_free (p->frame);
3585 +      free (p);
3586 +    }
3587 +  hash_destroy (h);
3588 +}
3589 +
3590 +/* Returns the page containing the given virtual ADDRESS,
3591 +   or a null pointer if no such page exists.
3592 +   Allocates stack pages as necessary. */
3593 +static struct page *
3594 +page_for_addr (const void *address)
3595 +{
3596 +  if (address < PHYS_BASE)
3597 +    {
3598 +      struct page p;
3599 +      struct hash_elem *e;
3600 +
3601 +      /* Find existing page. */
3602 +      p.addr = (void *) pg_round_down (address);
3603 +      e = hash_find (thread_current ()->pages, &p.hash_elem);
3604 +      if (e != NULL)
3605 +        return hash_entry (e, struct page, hash_elem);
3606 +
3607 +      /* No page.  Expand stack? */
3608 +      if (address >= PHYS_BASE - STACK_MAX
3609 +          && address >= thread_current ()->user_esp - 32)
3610 +        return page_allocate ((void *) address, false);
3611 +    }
3612 +  return NULL;
3613 +}
3614 +
3615 +/* Locks a frame for page P and pages it in.
3616 +   Returns true if successful, false on failure. */
3617 +static bool
3618 +do_page_in (struct page *p)
3619 +{
3620 +  /* Get a frame for the page. */
3621 +  p->frame = frame_alloc_and_lock (p);
3622 +  if (p->frame == NULL)
3623 +    return false;
3624 +
3625 +  /* Copy data into the frame. */
3626 +  if (p->sector != (disk_sector_t) -1)
3627 +    {
3628 +      /* Get data from swap. */
3629 +      swap_in (p);
3630 +    }
3631 +  else if (p->file != NULL)
3632 +    {
3633 +      /* Get data from file. */
3634 +      off_t read_bytes = file_read_at (p->file, p->frame->base,
3635 +                                        p->file_bytes, p->file_offset);
3636 +      off_t zero_bytes = PGSIZE - read_bytes;
3637 +      memset (p->frame->base + read_bytes, 0, zero_bytes);
3638 +      if (read_bytes != p->file_bytes)
3639 +        printf ("bytes read (%"PROTd") != bytes requested (%"PROTd")\n",
3640 +                read_bytes, p->file_bytes);
3641 +    }
3642 +  else
3643 +    {
3644 +      /* Provide all-zero page. */
3645 +      memset (p->frame->base, 0, PGSIZE);
3646 +    }
3647 +
3648 +  return true;
3649 +}
3650 +
3651 +/* Faults in the page containing FAULT_ADDR.
3652 +   Returns true if successful, false on failure. */
3653 +bool
3654 +page_in (void *fault_addr)
3655 +{
3656 +  struct page *p;
3657 +  bool success;
3658 +
3659 +  /* Can't handle page faults without a hash table. */
3660 +  if (thread_current ()->pages == NULL)
3661 +    return false;
3662 +
3663 +  p = page_for_addr (fault_addr);
3664 +  if (p == NULL)
3665 +    return false;
3666 +
3667 +  frame_lock (p);
3668 +  if (p->frame == NULL)
3669 +    {
3670 +      if (!do_page_in (p))
3671 +        return false;
3672 +    }
3673 +  ASSERT (lock_held_by_current_thread (&p->frame->lock));
3674 +
3675 +  /* Install frame into page table. */
3676 +  success = pagedir_set_page (thread_current ()->pagedir, p->addr,
3677 +                              p->frame->base, !p->read_only);
3678 +
3679 +  /* Release frame. */
3680 +  frame_unlock (p->frame);
3681 +
3682 +  return success;
3683 +}
3684 +
3685 +/* Evicts page P.
3686 +   P must have a locked frame.
3687 +   Return true if successful, false on failure. */
3688 +bool
3689 +page_out (struct page *p)
3690 +{
3691 +  bool dirty;
3692 +  bool ok;
3693 +
3694 +  ASSERT (p->frame != NULL);
3695 +  ASSERT (lock_held_by_current_thread (&p->frame->lock));
3696 +
3697 +  /* Mark page not present in page table, forcing accesses by the
3698 +     process to fault.  This must happen before checking the
3699 +     dirty bit, to prevent a race with the process dirtying the
3700 +     page. */
3701 +  pagedir_clear_page (p->thread->pagedir, p->addr);
3702 +
3703 +  /* Has the frame been modified? */
3704 +  dirty = pagedir_is_dirty (p->thread->pagedir, p->addr);
3705 +
3706 +  /* Write frame contents to disk if necessary. */
3707 +  if (p->file != NULL)
3708 +    {
3709 +      if (dirty)
3710 +        {
3711 +          if (p->private)
3712 +            ok = swap_out (p);
3713 +          else
3714 +            ok = file_write_at (p->file, p->frame->base, p->file_bytes,
3715 +                                p->file_offset) == p->file_bytes;
3716 +        }
3717 +      else
3718 +        ok = true;
3719 +    }
3720 +  else
3721 +    ok = swap_out (p);
3722 +  if (ok)
3723 +    {
3724 +      //memset (p->frame->base, 0xcc, PGSIZE);
3725 +      p->frame = NULL;
3726 +    }
3727 +  return ok;
3728 +}
3729 +
3730 +/* Returns true if page P's data has been accessed recently,
3731 +   false otherwise.
3732 +   P must have a frame locked into memory. */
3733 +bool
3734 +page_accessed_recently (struct page *p)
3735 +{
3736 +  bool was_accessed;
3737 +
3738 +  ASSERT (p->frame != NULL);
3739 +  ASSERT (lock_held_by_current_thread (&p->frame->lock));
3740 +
3741 +  was_accessed = pagedir_is_accessed (p->thread->pagedir, p->addr);
3742 +  if (was_accessed)
3743 +    pagedir_set_accessed (p->thread->pagedir, p->addr, false);
3744 +  return was_accessed;
3745 +}
3746 +
3747 +/* Adds a mapping for user virtual address VADDR to the page hash
3748 +   table.  Fails if VADDR is already mapped or if memory
3749 +   allocation fails. */
3750 +struct page *
3751 +page_allocate (void *vaddr, bool read_only)
3752 +{
3753 +  struct thread *t = thread_current ();
3754 +  struct page *p = malloc (sizeof *p);
3755 +  if (p != NULL)
3756 +    {
3757 +      p->addr = pg_round_down (vaddr);
3758 +
3759 +      p->read_only = read_only;
3760 +      p->private = !read_only;
3761 +
3762 +      p->frame = NULL;
3763 +
3764 +      p->sector = (disk_sector_t) -1;
3765 +
3766 +      p->file = NULL;
3767 +      p->file_offset = 0;
3768 +      p->file_bytes = 0;
3769 +
3770 +      p->thread = thread_current ();
3771 +
3772 +      if (hash_insert (t->pages, &p->hash_elem) != NULL)
3773 +        {
3774 +          /* Already mapped. */
3775 +          free (p);
3776 +          p = NULL;
3777 +        }
3778 +    }
3779 +  return p;
3780 +}
3781 +
3782 +/* Evicts the page containing address VADDR
3783 +   and removes it from the page table. */
3784 +void
3785 +page_deallocate (void *vaddr)
3786 +{
3787 +  struct page *p = page_for_addr (vaddr);
3788 +  ASSERT (p != NULL);
3789 +  frame_lock (p);
3790 +  if (p->frame)
3791 +    {
3792 +      struct frame *f = p->frame;
3793 +      if (p->file && !p->private)
3794 +        page_out (p);
3795 +      frame_free (f);
3796 +    }
3797 +  hash_delete (thread_current ()->pages, &p->hash_elem);
3798 +  free (p);
3799 +}
3800 +
3801 +/* Returns a hash value for the page that E refers to. */
3802 +unsigned
3803 +page_hash (const struct hash_elem *e, void *aux UNUSED)
3804 +{
3805 +  const struct page *p = hash_entry (e, struct page, hash_elem);
3806 +  return ((uintptr_t) p->addr) >> PGBITS;
3807 +}
3808 +
3809 +/* Returns true if page A precedes page B. */
3810 +bool
3811 +page_less (const struct hash_elem *a_, const struct hash_elem *b_,
3812 +           void *aux UNUSED)
3813 +{
3814 +  const struct page *a = hash_entry (a_, struct page, hash_elem);
3815 +  const struct page *b = hash_entry (b_, struct page, hash_elem);
3816 +
3817 +  return a->addr < b->addr;
3818 +}
3819 +
3820 +/* Tries to lock the page containing ADDR into physical memory.
3821 +   If WILL_WRITE is true, the page must be writeable;
3822 +   otherwise it may be read-only.
3823 +   Returns true if successful, false on failure. */
3824 +bool
3825 +page_lock (const void *addr, bool will_write)
3826 +{
3827 +  struct page *p = page_for_addr (addr);
3828 +  if (p == NULL || (p->read_only && will_write))
3829 +    return false;
3830 +
3831 +  frame_lock (p);
3832 +  if (p->frame == NULL)
3833 +    return (do_page_in (p)
3834 +            && pagedir_set_page (thread_current ()->pagedir, p->addr,
3835 +                                 p->frame->base, !p->read_only));
3836 +  else
3837 +    return true;
3838 +}
3839 +
3840 +/* Unlocks a page locked with page_lock(). */
3841 +void
3842 +page_unlock (const void *addr)
3843 +{
3844 +  struct page *p = page_for_addr (addr);
3845 +  ASSERT (p != NULL);
3846 +  frame_unlock (p->frame);
3847 +}
3848 diff -u src/vm/page.h~ src/vm/page.h
3849 --- src/vm/page.h~ 1969-12-31 16:00:00.000000000 -0800
3850 +++ src/vm/page.h 2005-06-16 15:09:31.000000000 -0700
3851 @@ -0,0 +1,50 @@
3852 +#ifndef VM_PAGE_H
3853 +#define VM_PAGE_H
3854 +
3855 +#include <hash.h>
3856 +#include "devices/disk.h"
3857 +#include "filesys/off_t.h"
3858 +#include "threads/synch.h"
3859 +
3860 +/* Virtual page. */
3861 +struct page
3862 +  {
3863 +    /* Immutable members. */
3864 +    void *addr;                 /* User virtual address. */
3865 +    bool read_only;             /* Read-only page? */
3866 +    struct thread *thread;      /* Owning thread. */
3867 +
3868 +    /* Accessed only in owning process context. */
3869 +    struct hash_elem hash_elem; /* struct thread `pages' hash element. */
3870 +
3871 +    /* Set only in owning process context with frame->frame_lock held.
3872 +       Cleared only with scan_lock and frame->frame_lock held. */
3873 +    struct frame *frame;        /* Page frame. */
3874 +
3875 +    /* Swap information, protected by frame->frame_lock. */
3876 +    disk_sector_t sector;       /* Starting sector of swap area, or -1. */
3877 +
3878 +    /* Memory-mapped file information, protected by frame->frame_lock. */
3879 +    bool private;               /* False to write back to file,
3880 +                                   true to write back to swap. */
3881 +    struct file *file;          /* File. */
3882 +    off_t file_offset;          /* Offset in file. */
3883 +    off_t file_bytes;           /* Bytes to read/write, 1...PGSIZE. */
3884 +  };
3885 +
3886 +void page_exit (void);
3887 +
3888 +struct page *page_allocate (void *, bool read_only);
3889 +void page_deallocate (void *vaddr);
3890 +
3891 +bool page_in (void *fault_addr);
3892 +bool page_out (struct page *);
3893 +bool page_accessed_recently (struct page *);
3894 +
3895 +bool page_lock (const void *, bool will_write);
3896 +void page_unlock (const void *);
3897 +
3898 +hash_hash_func page_hash;
3899 +hash_less_func page_less;
3900 +
3901 +#endif /* vm/page.h */
3902 diff -u src/vm/swap.c~ src/vm/swap.c
3903 --- src/vm/swap.c~ 1969-12-31 16:00:00.000000000 -0800
3904 +++ src/vm/swap.c 2005-06-16 15:09:31.000000000 -0700
3905 @@ -0,0 +1,85 @@
3906 +#include "vm/swap.h"
3907 +#include <bitmap.h>
3908 +#include <debug.h>
3909 +#include <stdio.h>
3910 +#include "vm/frame.h"
3911 +#include "vm/page.h"
3912 +#include "devices/disk.h"
3913 +#include "threads/mmu.h"
3914 +#include "threads/synch.h"
3915 +
3916 +/* The swap disk. */
3917 +static struct disk *swap_disk;
3918 +
3919 +/* Used swap pages. */
3920 +static struct bitmap *swap_bitmap;
3921 +
3922 +/* Protects swap_bitmap. */
3923 +static struct lock swap_lock;
3924 +
3925 +/* Number of sectors per page. */
3926 +#define PAGE_SECTORS (PGSIZE / DISK_SECTOR_SIZE)
3927 +
3928 +/* Sets up swap. */
3929 +void
3930 +swap_init (void)
3931 +{
3932 +  swap_disk = disk_get (1, 1);
3933 +  if (swap_disk == NULL)
3934 +    {
3935 +      printf ("no swap disk--swap disabled\n");
3936 +      swap_bitmap = bitmap_create (0);
3937 +    }
3938 +  else
3939 +    swap_bitmap = bitmap_create (disk_size (swap_disk) / PAGE_SECTORS);
3940 +  if (swap_bitmap == NULL)
3941 +    PANIC ("couldn't create swap bitmap");
3942 +  lock_init (&swap_lock);
3943 +}
3944 +
3945 +/* Swaps in page P, which must have a locked frame
3946 +   (and be swapped out). */
3947 +void
3948 +swap_in (struct page *p)
3949 +{
3950 +  size_t i;
3951 +
3952 +  ASSERT (p->frame != NULL);
3953 +  ASSERT (lock_held_by_current_thread (&p->frame->lock));
3954 +  ASSERT (p->sector != (disk_sector_t) -1);
3955 +
3956 +  for (i = 0; i < PAGE_SECTORS; i++)
3957 +    disk_read (swap_disk, p->sector + i,
3958 +               p->frame->base + i * DISK_SECTOR_SIZE);
3959 +  bitmap_reset (swap_bitmap, p->sector / PAGE_SECTORS);
3960 +  p->sector = (disk_sector_t) -1;
3961 +}
3962 +
3963 +/* Swaps out page P, which must have a locked frame. */
3964 +bool
3965 +swap_out (struct page *p)
3966 +{
3967 +  size_t slot;
3968 +  size_t i;
3969 +
3970 +  ASSERT (p->frame != NULL);
3971 +  ASSERT (lock_held_by_current_thread (&p->frame->lock));
3972 +
3973 +  lock_acquire (&swap_lock);
3974 +  slot = bitmap_scan_and_flip (swap_bitmap, 0, 1, false);
3975 +  lock_release (&swap_lock);
3976 +  if (slot == BITMAP_ERROR)
3977 +    return false;
3978 +
3979 +  p->sector = slot * PAGE_SECTORS;
3980 +  for (i = 0; i < PAGE_SECTORS; i++)
3981 +    disk_write (swap_disk, p->sector + i,
3982 +                p->frame->base + i * DISK_SECTOR_SIZE);
3983 +
3984 +  p->private = false;
3985 +  p->file = NULL;
3986 +  p->file_offset = 0;
3987 +  p->file_bytes = 0;
3988 +
3989 +  return true;
3990 +}
3991 diff -u src/vm/swap.h~ src/vm/swap.h
3992 --- src/vm/swap.h~ 1969-12-31 16:00:00.000000000 -0800
3993 +++ src/vm/swap.h 2005-06-16 15:09:31.000000000 -0700
3994 @@ -0,0 +1,11 @@
3995 +#ifndef VM_SWAP_H
3996 +#define VM_SWAP_H 1
3997 +
3998 +#include <stdbool.h>
3999 +
4000 +struct page;
4001 +void swap_init (void);
4002 +void swap_in (struct page *);
4003 +bool swap_out (struct page *);
4004 +
4005 +#endif /* vm/swap.h */