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

   1 diff --git a/src/Makefile.build b/src/Makefile.build
   2 index 1057023..05e888c 100644
   3 --- a/src/Makefile.build
   4 +++ b/src/Makefile.build
   5 @@ -73,6 +73,7 @@ filesys_SRC += filesys/file.c         # Files.
   6  filesys_SRC += filesys/directory.c     # Directories.
   7  filesys_SRC += filesys/inode.c         # File headers.
   8  filesys_SRC += filesys/fsutil.c                # Utilities.
   9 +filesys_SRC += filesys/cache.c         # Cache.
  10
  11  SOURCES = $(foreach dir,$(KERNEL_SUBDIRS),$($(dir)_SRC))
  12  OBJECTS = $(patsubst %.c,%.o,$(patsubst %.S,%.o,$(SOURCES)))
  13 diff --git a/src/filesys/Make.vars b/src/filesys/Make.vars
  14 index b3aa005..d04ab67 100644
  15 --- a/src/filesys/Make.vars
  16 +++ b/src/filesys/Make.vars
  17 @@ -7,7 +7,7 @@ GRADING_FILE = $(SRCDIR)/tests/filesys/Grading.no-vm
  18  SIMULATOR = --qemu
  19
  20  # Uncomment the lines below to enable VM.
  21 -#kernel.bin: DEFINES += -DVM
  22 -#KERNEL_SUBDIRS += vm
  23 -#TEST_SUBDIRS += tests/vm
  24 -#GRADING_FILE = $(SRCDIR)/tests/filesys/Grading.with-vm
  25 +kernel.bin: DEFINES += -DVM
  26 +KERNEL_SUBDIRS += vm
  27 +TEST_SUBDIRS += tests/vm
  28 +GRADING_FILE = $(SRCDIR)/tests/filesys/Grading.with-vm
  29 diff --git a/src/filesys/cache.c b/src/filesys/cache.c
  30 new file mode 100644
  31 index 0000000..cd2ff1c
  32 --- /dev/null
  33 +++ b/src/filesys/cache.c
  34 @@ -0,0 +1,472 @@
  35 +#include "filesys/cache.h"
  36 +#include <debug.h>
  37 +#include <string.h>
  38 +#include "filesys/filesys.h"
  39 +#include "devices/timer.h"
  40 +#include "threads/malloc.h"
  41 +#include "threads/synch.h"
  42 +#include "threads/thread.h"
  43 +
  44 +#define INVALID_SECTOR ((block_sector_t) -1)
  45 +
  46 +/* A cached block. */
  47 +struct cache_block
  48 +  {
  49 +    /* Locking to prevent eviction. */
  50 +    struct lock block_lock;                    /* Protects fields in group. */
  51 +    struct condition no_readers_or_writers; /* readers == 0 && writers == 0 */
  52 +    struct condition no_writers;                            /* writers == 0 */
  53 +    int readers, read_waiters;          /* # of readers, # waiting to read. */
  54 +    int writers, write_waiters; /* # of writers (<= 1), # waiting to write. */
  55 +
  56 +    /* Sector number.  INVALID_SECTOR indicates a free cache block.
  57 +
  58 +       Changing from free to allocated requires cache_sync.
  59 +
  60 +       Changing from allocated to free requires block_lock, block
  61 +       must be up-to-date and not dirty, and no one may be
  62 +       waiting on it. */
  63 +    block_sector_t sector;
  64 +
  65 +    /* Is data[] correct?
  66 +       Requires write lock or data_lock. */
  67 +    bool up_to_date;
  68 +
  69 +    /* Does data[] need to be written back to disk?
  70 +       Valid only when up-to-date.
  71 +       Requires read lock or write lock or data_lock. */
  72 +    bool dirty;
  73 +
  74 +    /* Sector data.
  75 +       Access to data[] requires up-to-date and read or write lock.
  76 +       Bringing up-to-date requires write lock or data_lock. */
  77 +    struct lock data_lock;              /* Protects fields in group. */
  78 +    uint8_t data[BLOCK_SECTOR_SIZE];    /* Disk data. */
  79 +  };
  80 +
  81 +/* Cache. */
  82 +#define CACHE_CNT 64
  83 +struct cache_block cache[CACHE_CNT];
  84 +
  85 +/* Cache lock.
  86 +
  87 +   Required to allocate a cache block to a sector, to prevent a
  88 +   single sector being allocated two different cache blocks.
  89 +
  90 +   Required to search the cache for a sector, to prevent the
  91 +   sector from being added while the search is ongoing.
  92 +
  93 +   Protects hand. */
  94 +struct lock cache_sync;
  95 +
  96 +/* Cache eviction hand.
  97 +   Protected by cache_sync. */
  98 +static int hand = 0;
  99 +
 100 +static void flushd_init (void);
 101 +static void readaheadd_init (void);
 102 +static void readaheadd_submit (block_sector_t sector);
 103 +\f
 104 +/* Initializes cache. */
 105 +void
 106 +cache_init (void)
 107 +{
 108 +  int i;
 109 +
 110 +  lock_init (&cache_sync);
 111 +  for (i = 0; i < CACHE_CNT; i++)
 112 +    {
 113 +      struct cache_block *b = &cache[i];
 114 +      lock_init (&b->block_lock);
 115 +      cond_init (&b->no_readers_or_writers);
 116 +      cond_init (&b->no_writers);
 117 +      b->readers = b->read_waiters = 0;
 118 +      b->writers = b->write_waiters = 0;
 119 +      b->sector = INVALID_SECTOR;
 120 +      lock_init (&b->data_lock);
 121 +    }
 122 +
 123 +  flushd_init ();
 124 +  readaheadd_init ();
 125 +}
 126 +
 127 +/* Flushes cache to disk. */
 128 +void
 129 +cache_flush (void)
 130 +{
 131 +  int i;
 132 +
 133 +  for (i = 0; i < CACHE_CNT; i++)
 134 +    {
 135 +      struct cache_block *b = &cache[i];
 136 +      block_sector_t sector;
 137 +
 138 +      lock_acquire (&b->block_lock);
 139 +      sector = b->sector;
 140 +      lock_release (&b->block_lock);
 141 +
 142 +      if (sector == INVALID_SECTOR)
 143 +        continue;
 144 +
 145 +      b = cache_lock (sector, EXCLUSIVE);
 146 +      if (b->up_to_date && b->dirty)
 147 +        {
 148 +          block_write (fs_device, b->sector, b->data);
 149 +          b->dirty = false;
 150 +        }
 151 +      cache_unlock (b);
 152 +    }
 153 +}
 154 +
 155 +/* Locks the given SECTOR into the cache and returns the cache
 156 +   block.
 157 +   If TYPE is EXCLUSIVE, then the block returned will be locked
 158 +   only by the caller.  The calling thread must not already
 159 +   have any lock on the block.
 160 +   If TYPE is NON_EXCLUSIVE, then block returned may be locked by
 161 +   any number of other callers.  The calling thread may already
 162 +   have any number of non-exclusive locks on the block. */
 163 +struct cache_block *
 164 +cache_lock (block_sector_t sector, enum lock_type type)
 165 +{
 166 +  int i;
 167 +
 168 + try_again:
 169 +  lock_acquire (&cache_sync);
 170 +
 171 +  /* Is the block already in-cache? */
 172 +  for (i = 0; i < CACHE_CNT; i++)
 173 +    {
 174 +      /* Skip any blocks that don't hold SECTOR. */
 175 +      struct cache_block *b = &cache[i];
 176 +      lock_acquire (&b->block_lock);
 177 +      if (b->sector != sector)
 178 +        {
 179 +          lock_release (&b->block_lock);
 180 +          continue;
 181 +        }
 182 +      lock_release (&cache_sync);
 183 +
 184 +      /* Get read or write lock. */
 185 +      if (type == NON_EXCLUSIVE)
 186 +        {
 187 +          /* Lock for read. */
 188 +          b->read_waiters++;
 189 +          if (b->writers || b->write_waiters)
 190 +            do {
 191 +              cond_wait (&b->no_writers, &b->block_lock);
 192 +            } while (b->writers);
 193 +          b->readers++;
 194 +          b->read_waiters--;
 195 +        }
 196 +      else
 197 +        {
 198 +          /* Lock for write. */
 199 +          b->write_waiters++;
 200 +          if (b->readers || b->read_waiters || b->writers)
 201 +            do {
 202 +              cond_wait (&b->no_readers_or_writers, &b->block_lock);
 203 +            } while (b->readers || b->writers);
 204 +          b->writers++;
 205 +          b->write_waiters--;
 206 +        }
 207 +      lock_release (&b->block_lock);
 208 +
 209 +      /* Our sector should have been pinned in the cache while we
 210 +         were waiting.  Make sure. */
 211 +      ASSERT (b->sector == sector);
 212 +
 213 +      return b;
 214 +    }
 215 +
 216 +  /* Not in cache.  Find empty slot.
 217 +     We hold cache_sync. */
 218 +  for (i = 0; i < CACHE_CNT; i++)
 219 +    {
 220 +      struct cache_block *b = &cache[i];
 221 +      lock_acquire (&b->block_lock);
 222 +      if (b->sector == INVALID_SECTOR)
 223 +        {
 224 +          /* Drop block_lock, which is no longer needed because
 225 +             this is the only code that allocates free blocks,
 226 +             and we still have cache_sync.
 227 +
 228 +             We can't drop cache_sync yet because someone else
 229 +             might try to allocate this same block (or read from
 230 +             it) while we're still initializing the block. */
 231 +          lock_release (&b->block_lock);
 232 +
 233 +          b->sector = sector;
 234 +          b->up_to_date = false;
 235 +          ASSERT (b->readers == 0);
 236 +          ASSERT (b->writers == 0);
 237 +          if (type == NON_EXCLUSIVE)
 238 +            b->readers = 1;
 239 +          else
 240 +            b->writers = 1;
 241 +          lock_release (&cache_sync);
 242 +          return b;
 243 +        }
 244 +      lock_release (&b->block_lock);
 245 +    }
 246 +
 247 +  /* No empty slots.  Evict something.
 248 +     We hold cache_sync. */
 249 +  for (i = 0; i < CACHE_CNT; i++)
 250 +    {
 251 +      struct cache_block *b = &cache[hand];
 252 +      if (++hand >= CACHE_CNT)
 253 +        hand = 0;
 254 +
 255 +      /* Try to grab exclusive write access to block. */
 256 +      lock_acquire (&b->block_lock);
 257 +      if (b->readers || b->writers || b->read_waiters || b->write_waiters)
 258 +        {
 259 +          lock_release (&b->block_lock);
 260 +          continue;
 261 +        }
 262 +      b->writers = 1;
 263 +      lock_release (&b->block_lock);
 264 +
 265 +      lock_release (&cache_sync);
 266 +
 267 +      /* Write block to disk if dirty. */
 268 +      if (b->up_to_date && b->dirty)
 269 +        {
 270 +          block_write (fs_device, b->sector, b->data);
 271 +          b->dirty = false;
 272 +        }
 273 +
 274 +      /* Remove block from cache, if possible: someone might have
 275 +         started waiting on it while the lock was released. */
 276 +      lock_acquire (&b->block_lock);
 277 +      b->writers = 0;
 278 +      if (!b->read_waiters && !b->write_waiters)
 279 +        {
 280 +          /* No one is waiting for it, so we can free it. */
 281 +          b->sector = INVALID_SECTOR;
 282 +        }
 283 +      else
 284 +        {
 285 +          /* There is a waiter.  Give it the block. */
 286 +          if (b->read_waiters)
 287 +            cond_broadcast (&b->no_writers, &b->block_lock);
 288 +          else
 289 +            cond_signal (&b->no_readers_or_writers, &b->block_lock);
 290 +        }
 291 +      lock_release (&b->block_lock);
 292 +
 293 +      /* Try again. */
 294 +      goto try_again;
 295 +    }
 296 +
 297 +  /* Wait for cache contention to die down. */
 298 +  lock_release (&cache_sync);
 299 +  timer_msleep (1000);
 300 +  goto try_again;
 301 +}
 302 +
 303 +/* Bring block B up-to-date, by reading it from disk if
 304 +   necessary, and return a pointer to its data.
 305 +   The caller must have an exclusive or non-exclusive lock on
 306 +   B. */
 307 +void *
 308 +cache_read (struct cache_block *b)
 309 +{
 310 +  lock_acquire (&b->data_lock);
 311 +  if (!b->up_to_date)
 312 +    {
 313 +      block_read (fs_device, b->sector, b->data);
 314 +      b->up_to_date = true;
 315 +      b->dirty = false;
 316 +    }
 317 +  lock_release (&b->data_lock);
 318 +
 319 +  return b->data;
 320 +}
 321 +
 322 +/* Zero out block B, without reading it from disk, and return a
 323 +   pointer to the zeroed data.
 324 +   The caller must have an exclusive lock on B. */
 325 +void *
 326 +cache_zero (struct cache_block *b)
 327 +{
 328 +  ASSERT (b->writers);
 329 +  memset (b->data, 0, BLOCK_SECTOR_SIZE);
 330 +  b->up_to_date = true;
 331 +  b->dirty = true;
 332 +
 333 +  return b->data;
 334 +}
 335 +
 336 +/* Marks block B as dirty, so that it will be written back to
 337 +   disk before eviction.
 338 +   The caller must have a read or write lock on B,
 339 +   and B must be up-to-date. */
 340 +void
 341 +cache_dirty (struct cache_block *b)
 342 +{
 343 +  ASSERT (b->up_to_date);
 344 +  b->dirty = true;
 345 +}
 346 +
 347 +/* Unlocks block B.
 348 +   If B is no longer locked by any thread, then it becomes a
 349 +   candidate for immediate eviction. */
 350 +void
 351 +cache_unlock (struct cache_block *b)
 352 +{
 353 +  lock_acquire (&b->block_lock);
 354 +  if (b->readers)
 355 +    {
 356 +      ASSERT (b->writers == 0);
 357 +      if (--b->readers == 0)
 358 +        cond_signal (&b->no_readers_or_writers, &b->block_lock);
 359 +    }
 360 +  else if (b->writers)
 361 +    {
 362 +      ASSERT (b->readers == 0);
 363 +      ASSERT (b->writers == 1);
 364 +      b->writers--;
 365 +      if (b->read_waiters)
 366 +        cond_broadcast (&b->no_writers, &b->block_lock);
 367 +      else
 368 +        cond_signal (&b->no_readers_or_writers, &b->block_lock);
 369 +    }
 370 +  else
 371 +    NOT_REACHED ();
 372 +  lock_release (&b->block_lock);
 373 +}
 374 +
 375 +/* If SECTOR is in the cache, evicts it immediately without
 376 +   writing it back to disk (even if dirty).
 377 +   The block must be entirely unused. */
 378 +void
 379 +cache_free (block_sector_t sector)
 380 +{
 381 +  int i;
 382 +
 383 +  lock_acquire (&cache_sync);
 384 +  for (i = 0; i < CACHE_CNT; i++)
 385 +    {
 386 +      struct cache_block *b = &cache[i];
 387 +
 388 +      lock_acquire (&b->block_lock);
 389 +      if (b->sector == sector)
 390 +        {
 391 +          lock_release (&cache_sync);
 392 +
 393 +          /* Only invalidate the block if it's unused.  That
 394 +             should be the normal case, but it could be part of a
 395 +             read-ahead (in readaheadd()) or write-behind (in
 396 +             cache_flush()). */
 397 +          if (b->readers == 0 && b->read_waiters == 0
 398 +              && b->writers == 0 && b->write_waiters == 0)
 399 +            b->sector = INVALID_SECTOR;
 400 +
 401 +          lock_release (&b->block_lock);
 402 +          return;
 403 +        }
 404 +      lock_release (&b->block_lock);
 405 +    }
 406 +  lock_release (&cache_sync);
 407 +}
 408 +
 409 +void
 410 +cache_readahead (block_sector_t sector)
 411 +{
 412 +  readaheadd_submit (sector);
 413 +}
 414 +\f
 415 +/* Flush daemon. */
 416 +
 417 +static void flushd (void *aux);
 418 +
 419 +/* Initializes flush daemon. */
 420 +static void
 421 +flushd_init (void)
 422 +{
 423 +  thread_create ("flushd", PRI_MIN, flushd, NULL);
 424 +}
 425 +
 426 +/* Flush daemon thread. */
 427 +static void
 428 +flushd (void *aux UNUSED)
 429 +{
 430 +  for (;;)
 431 +    {
 432 +      timer_msleep (30 * 1000);
 433 +      cache_flush ();
 434 +    }
 435 +}
 436 +\f
 437 +/* A block to read ahead. */
 438 +struct readahead_block
 439 +  {
 440 +    struct list_elem list_elem;         /* readahead_list element. */
 441 +    block_sector_t sector;              /* Sector to read. */
 442 +  };
 443 +
 444 +/* Protects readahead_list.
 445 +   Monitor lock for readahead_list_nonempty. */
 446 +static struct lock readahead_lock;
 447 +
 448 +/* Signaled when a block is added to readahead_list. */
 449 +static struct condition readahead_list_nonempty;
 450 +
 451 +/* List of blocks for read-ahead. */
 452 +static struct list readahead_list;
 453 +
 454 +static void readaheadd (void *aux);
 455 +
 456 +/* Initialize read-ahead daemon. */
 457 +static void
 458 +readaheadd_init (void)
 459 +{
 460 +  lock_init (&readahead_lock);
 461 +  cond_init (&readahead_list_nonempty);
 462 +  list_init (&readahead_list);
 463 +  thread_create ("readaheadd", PRI_MIN, readaheadd, NULL);
 464 +}
 465 +
 466 +/* Adds SECTOR to the read-ahead queue. */
 467 +static void
 468 +readaheadd_submit (block_sector_t sector)
 469 +{
 470 +  /* Allocate readahead block. */
 471 +  struct readahead_block *block = malloc (sizeof *block);
 472 +  if (block == NULL)
 473 +    return;
 474 +  block->sector = sector;
 475 +
 476 +  /* Add block to list. */
 477 +  lock_acquire (&readahead_lock);
 478 +  list_push_back (&readahead_list, &block->list_elem);
 479 +  cond_signal (&readahead_list_nonempty, &readahead_lock);
 480 +  lock_release (&readahead_lock);
 481 +}
 482 +
 483 +/* Read-ahead daemon. */
 484 +static void
 485 +readaheadd (void *aux UNUSED)
 486 +{
 487 +  for (;;)
 488 +    {
 489 +      struct readahead_block *ra_block;
 490 +      struct cache_block *cache_block;
 491 +
 492 +      /* Get readahead block from list. */
 493 +      lock_acquire (&readahead_lock);
 494 +      while (list_empty (&readahead_list))
 495 +        cond_wait (&readahead_list_nonempty, &readahead_lock);
 496 +      ra_block = list_entry (list_pop_front (&readahead_list),
 497 +                             struct readahead_block, list_elem);
 498 +      lock_release (&readahead_lock);
 499 +
 500 +      /* Read block into cache. */
 501 +      cache_block = cache_lock (ra_block->sector, NON_EXCLUSIVE);
 502 +      cache_read (cache_block);
 503 +      cache_unlock (cache_block);
 504 +      free (ra_block);
 505 +    }
 506 +}
 507 diff --git a/src/filesys/cache.h b/src/filesys/cache.h
 508 new file mode 100644
 509 index 0000000..2483924
 510 --- /dev/null
 511 +++ b/src/filesys/cache.h
 512 @@ -0,0 +1,23 @@
 513 +#ifndef FILESYS_CACHE_H
 514 +#define FILESYS_CACHE_H
 515 +
 516 +#include "devices/block.h"
 517 +
 518 +/* Type of block lock. */
 519 +enum lock_type
 520 +  {
 521 +    NON_EXCLUSIVE,     /* Any number of lockers. */
 522 +    EXCLUSIVE          /* Only one locker. */
 523 +  };
 524 +
 525 +void cache_init (void);
 526 +void cache_flush (void);
 527 +struct cache_block *cache_lock (block_sector_t, enum lock_type);
 528 +void *cache_read (struct cache_block *);
 529 +void *cache_zero (struct cache_block *);
 530 +void cache_dirty (struct cache_block *);
 531 +void cache_unlock (struct cache_block *);
 532 +void cache_free (block_sector_t);
 533 +void cache_readahead (block_sector_t);
 534 +
 535 +#endif /* filesys/cache.h */
 536 diff --git a/src/filesys/directory.c b/src/filesys/directory.c
 537 index 030c1c9..9855b9d 100644
 538 --- a/src/filesys/directory.c
 539 +++ b/src/filesys/directory.c
 540 @@ -2,6 +2,7 @@
 541  #include <stdio.h>
 542  #include <string.h>
 543  #include <list.h>
 544 +#include "filesys/free-map.h"
 545  #include "filesys/filesys.h"
 546  #include "filesys/inode.h"
 547  #include "threads/malloc.h"
 548 @@ -21,12 +22,39 @@ struct dir_entry
 549      bool in_use;                        /* In use or free? */
 550    };
 551
 552 -/* Creates a directory with space for ENTRY_CNT entries in the
 553 -   given SECTOR.  Returns true if successful, false on failure. */
 554 -bool
 555 -dir_create (block_sector_t sector, size_t entry_cnt)
 556 +/* Creates a directory in the given SECTOR.
 557 +   The directory's parent is in PARENT_SECTOR.
 558 +   Returns inode of created directory if successful,
 559 +   null pointer on faiilure.
 560 +   On failure, SECTOR is released in the free map. */
 561 +struct inode *
 562 +dir_create (block_sector_t sector, block_sector_t parent_sector)
 563  {
 564 -  return inode_create (sector, entry_cnt * sizeof (struct dir_entry));
 565 +  struct inode *inode = inode_create (sector, DIR_INODE);
 566 +  if (inode != NULL)
 567 +    {
 568 +      struct dir_entry entries[2];
 569 +
 570 +      memset (entries, 0, sizeof entries);
 571 +
 572 +      /* "." entry. */
 573 +      entries[0].inode_sector = sector;
 574 +      strlcpy (entries[0].name, ".", sizeof entries[0].name);
 575 +      entries[0].in_use = true;
 576 +
 577 +      /* ".." entry. */
 578 +      entries[1].inode_sector = parent_sector;
 579 +      strlcpy (entries[1].name, "..", sizeof entries[1].name);
 580 +      entries[1].in_use = true;
 581 +
 582 +      if (inode_write_at (inode, entries, sizeof entries, 0) != sizeof entries)
 583 +        {
 584 +          inode_remove (inode);
 585 +          inode_close (inode);
 586 +          inode = NULL;
 587 +        }
 588 +    }
 589 +  return inode;
 590  }
 591
 592  /* Opens and returns the directory for the given INODE, of which
 593 @@ -35,7 +63,7 @@ struct dir *
 594  dir_open (struct inode *inode)
 595  {
 596    struct dir *dir = calloc (1, sizeof *dir);
 597 -  if (inode != NULL && dir != NULL)
 598 +  if (inode != NULL && dir != NULL && inode_get_type (inode) == DIR_INODE)
 599      {
 600        dir->inode = inode;
 601        dir->pos = 0;
 602 @@ -84,10 +112,8 @@ dir_get_inode (struct dir *dir)
 603  }
 604
 605  /* Searches DIR for a file with the given NAME.
 606 -   If successful, returns true, sets *EP to the directory entry
 607 -   if EP is non-null, and sets *OFSP to the byte offset of the
 608 -   directory entry if OFSP is non-null.
 609 -   otherwise, returns false and ignores EP and OFSP. */
 610 +   If successful, returns the file's entry;
 611 +   otherwise, returns a null pointer. */
 612  static bool
 613  lookup (const struct dir *dir, const char *name,
 614          struct dir_entry *ep, off_t *ofsp)
 615 @@ -120,15 +146,16 @@ dir_lookup (const struct dir *dir, const char *name,
 616              struct inode **inode)
 617  {
 618    struct dir_entry e;
 619 +  bool ok;
 620
 621    ASSERT (dir != NULL);
 622    ASSERT (name != NULL);
 623
 624 -  if (lookup (dir, name, &e, NULL))
 625 -    *inode = inode_open (e.inode_sector);
 626 -  else
 627 -    *inode = NULL;
 628 +  inode_lock (dir->inode);
 629 +  ok = lookup (dir, name, &e, NULL);
 630 +  inode_unlock (dir->inode);
 631
 632 +  *inode = ok ? inode_open (e.inode_sector) : NULL;
 633    return *inode != NULL;
 634  }
 635
 636 @@ -149,10 +176,11 @@ dir_add (struct dir *dir, const char *name, block_sector_t inode_sector)
 637    ASSERT (name != NULL);
 638
 639    /* Check NAME for validity. */
 640 -  if (*name == '\0' || strlen (name) > NAME_MAX)
 641 +  if (*name == '\0' || strchr (name, '/') || strlen (name) > NAME_MAX)
 642      return false;
 643
 644    /* Check that NAME is not in use. */
 645 +  inode_lock (dir->inode);
 646    if (lookup (dir, name, NULL, NULL))
 647      goto done;
 648
 649 @@ -175,6 +203,7 @@ dir_add (struct dir *dir, const char *name, block_sector_t inode_sector)
 650    success = inode_write_at (dir->inode, &e, sizeof e, ofs) == sizeof e;
 651
 652   done:
 653 +  inode_unlock (dir->inode);
 654    return success;
 655  }
 656
 657 @@ -192,7 +221,11 @@ dir_remove (struct dir *dir, const char *name)
 658    ASSERT (dir != NULL);
 659    ASSERT (name != NULL);
 660
 661 +  if (!strcmp (name, ".") || !strcmp (name, ".."))
 662 +    return false;
 663 +
 664    /* Find directory entry. */
 665 +  inode_lock (dir->inode);
 666    if (!lookup (dir, name, &e, &ofs))
 667      goto done;
 668
 669 @@ -201,6 +234,26 @@ dir_remove (struct dir *dir, const char *name)
 670    if (inode == NULL)
 671      goto done;
 672
 673 +  /* Verify that it is not an in-use or non-empty directory. */
 674 +  if (inode_get_type (inode) == DIR_INODE)
 675 +    {
 676 +      struct dir_entry e2;
 677 +      off_t pos;
 678 +
 679 +      if (inode_open_cnt (inode) != 1)
 680 +        goto done;
 681 +
 682 +      inode_lock (inode);
 683 +      for (pos = 0; inode_read_at (inode, &e2, sizeof e2, pos) == sizeof e2;
 684 +           pos += sizeof e2)
 685 +        if (e2.in_use && strcmp (e2.name, ".") && strcmp (e2.name, ".."))
 686 +          {
 687 +            inode_unlock (inode);
 688 +            goto done;
 689 +          }
 690 +      inode_unlock (inode);
 691 +    }
 692 +
 693    /* Erase directory entry. */
 694    e.in_use = false;
 695    if (inode_write_at (dir->inode, &e, sizeof e, ofs) != sizeof e)
 696 @@ -211,6 +264,7 @@ dir_remove (struct dir *dir, const char *name)
 697    success = true;
 698
 699   done:
 700 +  inode_unlock (dir->inode);
 701    inode_close (inode);
 702    return success;
 703  }
 704 @@ -223,14 +277,17 @@ dir_readdir (struct dir *dir, char name[NAME_MAX + 1])
 705  {
 706    struct dir_entry e;
 707
 708 +  inode_lock (dir->inode);
 709    while (inode_read_at (dir->inode, &e, sizeof e, dir->pos) == sizeof e)
 710      {
 711        dir->pos += sizeof e;
 712 -      if (e.in_use)
 713 +      if (e.in_use && strcmp (e.name, ".") && strcmp (e.name, ".."))
 714          {
 715 +          inode_unlock (dir->inode);
 716            strlcpy (name, e.name, NAME_MAX + 1);
 717            return true;
 718          }
 719      }
 720 +  inode_unlock (dir->inode);
 721    return false;
 722  }
 723 diff --git a/src/filesys/directory.h b/src/filesys/directory.h
 724 index 930acf9..b8a4593 100644
 725 --- a/src/filesys/directory.h
 726 +++ b/src/filesys/directory.h
 727 @@ -14,7 +14,7 @@
 728  struct inode;
 729
 730  /* Opening and closing directories. */
 731 -bool dir_create (block_sector_t sector, size_t entry_cnt);
 732 +struct inode *dir_create (block_sector_t sector, block_sector_t parent_sector);
 733  struct dir *dir_open (struct inode *);
 734  struct dir *dir_open_root (void);
 735  struct dir *dir_reopen (struct dir *);
 736 diff --git a/src/filesys/file.c b/src/filesys/file.c
 737 index d5fc10d..8669324 100644
 738 --- a/src/filesys/file.c
 739 +++ b/src/filesys/file.c
 740 @@ -1,5 +1,6 @@
 741  #include "filesys/file.h"
 742  #include <debug.h>
 743 +#include "filesys/free-map.h"
 744  #include "filesys/inode.h"
 745  #include "threads/malloc.h"
 746
 747 @@ -11,6 +12,24 @@ struct file
 748      bool deny_write;            /* Has file_deny_write() been called? */
 749    };
 750
 751 +/* Creates a file in the given SECTOR,
 752 +   initially LENGTH bytes long.
 753 +   Returns inode for the file on success, null pointer on failure.
 754 +   On failure, SECTOR is released in the free map. */
 755 +struct inode *
 756 +file_create (block_sector_t sector, off_t length)
 757 +{
 758 +  struct inode *inode = inode_create (sector, FILE_INODE);
 759 +  if (inode != NULL && length > 0
 760 +      && inode_write_at (inode, "", 1, length - 1) != 1)
 761 +    {
 762 +      inode_remove (inode);
 763 +      inode_close (inode);
 764 +      inode = NULL;
 765 +    }
 766 +  return inode;
 767 +}
 768 +
 769  /* Opens a file for the given INODE, of which it takes ownership,
 770     and returns the new file.  Returns a null pointer if an
 771     allocation fails or if INODE is null. */
 772 @@ -18,7 +37,7 @@ struct file *
 773  file_open (struct inode *inode)
 774  {
 775    struct file *file = calloc (1, sizeof *file);
 776 -  if (inode != NULL && file != NULL)
 777 +  if (inode != NULL && file != NULL && inode_get_type (inode) == FILE_INODE)
 778      {
 779        file->inode = inode;
 780        file->pos = 0;
 781 diff --git a/src/filesys/file.h b/src/filesys/file.h
 782 index a33c5af..63b4a65 100644
 783 --- a/src/filesys/file.h
 784 +++ b/src/filesys/file.h
 785 @@ -1,11 +1,14 @@
 786  #ifndef FILESYS_FILE_H
 787  #define FILESYS_FILE_H
 788
 789 +#include <stdbool.h>
 790 +#include "devices/block.h"
 791  #include "filesys/off_t.h"
 792
 793  struct inode;
 794
 795  /* Opening and closing files. */
 796 +struct inode *file_create (block_sector_t sector, off_t length);
 797  struct file *file_open (struct inode *);
 798  struct file *file_reopen (struct file *);
 799  void file_close (struct file *);
 800 diff --git a/src/filesys/filesys.c b/src/filesys/filesys.c
 801 index 7a53f5f..51b4244 100644
 802 --- a/src/filesys/filesys.c
 803 +++ b/src/filesys/filesys.c
 804 @@ -2,10 +2,12 @@
 805  #include <debug.h>
 806  #include <stdio.h>
 807  #include <string.h>
 808 +#include "filesys/cache.h"
 809  #include "filesys/file.h"
 810  #include "filesys/free-map.h"
 811  #include "filesys/inode.h"
 812  #include "filesys/directory.h"
 813 +#include "threads/thread.h"
 814
 815  /* Partition that contains the file system. */
 816  struct block *fs_device;
 817 @@ -22,6 +24,7 @@ filesys_init (bool format)
 818      PANIC ("No file system device found, can't initialize file system.");
 819
 820    inode_init ();
 821 +  cache_init ();
 822    free_map_init ();
 823
 824    if (format)
 825 @@ -36,6 +39,130 @@ void
 826  filesys_done (void)
 827  {
 828    free_map_close ();
 829 +  cache_flush ();
 830 +}
 831 +\f
 832 +/* Extracts a file name part from *SRCP into PART,
 833 +   and updates *SRCP so that the next call will return the next
 834 +   file name part.
 835 +   Returns 1 if successful, 0 at end of string, -1 for a too-long
 836 +   file name part. */
 837 +static int
 838 +get_next_part (char part[NAME_MAX], const char **srcp)
 839 +{
 840 +  const char *src = *srcp;
 841 +  char *dst = part;
 842 +
 843 +  /* Skip leading slashes.
 844 +     If it's all slashes, we're done. */
 845 +  while (*src == '/')
 846 +    src++;
 847 +  if (*src == '\0')
 848 +    return 0;
 849 +
 850 +  /* Copy up to NAME_MAX character from SRC to DST.
 851 +     Add null terminator. */
 852 +  while (*src != '/' && *src != '\0')
 853 +    {
 854 +      if (dst < part + NAME_MAX)
 855 +        *dst++ = *src;
 856 +      else
 857 +        return -1;
 858 +      src++;
 859 +    }
 860 +  *dst = '\0';
 861 +
 862 +  /* Advance source pointer. */
 863 +  *srcp = src;
 864 +  return 1;
 865 +}
 866 +
 867 +/* Resolves relative or absolute file NAME.
 868 +   Returns true if successful, false on failure.
 869 +   Stores the directory corresponding to the name into *DIRP,
 870 +   and the file name part into BASE_NAME. */
 871 +static bool
 872 +resolve_name_to_entry (const char *name,
 873 +                       struct dir **dirp, char base_name[NAME_MAX + 1])
 874 +{
 875 +  struct dir *dir = NULL;
 876 +  struct inode *inode;
 877 +  const char *cp;
 878 +  char part[NAME_MAX + 1], next_part[NAME_MAX + 1];
 879 +  int ok;
 880 +
 881 +  /* Find starting directory. */
 882 +  if (name[0] == '/' || thread_current ()->wd == NULL)
 883 +    dir = dir_open_root ();
 884 +  else
 885 +    dir = dir_reopen (thread_current ()->wd);
 886 +  if (dir == NULL)
 887 +    goto error;
 888 +
 889 +  /* Get first name part. */
 890 +  cp = name;
 891 +  if (get_next_part (part, &cp) <= 0)
 892 +    goto error;
 893 +
 894 +  /* As long as another part follows the current one,
 895 +     traverse down another directory. */
 896 +  while ((ok = get_next_part (next_part, &cp)) > 0)
 897 +    {
 898 +      if (!dir_lookup (dir, part, &inode))
 899 +        goto error;
 900 +
 901 +      dir_close (dir);
 902 +      dir = dir_open (inode);
 903 +      if (dir == NULL)
 904 +        goto error;
 905 +
 906 +      strlcpy (part, next_part, NAME_MAX + 1);
 907 +    }
 908 +  if (ok < 0)
 909 +    goto error;
 910 +
 911 +  /* Return our results. */
 912 +  *dirp = dir;
 913 +  strlcpy (base_name, part, NAME_MAX + 1);
 914 +  return true;
 915 +
 916 + error:
 917 +  /* Return failure. */
 918 +  dir_close (dir);
 919 +  *dirp = NULL;
 920 +  base_name[0] = '\0';
 921 +  return false;
 922 +}
 923 +
 924 +/* Resolves relative or absolute file NAME to an inode.
 925 +   Returns an inode if successful, or a null pointer on failure.
 926 +   The caller is responsible for closing the returned inode. */
 927 +static struct inode *
 928 +resolve_name_to_inode (const char *name)
 929 +{
 930 +  if (name[0] == '/' && name[strspn (name, "/")] == '\0')
 931 +    {
 932 +      /* The name represents the root directory.
 933 +         There's no name part at all, so resolve_name_to_entry()
 934 +         would reject it entirely.
 935 +         Special case it. */
 936 +      return inode_open (ROOT_DIR_SECTOR);
 937 +    }
 938 +  else
 939 +    {
 940 +      struct dir *dir;
 941 +      char base_name[NAME_MAX + 1];
 942 +
 943 +      if (resolve_name_to_entry (name, &dir, base_name))
 944 +        {
 945 +          struct inode *inode;
 946 +          dir_lookup (dir, base_name, &inode);
 947 +          dir_close (dir);
 948 +          return inode;
 949 +        }
 950 +      else
 951 +        return NULL;
 952 +    }
 953  }
 954  \f
 955  /* Creates a file named NAME with the given INITIAL_SIZE.
 956 @@ -43,16 +170,32 @@ filesys_done (void)
 957     Fails if a file named NAME already exists,
 958     or if internal memory allocation fails. */
 959  bool
 960 -filesys_create (const char *name, off_t initial_size)
 961 +filesys_create (const char *name, off_t initial_size, enum inode_type type)
 962  {
 963 -  block_sector_t inode_sector = 0;
 964 -  struct dir *dir = dir_open_root ();
 965 -  bool success = (dir != NULL
 966 -                  && free_map_allocate (1, &inode_sector)
 967 -                  && inode_create (inode_sector, initial_size)
 968 -                  && dir_add (dir, name, inode_sector));
 969 -  if (!success && inode_sector != 0)
 970 -    free_map_release (inode_sector, 1);
 971 +  struct dir *dir;
 972 +  char base_name[NAME_MAX + 1];
 973 +  block_sector_t inode_sector;
 974 +
 975 +  bool success = (resolve_name_to_entry (name, &dir, base_name)
 976 +                  && free_map_allocate (&inode_sector));
 977 +  if (success)
 978 +    {
 979 +      struct inode *inode;
 980 +      if (type == FILE_INODE)
 981 +        inode = file_create (inode_sector, initial_size);
 982 +      else
 983 +        inode = dir_create (inode_sector,
 984 +                            inode_get_inumber (dir_get_inode (dir)));
 985 +      if (inode != NULL)
 986 +        {
 987 +          success = dir_add (dir, base_name, inode_sector);
 988 +          if (!success)
 989 +            inode_remove (inode);
 990 +          inode_close (inode);
 991 +        }
 992 +      else
 993 +        success = false;
 994 +    }
 995    dir_close (dir);
 996
 997    return success;
 998 @@ -63,17 +206,10 @@ filesys_create (const char *name, off_t initial_size)
 999     otherwise.
1000     Fails if no file named NAME exists,
1001     or if an internal memory allocation fails. */
1002 -struct file *
1003 +struct inode *
1004  filesys_open (const char *name)
1005  {
1006 -  struct dir *dir = dir_open_root ();
1007 -  struct inode *inode = NULL;
1008 -
1009 -  if (dir != NULL)
1010 -    dir_lookup (dir, name, &inode);
1011 -  dir_close (dir);
1012 -
1013 -  return file_open (inode);
1014 +  return resolve_name_to_inode (name);
1015  }
1016
1017  /* Deletes the file named NAME.
1018 @@ -83,21 +219,53 @@ filesys_open (const char *name)
1019  bool
1020  filesys_remove (const char *name)
1021  {
1022 -  struct dir *dir = dir_open_root ();
1023 -  bool success = dir != NULL && dir_remove (dir, name);
1024 -  dir_close (dir);
1025 +  struct dir *dir;
1026 +  char base_name[NAME_MAX + 1];
1027 +  bool success;
1028
1029 +  if (resolve_name_to_entry (name, &dir, base_name))
1030 +    {
1031 +      success = dir_remove (dir, base_name);
1032 +      dir_close (dir);
1033 +    }
1034 +  else
1035 +    success = false;
1036 +
1037    return success;
1038  }
1039 +/* Change current directory to NAME.
1040 +   Return true if successful, false on failure. */
1041 +bool
1042 +filesys_chdir (const char *name)
1043 +{
1044 +  struct dir *dir = dir_open (resolve_name_to_inode (name));
1045 +  if (dir != NULL)
1046 +    {
1047 +      dir_close (thread_current ()->wd);
1048 +      thread_current ()->wd = dir;
1049 +      return true;
1050 +    }
1051 +  else
1052 +    return false;
1053 +}
1054  \f
1055  /* Formats the file system. */
1056  static void
1057  do_format (void)
1058  {
1059 +  struct inode *inode;
1060    printf ("Formatting file system...");
1061 +
1062 +  /* Set up free map. */
1063    free_map_create ();
1064 -  if (!dir_create (ROOT_DIR_SECTOR, 16))
1065 +
1066 +  /* Set up root directory. */
1067 +  inode = dir_create (ROOT_DIR_SECTOR, ROOT_DIR_SECTOR);
1068 +  if (inode == NULL)
1069      PANIC ("root directory creation failed");
1070 +  inode_close (inode);
1071 +
1072    free_map_close ();
1073 +
1074    printf ("done.\n");
1075  }
1076 diff --git a/src/filesys/filesys.h b/src/filesys/filesys.h
1077 index c1cda84..f181764 100644
1078 --- a/src/filesys/filesys.h
1079 +++ b/src/filesys/filesys.h
1080 @@ -3,6 +3,7 @@
1081
1082  #include <stdbool.h>
1083  #include "filesys/off_t.h"
1084 +#include "filesys/inode.h"
1085
1086  /* Sectors of system file inodes. */
1087  #define FREE_MAP_SECTOR 0       /* Free map file inode sector. */
1088 @@ -13,8 +14,9 @@ struct block *fs_device;
1089
1090  void filesys_init (bool format);
1091  void filesys_done (void);
1092 -bool filesys_create (const char *name, off_t initial_size);
1093 -struct file *filesys_open (const char *name);
1094 +bool filesys_create (const char *name, off_t initial_size, enum inode_type);
1095 +struct inode *filesys_open (const char *name);
1096  bool filesys_remove (const char *name);
1097 +bool filesys_chdir (const char *name);
1098
1099  #endif /* filesys/filesys.h */
1100 diff --git a/src/filesys/free-map.c b/src/filesys/free-map.c
1101 index 29ea4df..2c88a5c 100644
1102 --- a/src/filesys/free-map.c
1103 +++ b/src/filesys/free-map.c
1104 @@ -3,15 +3,18 @@
1105  #include <debug.h>
1106  #include "filesys/file.h"
1107  #include "filesys/filesys.h"
1108 -#include "filesys/inode.h"
1109 +#include "threads/synch.h"
1110
1111  static struct file *free_map_file;   /* Free map file. */
1112  static struct bitmap *free_map;      /* Free map, one bit per sector. */
1113 +static struct lock free_map_lock;    /* Mutual exclusion. */
1114
1115  /* Initializes the free map. */
1116  void
1117  free_map_init (void)
1118  {
1119 +  lock_init (&free_map_lock);
1120 +
1121    free_map = bitmap_create (block_size (fs_device));
1122    if (free_map == NULL)
1123      PANIC ("bitmap creation failed--file system device is too large");
1124 @@ -19,34 +22,33 @@ free_map_init (void)
1125    bitmap_mark (free_map, ROOT_DIR_SECTOR);
1126  }
1127
1128 -/* Allocates CNT consecutive sectors from the free map and stores
1129 -   the first into *SECTORP.
1130 +/* Allocates a sector from the free map and stores it into
1131 +   *SECTORP.
1132     Returns true if successful, false if not enough consecutive
1133     sectors were available or if the free_map file could not be
1134     written. */
1135  bool
1136 -free_map_allocate (size_t cnt, block_sector_t *sectorp)
1137 +free_map_allocate (block_sector_t *sectorp)
1138  {
1139 -  block_sector_t sector = bitmap_scan_and_flip (free_map, 0, cnt, false);
1140 -  if (sector != BITMAP_ERROR
1141 -      && free_map_file != NULL
1142 -      && !bitmap_write (free_map, free_map_file))
1143 -    {
1144 -      bitmap_set_multiple (free_map, sector, cnt, false);
1145 -      sector = BITMAP_ERROR;
1146 -    }
1147 -  if (sector != BITMAP_ERROR)
1148 +  size_t sector;
1149 +
1150 +  lock_acquire (&free_map_lock);
1151 +  sector = bitmap_scan_and_flip (free_map, 0, 1, false);
1152 +  lock_release (&free_map_lock);
1153 +
1154 +  if (sector != BITMAP_ERROR)
1155      *sectorp = sector;
1156    return sector != BITMAP_ERROR;
1157  }
1158
1159 -/* Makes CNT sectors starting at SECTOR available for use. */
1160 +/* Makes SECTOR available for use. */
1161  void
1162 -free_map_release (block_sector_t sector, size_t cnt)
1163 +free_map_release (block_sector_t sector)
1164  {
1165 -  ASSERT (bitmap_all (free_map, sector, cnt));
1166 -  bitmap_set_multiple (free_map, sector, cnt, false);
1167 -  bitmap_write (free_map, free_map_file);
1168 +  lock_acquire (&free_map_lock);
1169 +  ASSERT (bitmap_test (free_map, sector));
1170 +  bitmap_reset (free_map, sector);
1171 +  lock_release (&free_map_lock);
1172  }
1173
1174  /* Opens the free map file and reads it from disk. */
1175 @@ -64,6 +66,8 @@ free_map_open (void)
1176  void
1177  free_map_close (void)
1178  {
1179 +  if (!bitmap_write (free_map, free_map_file))
1180 +    PANIC ("can't write free map");
1181    file_close (free_map_file);
1182  }
1183
1184 @@ -72,9 +76,13 @@ free_map_close (void)
1185  void
1186  free_map_create (void)
1187  {
1188 +  struct inode *inode;
1189 +
1190    /* Create inode. */
1191 -  if (!inode_create (FREE_MAP_SECTOR, bitmap_file_size (free_map)))
1192 +  inode = file_create (FREE_MAP_SECTOR, 0);
1193 +  if (inode == NULL)
1194      PANIC ("free map creation failed");
1195 +  inode_close (inode);
1196
1197    /* Write bitmap to file. */
1198    free_map_file = file_open (inode_open (FREE_MAP_SECTOR));
1199 diff --git a/src/filesys/free-map.h b/src/filesys/free-map.h
1200 index 316cd1c..63e35e9 100644
1201 --- a/src/filesys/free-map.h
1202 +++ b/src/filesys/free-map.h
1203 @@ -11,7 +11,7 @@ void free_map_create (void);
1204  void free_map_open (void);
1205  void free_map_close (void);
1206
1207 -bool free_map_allocate (size_t, block_sector_t *);
1208 -void free_map_release (block_sector_t, size_t);
1209 +bool free_map_allocate (block_sector_t *);
1210 +void free_map_release (block_sector_t);
1211
1212  #endif /* filesys/free-map.h */
1213 diff --git a/src/filesys/fsutil.c b/src/filesys/fsutil.c
1214 index 447f291..8016fb3 100644
1215 --- a/src/filesys/fsutil.c
1216 +++ b/src/filesys/fsutil.c
1217 @@ -38,7 +38,7 @@ fsutil_cat (char **argv)
1218    char *buffer;
1219
1220    printf ("Printing '%s' to the console...\n", file_name);
1221 -  file = filesys_open (file_name);
1222 +  file = file_open (filesys_open (file_name));
1223    if (file == NULL)
1224      PANIC ("%s: open failed", file_name);
1225    buffer = palloc_get_page (PAL_ASSERT);
1226 @@ -117,9 +117,9 @@ fsutil_extract (char **argv UNUSED)
1227            printf ("Putting '%s' into the file system...\n", file_name);
1228
1229            /* Create destination file. */
1230 -          if (!filesys_create (file_name, size))
1231 +          if (!filesys_create (file_name, size, FILE_INODE))
1232              PANIC ("%s: create failed", file_name);
1233 -          dst = filesys_open (file_name);
1234 +          dst = file_open (filesys_open (file_name));
1235            if (dst == NULL)
1236              PANIC ("%s: open failed", file_name);
1237
1238 @@ -181,7 +181,7 @@ fsutil_append (char **argv)
1239      PANIC ("couldn't allocate buffer");
1240
1241    /* Open source file. */
1242 -  src = filesys_open (file_name);
1243 +  src = file_open (filesys_open (file_name));
1244    if (src == NULL)
1245      PANIC ("%s: open failed", file_name);
1246    size = file_length (src);
1247 diff --git a/src/filesys/inode.c b/src/filesys/inode.c
1248 index 3463563..58ab0d1 100644
1249 --- a/src/filesys/inode.c
1250 +++ b/src/filesys/inode.c
1251 @@ -1,23 +1,38 @@
1252  #include "filesys/inode.h"
1253 +#include <bitmap.h>
1254  #include <list.h>
1255  #include <debug.h>
1256  #include <round.h>
1257 +#include <stdio.h>
1258  #include <string.h>
1259 +#include "filesys/cache.h"
1260  #include "filesys/filesys.h"
1261  #include "filesys/free-map.h"
1262  #include "threads/malloc.h"
1263 +#include "threads/synch.h"
1264
1265  /* Identifies an inode. */
1266  #define INODE_MAGIC 0x494e4f44
1267
1268 +#define DIRECT_CNT 123
1269 +#define INDIRECT_CNT 1
1270 +#define DBL_INDIRECT_CNT 1
1271 +#define SECTOR_CNT (DIRECT_CNT + INDIRECT_CNT + DBL_INDIRECT_CNT)
1272 +
1273 +#define PTRS_PER_SECTOR ((off_t) (BLOCK_SECTOR_SIZE / sizeof (block_sector_t)))
1274 +#define INODE_SPAN ((DIRECT_CNT                                              \
1275 +                     + PTRS_PER_SECTOR * INDIRECT_CNT                        \
1276 +                     + PTRS_PER_SECTOR * PTRS_PER_SECTOR * DBL_INDIRECT_CNT) \
1277 +                    * BLOCK_SECTOR_SIZE)
1278 +
1279  /* On-disk inode.
1280     Must be exactly BLOCK_SECTOR_SIZE bytes long. */
1281  struct inode_disk
1282    {
1283 -    block_sector_t start;               /* First data sector. */
1284 +    block_sector_t sectors[SECTOR_CNT]; /* Sectors. */
1285 +    enum inode_type type;               /* FILE_INODE or DIR_INODE. */
1286      off_t length;                       /* File size in bytes. */
1287      unsigned magic;                     /* Magic number. */
1288 -    uint32_t unused[125];               /* Not used. */
1289    };
1290
1291  /* Returns the number of sectors to allocate for an inode SIZE
1292 @@ -35,74 +50,59 @@ struct inode
1293      block_sector_t sector;              /* Sector number of disk location. */
1294      int open_cnt;                       /* Number of openers. */
1295      bool removed;                       /* True if deleted, false otherwise. */
1296 +    struct lock lock;                   /* Protects the inode. */
1297 +
1298 +    /* Denying writes. */
1299 +    struct lock deny_write_lock;        /* Protects members below. */
1300 +    struct condition no_writers_cond;   /* Signaled when no writers. */
1301      int deny_write_cnt;                 /* 0: writes ok, >0: deny writes. */
1302 -    struct inode_disk data;             /* Inode content. */
1303 +    int writer_cnt;                     /* Number of writers. */
1304    };
1305
1306 -/* Returns the block device sector that contains byte offset POS
1307 -   within INODE.
1308 -   Returns -1 if INODE does not contain data for a byte at offset
1309 -   POS. */
1310 -static block_sector_t
1311 -byte_to_sector (const struct inode *inode, off_t pos)
1312 -{
1313 -  ASSERT (inode != NULL);
1314 -  if (pos < inode->data.length)
1315 -    return inode->data.start + pos / BLOCK_SECTOR_SIZE;
1316 -  else
1317 -    return -1;
1318 -}
1319 -
1320  /* List of open inodes, so that opening a single inode twice
1321     returns the same `struct inode'. */
1322  static struct list open_inodes;
1323
1324 +/* Controls access to open_inodes list. */
1325 +static struct lock open_inodes_lock;
1326 +
1327 +static void deallocate_inode (const struct inode *);
1328 +
1329  /* Initializes the inode module. */
1330  void
1331  inode_init (void)
1332  {
1333    list_init (&open_inodes);
1334 +  lock_init (&open_inodes_lock);
1335  }
1336
1337 -/* Initializes an inode with LENGTH bytes of data and
1338 -   writes the new inode to sector SECTOR on the file system
1339 -   device.
1340 -   Returns true if successful.
1341 -   Returns false if memory or disk allocation fails. */
1342 -bool
1343 -inode_create (block_sector_t sector, off_t length)
1344 +/* Initializes an inode of the given TYPE, writes the new inode
1345 +   to sector SECTOR on the file system device, and returns the
1346 +   inode thus created.  Returns a null pointer if unsuccessful,
1347 +   in which case SECTOR is released in the free map. */
1348 +struct inode *
1349 +inode_create (block_sector_t sector, enum inode_type type)
1350  {
1351 -  struct inode_disk *disk_inode = NULL;
1352 -  bool success = false;
1353 +  struct cache_block *block;
1354 +  struct inode_disk *disk_inode;
1355 +  struct inode *inode;
1356
1357 -  ASSERT (length >= 0);
1358 +  block = cache_lock (sector, EXCLUSIVE);
1359
1360    /* If this assertion fails, the inode structure is not exactly
1361       one sector in size, and you should fix that. */
1362    ASSERT (sizeof *disk_inode == BLOCK_SECTOR_SIZE);
1363 -
1364 -  disk_inode = calloc (1, sizeof *disk_inode);
1365 -  if (disk_inode != NULL)
1366 -    {
1367 -      size_t sectors = bytes_to_sectors (length);
1368 -      disk_inode->length = length;
1369 -      disk_inode->magic = INODE_MAGIC;
1370 -      if (free_map_allocate (sectors, &disk_inode->start))
1371 -        {
1372 -          block_write (fs_device, sector, disk_inode);
1373 -          if (sectors > 0)
1374 -            {
1375 -              static char zeros[BLOCK_SECTOR_SIZE];
1376 -              size_t i;
1377 -
1378 -              for (i = 0; i < sectors; i++)
1379 -                block_write (fs_device, disk_inode->start + i, zeros);
1380 -            }
1381 -          success = true;
1382 -        }
1383 -      free (disk_inode);
1384 -    }
1385 -  return success;
1386 +  disk_inode = cache_zero (block);
1387 +  disk_inode->type = type;
1388 +  disk_inode->length = 0;
1389 +  disk_inode->magic = INODE_MAGIC;
1390 +  cache_dirty (block);
1391 +  cache_unlock (block);
1392 +
1393 +  inode = inode_open (sector);
1394 +  if (inode == NULL)
1395 +    free_map_release (sector);
1396 +  return inode;
1397  }
1398
1399  /* Reads an inode from SECTOR
1400 @@ -115,29 +115,35 @@ inode_open (block_sector_t sector)
1401    struct inode *inode;
1402
1403    /* Check whether this inode is already open. */
1404 +  lock_acquire (&open_inodes_lock);
1405    for (e = list_begin (&open_inodes); e != list_end (&open_inodes);
1406         e = list_next (e))
1407      {
1408        inode = list_entry (e, struct inode, elem);
1409        if (inode->sector == sector)
1410          {
1411 -          inode_reopen (inode);
1412 -          return inode;
1413 +          inode->open_cnt++;
1414 +          goto done;
1415          }
1416      }
1417
1418    /* Allocate memory. */
1419    inode = malloc (sizeof *inode);
1420    if (inode == NULL)
1421 -    return NULL;
1422 +    goto done;
1423
1424    /* Initialize. */
1425    list_push_front (&open_inodes, &inode->elem);
1426    inode->sector = sector;
1427    inode->open_cnt = 1;
1428 +  lock_init (&inode->lock);
1429    inode->deny_write_cnt = 0;
1430 +  lock_init (&inode->deny_write_lock);
1431 +  cond_init (&inode->no_writers_cond);
1432    inode->removed = false;
1433 -  block_read (fs_device, inode->sector, &inode->data);
1434 +
1435 + done:
1436 +  lock_release (&open_inodes_lock);
1437    return inode;
1438  }
1439
1440 @@ -146,10 +152,25 @@ struct inode *
1441  inode_reopen (struct inode *inode)
1442  {
1443    if (inode != NULL)
1444 -    inode->open_cnt++;
1445 +    {
1446 +      lock_acquire (&open_inodes_lock);
1447 +      inode->open_cnt++;
1448 +      lock_release (&open_inodes_lock);
1449 +    }
1450    return inode;
1451  }
1452
1453 +/* Returns the type of INODE. */
1454 +enum inode_type
1455 +inode_get_type (const struct inode *inode)
1456 +{
1457 +  struct cache_block *inode_block = cache_lock (inode->sector, NON_EXCLUSIVE);
1458 +  struct inode_disk *disk_inode = cache_read (inode_block);
1459 +  enum inode_type type = disk_inode->type;
1460 +  cache_unlock (inode_block);
1461 +  return type;
1462 +}
1463 +
1464  /* Returns INODE's inode number. */
1465  block_sector_t
1466  inode_get_inumber (const struct inode *inode)
1467 @@ -168,21 +189,60 @@ inode_close (struct inode *inode)
1468      return;
1469
1470    /* Release resources if this was the last opener. */
1471 +  lock_acquire (&open_inodes_lock);
1472    if (--inode->open_cnt == 0)
1473      {
1474        /* Remove from inode list and release lock. */
1475        list_remove (&inode->elem);
1476 +      lock_release (&open_inodes_lock);
1477
1478        /* Deallocate blocks if removed. */
1479        if (inode->removed)
1480 -        {
1481 -          free_map_release (inode->sector, 1);
1482 -          free_map_release (inode->data.start,
1483 -                            bytes_to_sectors (inode->data.length));
1484 -        }
1485 +        deallocate_inode (inode);
1486
1487        free (inode);
1488      }
1489 +  else
1490 +    lock_release (&open_inodes_lock);
1491 +}
1492 +
1493 +/* Deallocates SECTOR and anything it points to recursively.
1494 +   LEVEL is 2 if SECTOR is doubly indirect,
1495 +   or 1 if SECTOR is indirect,
1496 +   or 0 if SECTOR is a data sector. */
1497 +static void
1498 +deallocate_recursive (block_sector_t sector, int level)
1499 +{
1500 +  if (level > 0)
1501 +    {
1502 +      struct cache_block *block = cache_lock (sector, EXCLUSIVE);
1503 +      block_sector_t *pointers = cache_read (block);
1504 +      int i;
1505 +      for (i = 0; i < PTRS_PER_SECTOR; i++)
1506 +        if (pointers[i])
1507 +          deallocate_recursive (sector, level - 1);
1508 +      cache_unlock (block);
1509 +    }
1510 +
1511 +  cache_free (sector);
1512 +  free_map_release (sector);
1513 +}
1514 +
1515 +/* Deallocates the blocks allocated for INODE. */
1516 +static void
1517 +deallocate_inode (const struct inode *inode)
1518 +{
1519 +  struct cache_block *block = cache_lock (inode->sector, EXCLUSIVE);
1520 +  struct inode_disk *disk_inode = cache_read (block);
1521 +  int i;
1522 +  for (i = 0; i < SECTOR_CNT; i++)
1523 +    if (disk_inode->sectors[i])
1524 +      {
1525 +        int level = (i >= DIRECT_CNT) + (i >= DIRECT_CNT + INDIRECT_CNT);
1526 +        deallocate_recursive (disk_inode->sectors[i], level);
1527 +      }
1528 +  cache_unlock (block);
1529 +  deallocate_recursive (inode->sector, 0);
1530  }
1531
1532  /* Marks INODE to be deleted when it is closed by the last caller who
1533 @@ -194,6 +254,157 @@ inode_remove (struct inode *inode)
1534    inode->removed = true;
1535  }
1536
1537 +/* Translates SECTOR_IDX into a sequence of block indexes in
1538 +   OFFSETS and sets *OFFSET_CNT to the number of offsets. */
1539 +static void
1540 +calculate_indices (off_t sector_idx, size_t offsets[], size_t *offset_cnt)
1541 +{
1542 +  /* Handle direct blocks. */
1543 +  if (sector_idx < DIRECT_CNT)
1544 +    {
1545 +      offsets[0] = sector_idx;
1546 +      *offset_cnt = 1;
1547 +      return;
1548 +    }
1549 +  sector_idx -= DIRECT_CNT;
1550 +
1551 +  /* Handle indirect blocks. */
1552 +  if (sector_idx < PTRS_PER_SECTOR * INDIRECT_CNT)
1553 +    {
1554 +      offsets[0] = DIRECT_CNT + sector_idx / PTRS_PER_SECTOR;
1555 +      offsets[1] = sector_idx % PTRS_PER_SECTOR;
1556 +      *offset_cnt = 2;
1557 +      return;
1558 +    }
1559 +  sector_idx -= PTRS_PER_SECTOR * INDIRECT_CNT;
1560 +
1561 +  /* Handle doubly indirect blocks. */
1562 +  if (sector_idx < DBL_INDIRECT_CNT * PTRS_PER_SECTOR * PTRS_PER_SECTOR)
1563 +    {
1564 +      offsets[0] = (DIRECT_CNT + INDIRECT_CNT
1565 +                    + sector_idx / (PTRS_PER_SECTOR * PTRS_PER_SECTOR));
1566 +      offsets[1] = sector_idx / PTRS_PER_SECTOR;
1567 +      offsets[2] = sector_idx % PTRS_PER_SECTOR;
1568 +      *offset_cnt = 3;
1569 +      return;
1570 +    }
1571 +  NOT_REACHED ();
1572 +}
1573 +
1574 +/* Retrieves the data block for the given byte OFFSET in INODE,
1575 +   setting *DATA_BLOCK to the block.
1576 +   Returns true if successful, false on failure.
1577 +   If ALLOCATE is false, then missing blocks will be successful
1578 +   with *DATA_BLOCk set to a null pointer.
1579 +   If ALLOCATE is true, then missing blocks will be allocated.
1580 +   The block returned will be locked, normally non-exclusively,
1581 +   but a newly allocated block will have an exclusive lock. */
1582 +static bool
1583 +get_data_block (struct inode *inode, off_t offset, bool allocate,
1584 +                struct cache_block **data_block)
1585 +{
1586 +  block_sector_t this_level_sector;
1587 +  size_t offsets[3];
1588 +  size_t offset_cnt;
1589 +  size_t level;
1590 +
1591 +  ASSERT (offset >= 0);
1592 +
1593 +  calculate_indices (offset / BLOCK_SECTOR_SIZE, offsets, &offset_cnt);
1594 +  level = 0;
1595 +  this_level_sector = inode->sector;
1596 +  for (;;)
1597 +    {
1598 +      struct cache_block *this_level_block;
1599 +      uint32_t *this_level_data;
1600 +
1601 +      struct cache_block *next_level_block;
1602 +
1603 +      /* Check whether the block for the next level is allocated. */
1604 +      this_level_block = cache_lock (this_level_sector, NON_EXCLUSIVE);
1605 +      this_level_data = cache_read (this_level_block);
1606 +      if (this_level_data[offsets[level]] != 0)
1607 +        {
1608 +          /* Yes, it's allocated.  Advance to next level. */
1609 +          this_level_sector = this_level_data[offsets[level]];
1610 +
1611 +          if (++level == offset_cnt)
1612 +            {
1613 +              /* We hit the data block.
1614 +                 Do read-ahead. */
1615 +              if ((level == 0 && offsets[level] + 1 < DIRECT_CNT)
1616 +                  || (level > 0 && offsets[level] + 1 < PTRS_PER_SECTOR))
1617 +                {
1618 +                  uint32_t next_sector = this_level_data[offsets[level] + 1];
1619 +                  if (next_sector
1620 +                      && next_sector < block_size (fs_device))
1621 +                    cache_readahead (next_sector);
1622 +                }
1623 +              cache_unlock (this_level_block);
1624 +
1625 +              /* Return block. */
1626 +              *data_block = cache_lock (this_level_sector, NON_EXCLUSIVE);
1627 +              return true;
1628 +            }
1629 +          cache_unlock (this_level_block);
1630 +          continue;
1631 +        }
1632 +      cache_unlock (this_level_block);
1633 +
1634 +      /* No block is allocated.  Nothing is locked.
1635 +         If we're not allocating new blocks, then this is
1636 +         "success" (with all-zero data). */
1637 +      if (!allocate)
1638 +        {
1639 +          *data_block = NULL;
1640 +          return true;
1641 +        }
1642 +
1643 +      /* We need to allocate a new block.
1644 +         Grab an exclusive lock on this level's block so we can
1645 +         insert the new block. */
1646 +      this_level_block = cache_lock (this_level_sector, EXCLUSIVE);
1647 +      this_level_data = cache_read (this_level_block);
1648 +
1649 +      /* Since we released this level's block, someone else might
1650 +         have allocated the block in the meantime.  Recheck. */
1651 +      if (this_level_data[offsets[level]] != 0)
1652 +        {
1653 +          cache_unlock (this_level_block);
1654 +          continue;
1655 +        }
1656 +
1657 +      /* Allocate the new block. */
1658 +      if (!free_map_allocate (&this_level_data[offsets[level]]))
1659 +        {
1660 +          cache_unlock (this_level_block);
1661 +          *data_block = NULL;
1662 +          return false;
1663 +        }
1664 +      cache_dirty (this_level_block);
1665 +
1666 +      /* Lock and clear the new block. */
1667 +      next_level_block = cache_lock (this_level_data[offsets[level]],
1668 +                                     EXCLUSIVE);
1669 +      cache_zero (next_level_block);
1670 +
1671 +      /* Release this level's block.  No one else can access the
1672 +         new block yet, because we have an exclusive lock on it. */
1673 +      cache_unlock (this_level_block);
1674 +
1675 +      /* If this is the final level, then return the new block. */
1676 +      if (level == offset_cnt - 1)
1677 +        {
1678 +          *data_block = next_level_block;
1679 +          return true;
1680 +        }
1681 +
1682 +      /* Otherwise, release the new block and go around again to
1683 +         follow the new pointer. */
1684 +      cache_unlock (next_level_block);
1685 +    }
1686 +}
1687 +
1688  /* Reads SIZE bytes from INODE into BUFFER, starting at position OFFSET.
1689     Returns the number of bytes actually read, which may be less
1690     than SIZE if an error occurs or end of file is reached. */
1691 @@ -202,13 +413,12 @@ inode_read_at (struct inode *inode, void *buffer_, off_t size, off_t offset)
1692  {
1693    uint8_t *buffer = buffer_;
1694    off_t bytes_read = 0;
1695 -  uint8_t *bounce = NULL;
1696
1697    while (size > 0)
1698      {
1699 -      /* Disk sector to read, starting byte offset within sector. */
1700 -      block_sector_t sector_idx = byte_to_sector (inode, offset);
1701 +      /* Sector to read, starting byte offset within sector, sector data. */
1702        int sector_ofs = offset % BLOCK_SECTOR_SIZE;
1703 +      struct cache_block *block;
1704
1705        /* Bytes left in inode, bytes left in sector, lesser of the two. */
1706        off_t inode_left = inode_length (inode) - offset;
1707 @@ -217,26 +427,16 @@ inode_read_at (struct inode *inode, void *buffer_, off_t size, off_t offset)
1708
1709        /* Number of bytes to actually copy out of this sector. */
1710        int chunk_size = size < min_left ? size : min_left;
1711 -      if (chunk_size <= 0)
1712 +      if (chunk_size <= 0 || !get_data_block (inode, offset, false, &block))
1713          break;
1714
1715 -      if (sector_ofs == 0 && chunk_size == BLOCK_SECTOR_SIZE)
1716 -        {
1717 -          /* Read full sector directly into caller's buffer. */
1718 -          block_read (fs_device, sector_idx, buffer + bytes_read);
1719 -        }
1720 +      if (block == NULL)
1721 +        memset (buffer + bytes_read, 0, chunk_size);
1722        else
1723          {
1724 -          /* Read sector into bounce buffer, then partially copy
1725 -             into caller's buffer. */
1726 -          if (bounce == NULL)
1727 -            {
1728 -              bounce = malloc (BLOCK_SECTOR_SIZE);
1729 -              if (bounce == NULL)
1730 -                break;
1731 -            }
1732 -          block_read (fs_device, sector_idx, bounce);
1733 -          memcpy (buffer + bytes_read, bounce + sector_ofs, chunk_size);
1734 +          const uint8_t *sector_data = cache_read (block);
1735 +          memcpy (buffer + bytes_read, sector_data + sector_ofs, chunk_size);
1736 +          cache_unlock (block);
1737          }
1738
1739        /* Advance. */
1740 @@ -244,75 +444,82 @@ inode_read_at (struct inode *inode, void *buffer_, off_t size, off_t offset)
1741        offset += chunk_size;
1742        bytes_read += chunk_size;
1743      }
1744 -  free (bounce);
1745
1746    return bytes_read;
1747  }
1748
1749 +/* Extends INODE to be at least LENGTH bytes long. */
1750 +static void
1751 +extend_file (struct inode *inode, off_t length)
1752 +{
1753 +  if (length > inode_length (inode))
1754 +    {
1755 +      struct cache_block *inode_block = cache_lock (inode->sector, EXCLUSIVE);
1756 +      struct inode_disk *disk_inode = cache_read (inode_block);
1757 +      if (length > disk_inode->length)
1758 +        {
1759 +          disk_inode->length = length;
1760 +          cache_dirty (inode_block);
1761 +        }
1762 +      cache_unlock (inode_block);
1763 +    }
1764 +}
1765 +
1766  /* Writes SIZE bytes from BUFFER into INODE, starting at OFFSET.
1767     Returns the number of bytes actually written, which may be
1768 -   less than SIZE if end of file is reached or an error occurs.
1769 -   (Normally a write at end of file would extend the inode, but
1770 -   growth is not yet implemented.) */
1771 +   less than SIZE if an error occurs. */
1772  off_t
1773  inode_write_at (struct inode *inode, const void *buffer_, off_t size,
1774                  off_t offset)
1775  {
1776    const uint8_t *buffer = buffer_;
1777    off_t bytes_written = 0;
1778 -  uint8_t *bounce = NULL;
1779
1780 -  if (inode->deny_write_cnt)
1781 -    return 0;
1782 +  /* Don't write if writes are denied. */
1783 +  lock_acquire (&inode->deny_write_lock);
1784 +  if (inode->deny_write_cnt)
1785 +    {
1786 +      lock_release (&inode->deny_write_lock);
1787 +      return 0;
1788 +    }
1789 +  inode->writer_cnt++;
1790 +  lock_release (&inode->deny_write_lock);
1791
1792    while (size > 0)
1793      {
1794 -      /* Sector to write, starting byte offset within sector. */
1795 -      block_sector_t sector_idx = byte_to_sector (inode, offset);
1796 +      /* Sector to write, starting byte offset within sector, sector data. */
1797        int sector_ofs = offset % BLOCK_SECTOR_SIZE;
1798 +      struct cache_block *block;
1799 +      uint8_t *sector_data;
1800
1801 -      /* Bytes left in inode, bytes left in sector, lesser of the two. */
1802 -      off_t inode_left = inode_length (inode) - offset;
1803 +      /* Bytes to max inode size, bytes left in sector, lesser of the two. */
1804 +      off_t inode_left = INODE_SPAN - offset;
1805        int sector_left = BLOCK_SECTOR_SIZE - sector_ofs;
1806        int min_left = inode_left < sector_left ? inode_left : sector_left;
1807
1808        /* Number of bytes to actually write into this sector. */
1809        int chunk_size = size < min_left ? size : min_left;
1810 -      if (chunk_size <= 0)
1811 -        break;
1812
1813 -      if (sector_ofs == 0 && chunk_size == BLOCK_SECTOR_SIZE)
1814 -        {
1815 -          /* Write full sector directly to disk. */
1816 -          block_write (fs_device, sector_idx, buffer + bytes_written);
1817 -        }
1818 -      else
1819 -        {
1820 -          /* We need a bounce buffer. */
1821 -          if (bounce == NULL)
1822 -            {
1823 -              bounce = malloc (BLOCK_SECTOR_SIZE);
1824 -              if (bounce == NULL)
1825 -                break;
1826 -            }
1827 +      if (chunk_size <= 0 || !get_data_block (inode, offset, true, &block))
1828 +        break;
1829
1830 -          /* If the sector contains data before or after the chunk
1831 -             we're writing, then we need to read in the sector
1832 -             first.  Otherwise we start with a sector of all zeros. */
1833 -          if (sector_ofs > 0 || chunk_size < sector_left)
1834 -            block_read (fs_device, sector_idx, bounce);
1835 -          else
1836 -            memset (bounce, 0, BLOCK_SECTOR_SIZE);
1837 -          memcpy (bounce + sector_ofs, buffer + bytes_written, chunk_size);
1838 -          block_write (fs_device, sector_idx, bounce);
1839 -        }
1840 +      sector_data = cache_read (block);
1841 +      memcpy (sector_data + sector_ofs, buffer + bytes_written, chunk_size);
1842 +      cache_dirty (block);
1843 +      cache_unlock (block);
1844
1845        /* Advance. */
1846        size -= chunk_size;
1847        offset += chunk_size;
1848        bytes_written += chunk_size;
1849      }
1850 -  free (bounce);
1851 +
1852 +  extend_file (inode, offset);
1853 +
1854 +  lock_acquire (&inode->deny_write_lock);
1855 +  if (--inode->writer_cnt == 0)
1856 +    cond_signal (&inode->no_writers_cond, &inode->deny_write_lock);
1857 +  lock_release (&inode->deny_write_lock);
1858
1859    return bytes_written;
1860  }
1861 @@ -322,8 +529,12 @@ inode_write_at (struct inode *inode, const void *buffer_, off_t size,
1862  void
1863  inode_deny_write (struct inode *inode)
1864  {
1865 +  lock_acquire (&inode->deny_write_lock);
1866 +  while (inode->writer_cnt > 0)
1867 +    cond_wait (&inode->no_writers_cond, &inode->deny_write_lock);
1868 +  ASSERT (inode->deny_write_cnt < inode->open_cnt);
1869    inode->deny_write_cnt++;
1870 -  ASSERT (inode->deny_write_cnt <= inode->open_cnt);
1871 +  lock_release (&inode->deny_write_lock);
1872  }
1873
1874  /* Re-enables writes to INODE.
1875 @@ -332,14 +543,47 @@ inode_deny_write (struct inode *inode)
1876  void
1877  inode_allow_write (struct inode *inode)
1878  {
1879 +  lock_acquire (&inode->deny_write_lock);
1880    ASSERT (inode->deny_write_cnt > 0);
1881    ASSERT (inode->deny_write_cnt <= inode->open_cnt);
1882    inode->deny_write_cnt--;
1883 +  lock_release (&inode->deny_write_lock);
1884  }
1885
1886  /* Returns the length, in bytes, of INODE's data. */
1887  off_t
1888  inode_length (const struct inode *inode)
1889  {
1890 -  return inode->data.length;
1891 +  struct cache_block *inode_block = cache_lock (inode->sector, NON_EXCLUSIVE);
1892 +  struct inode_disk *disk_inode = cache_read (inode_block);
1893 +  off_t length = disk_inode->length;
1894 +  cache_unlock (inode_block);
1895 +  return length;
1896 +}
1897 +
1898 +/* Returns the number of openers. */
1899 +int
1900 +inode_open_cnt (const struct inode *inode)
1901 +{
1902 +  int open_cnt;
1903 +
1904 +  lock_acquire (&open_inodes_lock);
1905 +  open_cnt = inode->open_cnt;
1906 +  lock_release (&open_inodes_lock);
1907 +
1908 +  return open_cnt;
1909 +}
1910 +
1911 +/* Locks INODE. */
1912 +void
1913 +inode_lock (struct inode *inode)
1914 +{
1915 +  lock_acquire (&inode->lock);
1916 +}
1917 +
1918 +/* Releases INODE's lock. */
1919 +void
1920 +inode_unlock (struct inode *inode)
1921 +{
1922 +  lock_release (&inode->lock);
1923  }
1924 diff --git a/src/filesys/inode.h b/src/filesys/inode.h
1925 index cb42310..380d1b7 100644
1926 --- a/src/filesys/inode.h
1927 +++ b/src/filesys/inode.h
1928 @@ -7,10 +7,18 @@
1929
1930  struct bitmap;
1931
1932 +/* Type of an inode. */
1933 +enum inode_type
1934 +  {
1935 +    FILE_INODE,         /* Ordinary file. */
1936 +    DIR_INODE           /* Directory. */
1937 +  };
1938 +
1939  void inode_init (void);
1940 -bool inode_create (block_sector_t, off_t);
1941 +struct inode *inode_create (block_sector_t, enum inode_type);
1942  struct inode *inode_open (block_sector_t);
1943  struct inode *inode_reopen (struct inode *);
1944 +enum inode_type inode_get_type (const struct inode *);
1945  block_sector_t inode_get_inumber (const struct inode *);
1946  void inode_close (struct inode *);
1947  void inode_remove (struct inode *);
1948 @@ -19,5 +27,8 @@ off_t inode_write_at (struct inode *, const void *, off_t size, off_t offset);
1949  void inode_deny_write (struct inode *);
1950  void inode_allow_write (struct inode *);
1951  off_t inode_length (const struct inode *);
1952 +int inode_open_cnt (const struct inode *);
1953 +void inode_lock (struct inode *);
1954 +void inode_unlock (struct inode *);
1955
1956  #endif /* filesys/inode.h */
1957 diff --git a/src/threads/thread.c b/src/threads/thread.c
1958 index f9f2310..1c82b6c 100644
1959 --- a/src/threads/thread.c
1960 +++ b/src/threads/thread.c
1961 @@ -475,6 +475,7 @@ init_thread (struct thread *t, const char *name, int priority, tid_t tid)
1962    list_init (&t->fds);
1963    list_init (&t->mappings);
1964    t->next_handle = 2;
1965 +  t->wd = NULL;
1966    t->magic = THREAD_MAGIC;
1967    old_level = intr_disable ();
1968    list_push_back (&all_list, &t->allelem);
1969 diff --git a/src/threads/thread.h b/src/threads/thread.h
1970 index b9e7b0c..b60376f 100644
1971 --- a/src/threads/thread.h
1972 +++ b/src/threads/thread.h
1973 @@ -115,6 +115,7 @@ struct thread
1974      struct list mappings;               /* Memory-mapped files. */
1975      int next_handle;                    /* Next handle value. */
1976      void *user_esp;                     /* User's stack pointer. */
1977 +    struct dir *wd;                     /* Working directory. */
1978
1979      /* Owned by thread.c. */
1980      unsigned magic;                     /* Detects stack overflow. */
1981 diff --git a/src/userprog/process.c b/src/userprog/process.c
1982 index 7a15814..3d16752 100644
1983 --- a/src/userprog/process.c
1984 +++ b/src/userprog/process.c
1985 @@ -32,6 +32,7 @@ struct exec_info
1986      const char *file_name;              /* Program to load. */
1987      struct semaphore load_done;         /* "Up"ed when loading complete. */
1988      struct wait_status *wait_status;    /* Child process. */
1989 +    struct dir *wd;                     /* Working directory. */
1990      bool success;                       /* Program successfully loaded? */
1991    };
1992
1993 @@ -42,6 +43,7 @@ struct exec_info
1994  tid_t
1995  process_execute (const char *file_name)
1996  {
1997 +  struct dir *wd = thread_current ()->wd;
1998    struct exec_info exec;
1999    char thread_name[16];
2000    char *save_ptr;
2001 @@ -49,6 +51,9 @@ process_execute (const char *file_name)
2002
2003    /* Initialize exec_info. */
2004    exec.file_name = file_name;
2005 +  exec.wd = wd != NULL ? dir_reopen (wd) : dir_open_root ();
2006 +  if (exec.wd == NULL)
2007 +    return TID_ERROR;
2008    sema_init (&exec.load_done, 0);
2009
2010    /* Create a new thread to execute FILE_NAME. */
2011 @@ -61,8 +66,13 @@ process_execute (const char *file_name)
2012        if (exec.success)
2013          list_push_back (&thread_current ()->children, &exec.wait_status->elem);
2014        else
2015 -        tid = TID_ERROR;
2016 +        {
2017 +          tid = TID_ERROR;
2018 +          /* Don't close exec.wd; child process will have done so. */
2019 +        }
2020      }
2021 +  else
2022 +    dir_close (exec.wd);
2023
2024    return tid;
2025  }
2026 @@ -76,6 +86,8 @@ start_process (void *exec_)
2027    struct intr_frame if_;
2028    bool success;
2029
2030 +  thread_current ()->wd = exec->wd;
2031 +
2032    /* Initialize interrupt frame and load executable. */
2033    memset (&if_, 0, sizeof if_);
2034    if_.gs = if_.fs = if_.es = if_.ds = if_.ss = SEL_UDSEG;
2035 @@ -334,13 +346,13 @@ load (const char *cmd_line, void (**eip) (void), void **esp)
2036      *cp = '\0';
2037
2038    /* Open executable file. */
2039 -  t->bin_file = file = filesys_open (file_name);
2040 +  t->bin_file = file = file_open (filesys_open (file_name));
2041    if (file == NULL)
2042      {
2043        printf ("load: %s: open failed\n", file_name);
2044        goto done;
2045      }
2046 -  file_deny_write (t->bin_file);
2047 +  file_deny_write (file);
2048
2049    /* Read and verify executable header. */
2050    if (file_read (file, &ehdr, sizeof ehdr) != sizeof ehdr
2051 diff --git a/src/userprog/syscall.c b/src/userprog/syscall.c
2052 index e6be702..e41cbcd 100644
2053 --- a/src/userprog/syscall.c
2054 +++ b/src/userprog/syscall.c
2055 @@ -9,6 +9,7 @@
2056  #include "filesys/directory.h"
2057  #include "filesys/filesys.h"
2058  #include "filesys/file.h"
2059 +#include "threads/init.h"
2060  #include "threads/interrupt.h"
2061  #include "threads/malloc.h"
2062  #include "threads/palloc.h"
2063 @@ -32,17 +33,19 @@ static int sys_tell (int handle);
2064  static int sys_close (int handle);
2065  static int sys_mmap (int handle, void *addr);
2066  static int sys_munmap (int mapping);
2067 +static int sys_chdir (const char *udir);
2068 +static int sys_mkdir (const char *udir);
2069 +static int sys_readdir (int handle, char *name);
2070 +static int sys_isdir (int handle);
2071 +static int sys_inumber (int handle);
2072
2073  static void syscall_handler (struct intr_frame *);
2074  static void copy_in (void *, const void *, size_t);
2075 -
2076 -static struct lock fs_lock;
2077
2078  void
2079  syscall_init (void)
2080  {
2081    intr_register_int (0x30, 3, INTR_ON, syscall_handler, "syscall");
2082 -  lock_init (&fs_lock);
2083  }
2084
2085  /* System call handler. */
2086 @@ -76,6 +79,11 @@ syscall_handler (struct intr_frame *f)
2087        {1, (syscall_function *) sys_close},
2088        {2, (syscall_function *) sys_mmap},
2089        {1, (syscall_function *) sys_munmap},
2090 +      {1, (syscall_function *) sys_chdir},
2091 +      {1, (syscall_function *) sys_mkdir},
2092 +      {2, (syscall_function *) sys_readdir},
2093 +      {1, (syscall_function *) sys_isdir},
2094 +      {1, (syscall_function *) sys_inumber},
2095      };
2096
2097    const struct syscall *sc;
2098 @@ -124,6 +132,32 @@ copy_in (void *dst_, const void *usrc_, size_t size)
2099      }
2100  }
2101
2102 +/* Copies SIZE bytes from kernel address SRC to user address
2103 +   UDST.
2104 +   Call thread_exit() if any of the user accesses are invalid. */
2105 +static void
2106 +copy_out (void *udst_, const void *src_, size_t size)
2107 +{
2108 +  uint8_t *udst = udst_;
2109 +  const uint8_t *src = src_;
2110 +
2111 +  while (size > 0)
2112 +    {
2113 +      size_t chunk_size = PGSIZE - pg_ofs (udst);
2114 +      if (chunk_size > size)
2115 +        chunk_size = size;
2116 +
2117 +      if (!page_lock (udst, false))
2118 +        thread_exit ();
2119 +      memcpy (udst, src, chunk_size);
2120 +      page_unlock (udst);
2121 +
2122 +      udst += chunk_size;
2123 +      src += chunk_size;
2124 +      size -= chunk_size;
2125 +    }
2126 +}
2127 +
2128  /* Creates a copy of user string US in kernel memory
2129     and returns it as a page that must be freed with
2130     palloc_free_page().
2131 @@ -191,10 +225,8 @@ sys_exec (const char *ufile)
2132  {
2133    tid_t tid;
2134    char *kfile = copy_in_string (ufile);
2135 -
2136 -  lock_acquire (&fs_lock);
2137 +
2138    tid = process_execute (kfile);
2139 -  lock_release (&fs_lock);
2140
2141    palloc_free_page (kfile);
2142
2143 @@ -213,12 +245,7 @@ static int
2144  sys_create (const char *ufile, unsigned initial_size)
2145  {
2146    char *kfile = copy_in_string (ufile);
2147 -  bool ok;
2148 -
2149 -  lock_acquire (&fs_lock);
2150 -  ok = filesys_create (kfile, initial_size);
2151 -  lock_release (&fs_lock);
2152 -
2153 +  bool ok = filesys_create (kfile, initial_size, FILE_INODE);
2154    palloc_free_page (kfile);
2155
2156    return ok;
2157 @@ -229,12 +256,7 @@ static int
2158  sys_remove (const char *ufile)
2159  {
2160    char *kfile = copy_in_string (ufile);
2161 -  bool ok;
2162 -
2163 -  lock_acquire (&fs_lock);
2164 -  ok = filesys_remove (kfile);
2165 -  lock_release (&fs_lock);
2166 -
2167 +  bool ok = filesys_remove (kfile);
2168    palloc_free_page (kfile);
2169
2170    return ok;
2171 @@ -245,6 +267,7 @@ struct file_descriptor
2172    {
2173      struct list_elem elem;      /* List element. */
2174      struct file *file;          /* File. */
2175 +    struct dir *dir;            /* Directory. */
2176      int handle;                 /* File handle. */
2177    };
2178
2179 @@ -256,20 +279,28 @@ sys_open (const char *ufile)
2180    struct file_descriptor *fd;
2181    int handle = -1;
2182
2183 -  fd = malloc (sizeof *fd);
2184 +  fd = calloc (1, sizeof *fd);
2185    if (fd != NULL)
2186      {
2187 -      lock_acquire (&fs_lock);
2188 -      fd->file = filesys_open (kfile);
2189 -      if (fd->file != NULL)
2190 +      struct inode *inode = filesys_open (kfile);
2191 +      if (inode != NULL)
2192          {
2193 -          struct thread *cur = thread_current ();
2194 -          handle = fd->handle = cur->next_handle++;
2195 -          list_push_front (&cur->fds, &fd->elem);
2196 +          if (inode_get_type (inode) == FILE_INODE)
2197 +            fd->file = file_open (inode);
2198 +          else
2199 +            fd->dir = dir_open (inode);
2200 +          if (fd->file != NULL || fd->dir != NULL)
2201 +            {
2202 +              struct thread *cur = thread_current ();
2203 +              handle = fd->handle = cur->next_handle++;
2204 +              list_push_front (&cur->fds, &fd->elem);
2205 +            }
2206 +          else
2207 +            {
2208 +              free (fd);
2209 +              inode_close (inode);
2210 +            }
2211          }
2212 -      else
2213 -        free (fd);
2214 -      lock_release (&fs_lock);
2215      }
2216
2217    palloc_free_page (kfile);
2218 @@ -297,16 +328,38 @@ lookup_fd (int handle)
2219    thread_exit ();
2220  }
2221
2222 +/* Returns the file descriptor associated with the given handle.
2223 +   Terminates the process if HANDLE is not associated with an
2224 +   open ordinary file. */
2225 +static struct file_descriptor *
2226 +lookup_file_fd (int handle)
2227 +{
2228 +  struct file_descriptor *fd = lookup_fd (handle);
2229 +  if (fd->file == NULL)
2230 +    thread_exit ();
2231 +  return fd;
2232 +}
2233 +
2234 +/* Returns the file descriptor associated with the given handle.
2235 +   Terminates the process if HANDLE is not associated with an
2236 +   open directory. */
2237 +static struct file_descriptor *
2238 +lookup_dir_fd (int handle)
2239 +{
2240 +  struct file_descriptor *fd = lookup_fd (handle);
2241 +  if (fd->dir == NULL)
2242 +    thread_exit ();
2243 +  return fd;
2244 +}
2245 +
2246  /* Filesize system call. */
2247  static int
2248  sys_filesize (int handle)
2249  {
2250 -  struct file_descriptor *fd = lookup_fd (handle);
2251 +  struct file_descriptor *fd = lookup_file_fd (handle);
2252    int size;
2253
2254 -  lock_acquire (&fs_lock);
2255    size = file_length (fd->file);
2256 -  lock_release (&fs_lock);
2257
2258    return size;
2259  }
2260 @@ -319,7 +372,10 @@ sys_read (int handle, void *udst_, unsigned size)
2261    struct file_descriptor *fd;
2262    int bytes_read = 0;
2263
2264 -  fd = lookup_fd (handle);
2265 +  /* Look up file descriptor. */
2266 +  if (handle != STDIN_FILENO)
2267 +    fd = lookup_file_fd (handle);
2268 +
2269    while (size > 0)
2270      {
2271        /* How much to read into this page? */
2272 @@ -327,44 +383,37 @@ sys_read (int handle, void *udst_, unsigned size)
2273        size_t read_amt = size < page_left ? size : page_left;
2274        off_t retval;
2275
2276 +      /* Check that touching this page is okay. */
2277 +      if (!page_lock (udst, true))
2278 +        thread_exit ();
2279 +
2280        /* Read from file into page. */
2281        if (handle != STDIN_FILENO)
2282          {
2283 -          if (!page_lock (udst, true))
2284 -            thread_exit ();
2285 -          lock_acquire (&fs_lock);
2286            retval = file_read (fd->file, udst, read_amt);
2287 -          lock_release (&fs_lock);
2288 -          page_unlock (udst);
2289 +          if (retval < 0)
2290 +            {
2291 +              if (bytes_read == 0)
2292 +                bytes_read = -1;
2293 +              break;
2294 +            }
2295 +          bytes_read += retval;
2296          }
2297        else
2298          {
2299            size_t i;
2300
2301            for (i = 0; i < read_amt; i++)
2302 -            {
2303 -              char c = input_getc ();
2304 -              if (!page_lock (udst, true))
2305 -                thread_exit ();
2306 -              udst[i] = c;
2307 -              page_unlock (udst);
2308 -            }
2309 +            udst[i] = input_getc ();
2310            bytes_read = read_amt;
2311          }
2312 -
2313 -      /* Check success. */
2314 -      if (retval < 0)
2315 -        {
2316 -          if (bytes_read == 0)
2317 -            bytes_read = -1;
2318 -          break;
2319 -        }
2320 -      bytes_read += retval;
2321 -      if (retval != (off_t) read_amt)
2322 -        {
2323 -          /* Short read, so we're done. */
2324 -          break;
2325 -        }
2326 +
2327 +      /* Release page. */
2328 +      page_unlock (udst);
2329 +
2330 +      /* If it was a short read we're done. */
2331 +      if (retval != (off_t) read_amt)
2332 +        break;
2333
2334        /* Advance. */
2335        udst += retval;
2336 @@ -384,7 +433,7 @@ sys_write (int handle, void *usrc_, unsigned size)
2337
2338    /* Lookup up file descriptor. */
2339    if (handle != STDOUT_FILENO)
2340 -    fd = lookup_fd (handle);
2341 +    fd = lookup_file_fd (handle);
2342
2343    while (size > 0)
2344      {
2345 @@ -393,10 +442,11 @@ sys_write (int handle, void *usrc_, unsigned size)
2346        size_t write_amt = size < page_left ? size : page_left;
2347        off_t retval;
2348
2349 -      /* Write from page into file. */
2350 +      /* Check that we can touch this user page. */
2351        if (!page_lock (usrc, false))
2352          thread_exit ();
2353 -      lock_acquire (&fs_lock);
2354 +
2355 +      /* Do the write. */
2356        if (handle == STDOUT_FILENO)
2357          {
2358            putbuf ((char *) usrc, write_amt);
2359 @@ -404,7 +454,8 @@ sys_write (int handle, void *usrc_, unsigned size)
2360          }
2361        else
2362          retval = file_write (fd->file, usrc, write_amt);
2363 -      lock_release (&fs_lock);
2364 +
2365 +      /* Release user page. */
2366        page_unlock (usrc);
2367
2368        /* Handle return value. */
2369 @@ -432,13 +483,8 @@ sys_write (int handle, void *usrc_, unsigned size)
2370  static int
2371  sys_seek (int handle, unsigned position)
2372  {
2373 -  struct file_descriptor *fd = lookup_fd (handle);
2374 -
2375 -  lock_acquire (&fs_lock);
2376    if ((off_t) position >= 0)
2377 -    file_seek (fd->file, position);
2378 -  lock_release (&fs_lock);
2379 -
2380 +    file_seek (lookup_file_fd (handle)->file, position);
2381    return 0;
2382  }
2383
2384 @@ -446,14 +492,7 @@ sys_seek (int handle, unsigned position)
2385  static int
2386  sys_tell (int handle)
2387  {
2388 -  struct file_descriptor *fd = lookup_fd (handle);
2389 -  unsigned position;
2390 -
2391 -  lock_acquire (&fs_lock);
2392 -  position = file_tell (fd->file);
2393 -  lock_release (&fs_lock);
2394 -
2395 -  return position;
2396 +  return file_tell (lookup_file_fd (handle)->file);
2397  }
2398
2399  /* Close system call. */
2400 @@ -461,9 +500,8 @@ static int
2401  sys_close (int handle)
2402  {
2403    struct file_descriptor *fd = lookup_fd (handle);
2404 -  lock_acquire (&fs_lock);
2405    file_close (fd->file);
2406 -  lock_release (&fs_lock);
2407 +  dir_close (fd->dir);
2408    list_remove (&fd->elem);
2409    free (fd);
2410    return 0;
2411 @@ -518,7 +556,7 @@ unmap (struct mapping *m)
2412  static int
2413  sys_mmap (int handle, void *addr)
2414  {
2415 -  struct file_descriptor *fd = lookup_fd (handle);
2416 +  struct file_descriptor *fd = lookup_file_fd (handle);
2417    struct mapping *m = malloc (sizeof *m);
2418    size_t offset;
2419    off_t length;
2420 @@ -527,9 +565,7 @@ sys_mmap (int handle, void *addr)
2421      return -1;
2422
2423    m->handle = thread_current ()->next_handle++;
2424 -  lock_acquire (&fs_lock);
2425    m->file = file_reopen (fd->file);
2426 -  lock_release (&fs_lock);
2427    if (m->file == NULL)
2428      {
2429        free (m);
2430 @@ -540,9 +576,7 @@ sys_mmap (int handle, void *addr)
2431    list_push_front (&thread_current ()->mappings, &m->elem);
2432
2433    offset = 0;
2434 -  lock_acquire (&fs_lock);
2435    length = file_length (m->file);
2436 -  lock_release (&fs_lock);
2437    while (length > 0)
2438      {
2439        struct page *p = page_allocate ((uint8_t *) addr + offset, false);
2440 @@ -570,6 +604,58 @@ sys_munmap (int mapping)
2441    unmap (lookup_mapping (mapping));
2442    return 0;
2443  }
2444 +
2445 +/* Chdir system call. */
2446 +static int
2447 +sys_chdir (const char *udir)
2448 +{
2449 +  char *kdir = copy_in_string (udir);
2450 +  bool ok = filesys_chdir (kdir);
2451 +  palloc_free_page (kdir);
2452 +  return ok;
2453 +}
2454 +
2455 +/* Mkdir system call. */
2456 +static int
2457 +sys_mkdir (const char *udir)
2458 +{
2459 +  char *kdir = copy_in_string (udir);
2460 +  bool ok = filesys_create (kdir, 0, DIR_INODE);
2461 +  palloc_free_page (kdir);
2462 +
2463 +  return ok;
2464 +}
2465 +
2466 +/* Readdir system call. */
2467 +static int
2468 +sys_readdir (int handle, char *uname)
2469 +{
2470 +  struct file_descriptor *fd = lookup_dir_fd (handle);
2471 +  char name[NAME_MAX + 1];
2472 +  bool ok = dir_readdir (fd->dir, name);
2473 +  if (ok)
2474 +    copy_out (uname, name, strlen (name) + 1);
2475 +  return ok;
2476 +}
2477 +
2478 +/* Isdir system call. */
2479 +static int
2480 +sys_isdir (int handle)
2481 +{
2482 +  struct file_descriptor *fd = lookup_fd (handle);
2483 +  return fd->dir != NULL;
2484 +}
2485 +
2486 +/* Inumber system call. */
2487 +static int
2488 +sys_inumber (int handle)
2489 +{
2490 +  struct file_descriptor *fd = lookup_fd (handle);
2491 +  struct inode *inode = (fd->file
2492 +                         ? file_get_inode (fd->file)
2493 +                         : dir_get_inode (fd->dir));
2494 +  return inode_get_inumber (inode);
2495 +}
2496  \f
2497  /* On thread exit, close all open files and unmap all mappings. */
2498  void
2499 @@ -582,9 +668,8 @@ syscall_exit (void)
2500      {
2501        struct file_descriptor *fd = list_entry (e, struct file_descriptor, elem);
2502        next = list_next (e);
2503 -      lock_acquire (&fs_lock);
2504        file_close (fd->file);
2505 -      lock_release (&fs_lock);
2506 +      dir_close (fd->dir);
2507        free (fd);
2508      }
2509
2510 @@ -595,4 +680,6 @@ syscall_exit (void)
2511        next = list_next (e);
2512        unmap (m);
2513      }
2514 +
2515 +  dir_close (cur->wd);
2516  }
2517 diff --git a/src/vm/frame.c b/src/vm/frame.c
2518 index ef55376..39b4cec 100644
2519 --- a/src/vm/frame.c
2520 +++ b/src/vm/frame.c
2521 @@ -100,7 +100,6 @@ try_frame_alloc_and_lock (struct page *page)
2522    return NULL;
2523  }
2524
2525 -
2526  /* Tries really hard to allocate and lock a frame for PAGE.
2527     Returns the frame if successful, false on failure. */
2528  struct frame *
2529 diff --git a/src/vm/page.c b/src/vm/page.c
2530 index f08bcf8..62aab36 100644
2531 --- a/src/vm/page.c
2532 +++ b/src/vm/page.c
2533 @@ -24,6 +24,7 @@ destroy_page (struct hash_elem *p_, void *aux UNUSED)
2534    free (p);
2535  }
2536
2537 +
2538  /* Destroys the current process's page table. */
2539  void
2540  page_exit (void)
2541 diff --git a/src/vm/swap.c b/src/vm/swap.c
2542 index 76fcf71..ce9d25e 100644
2543 --- a/src/vm/swap.c
2544 +++ b/src/vm/swap.c
2545 @@ -4,10 +4,11 @@
2546  #include <stdio.h>
2547  #include "vm/frame.h"
2548  #include "vm/page.h"
2549 +#include "devices/block.h"
2550  #include "threads/synch.h"
2551  #include "threads/vaddr.h"
2552
2553 -/* The swap device. */
2554 +/* The swap partition. */
2555  static struct block *swap_device;
2556
2557  /* Used swap pages. */