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