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