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

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