16 files changed, 1320 insertions, 0 deletions

diff --git a/filesys/.gitignore b/filesys/.gitignore
new file mode 100644
index 0000000..6d5357c
--- /dev/null
+++ b/filesys/.gitignore
@@ -0,0 +1,3 @@
+build
+bochsrc.txt
+bochsout.txt
diff --git a/filesys/Make.vars b/filesys/Make.vars
new file mode 100644
index 0000000..b3aa005
--- /dev/null
+++ b/filesys/Make.vars
@@ -0,0 +1,13 @@
+# -*- makefile -*-
+
+kernel.bin: DEFINES = -DUSERPROG -DFILESYS
+KERNEL_SUBDIRS = threads devices lib lib/kernel userprog filesys
+TEST_SUBDIRS = tests/userprog tests/filesys/base tests/filesys/extended
+GRADING_FILE = $(SRCDIR)/tests/filesys/Grading.no-vm
+SIMULATOR = --qemu
+
+# Uncomment the lines below to enable VM.
+#kernel.bin: DEFINES += -DVM
+#KERNEL_SUBDIRS += vm
+#TEST_SUBDIRS += tests/vm
+#GRADING_FILE = $(SRCDIR)/tests/filesys/Grading.with-vm
diff --git a/filesys/Makefile b/filesys/Makefile
new file mode 100644
index 0000000..34c10aa
--- /dev/null
+++ b/filesys/Makefile
@@ -0,0 +1 @@
+include ../Makefile.kernel
diff --git a/filesys/directory.c b/filesys/directory.c
new file mode 100644
index 0000000..030c1c9
--- /dev/null
+++ b/filesys/directory.c
@@ -0,0 +1,236 @@
+#include "filesys/directory.h"
+#include <stdio.h>
+#include <string.h>
+#include <list.h>
+#include "filesys/filesys.h"
+#include "filesys/inode.h"
+#include "threads/malloc.h"
+
+/* A directory. */
+struct dir 
+  {
+    struct inode *inode;                /* Backing store. */
+    off_t pos;                          /* Current position. */
+  };
+
+/* A single directory entry. */
+struct dir_entry 
+  {
+    block_sector_t inode_sector;        /* Sector number of header. */
+    char name[NAME_MAX + 1];            /* Null terminated file name. */
+    bool in_use;                        /* In use or free? */
+  };
+
+/* Creates a directory with space for ENTRY_CNT entries in the
+   given SECTOR.  Returns true if successful, false on failure. */
+bool
+dir_create (block_sector_t sector, size_t entry_cnt)
+{
+  return inode_create (sector, entry_cnt * sizeof (struct dir_entry));
+}
+
+/* Opens and returns the directory for the given INODE, of which
+   it takes ownership.  Returns a null pointer on failure. */
+struct dir *
+dir_open (struct inode *inode) 
+{
+  struct dir *dir = calloc (1, sizeof *dir);
+  if (inode != NULL && dir != NULL)
+    {
+      dir->inode = inode;
+      dir->pos = 0;
+      return dir;
+    }
+  else
+    {
+      inode_close (inode);
+      free (dir);
+      return NULL; 
+    }
+}
+
+/* Opens the root directory and returns a directory for it.
+   Return true if successful, false on failure. */
+struct dir *
+dir_open_root (void)
+{
+  return dir_open (inode_open (ROOT_DIR_SECTOR));
+}
+
+/* Opens and returns a new directory for the same inode as DIR.
+   Returns a null pointer on failure. */
+struct dir *
+dir_reopen (struct dir *dir) 
+{
+  return dir_open (inode_reopen (dir->inode));
+}
+
+/* Destroys DIR and frees associated resources. */
+void
+dir_close (struct dir *dir) 
+{
+  if (dir != NULL)
+    {
+      inode_close (dir->inode);
+      free (dir);
+    }
+}
+
+/* Returns the inode encapsulated by DIR. */
+struct inode *
+dir_get_inode (struct dir *dir) 
+{
+  return dir->inode;
+}
+
+/* Searches DIR for a file with the given NAME.
+   If successful, returns true, sets *EP to the directory entry
+   if EP is non-null, and sets *OFSP to the byte offset of the
+   directory entry if OFSP is non-null.
+   otherwise, returns false and ignores EP and OFSP. */
+static bool
+lookup (const struct dir *dir, const char *name,
+        struct dir_entry *ep, off_t *ofsp) 
+{
+  struct dir_entry e;
+  size_t ofs;
+  
+  ASSERT (dir != NULL);
+  ASSERT (name != NULL);
+
+  for (ofs = 0; inode_read_at (dir->inode, &e, sizeof e, ofs) == sizeof e;
+       ofs += sizeof e) 
+    if (e.in_use && !strcmp (name, e.name)) 
+      {
+        if (ep != NULL)
+          *ep = e;
+        if (ofsp != NULL)
+          *ofsp = ofs;
+        return true;
+      }
+  return false;
+}
+
+/* Searches DIR for a file with the given NAME
+   and returns true if one exists, false otherwise.
+   On success, sets *INODE to an inode for the file, otherwise to
+   a null pointer.  The caller must close *INODE. */
+bool
+dir_lookup (const struct dir *dir, const char *name,
+            struct inode **inode) 
+{
+  struct dir_entry e;
+
+  ASSERT (dir != NULL);
+  ASSERT (name != NULL);
+
+  if (lookup (dir, name, &e, NULL))
+    *inode = inode_open (e.inode_sector);
+  else
+    *inode = NULL;
+
+  return *inode != NULL;
+}
+
+/* Adds a file named NAME to DIR, which must not already contain a
+   file by that name.  The file's inode is in sector
+   INODE_SECTOR.
+   Returns true if successful, false on failure.
+   Fails if NAME is invalid (i.e. too long) or a disk or memory
+   error occurs. */
+bool
+dir_add (struct dir *dir, const char *name, block_sector_t inode_sector)
+{
+  struct dir_entry e;
+  off_t ofs;
+  bool success = false;
+
+  ASSERT (dir != NULL);
+  ASSERT (name != NULL);
+
+  /* Check NAME for validity. */
+  if (*name == '\0' || strlen (name) > NAME_MAX)
+    return false;
+
+  /* Check that NAME is not in use. */
+  if (lookup (dir, name, NULL, NULL))
+    goto done;
+
+  /* Set OFS to offset of free slot.
+     If there are no free slots, then it will be set to the
+     current end-of-file.
+     
+     inode_read_at() will only return a short read at end of file.
+     Otherwise, we'd need to verify that we didn't get a short
+     read due to something intermittent such as low memory. */
+  for (ofs = 0; inode_read_at (dir->inode, &e, sizeof e, ofs) == sizeof e;
+       ofs += sizeof e) 
+    if (!e.in_use)
+      break;
+
+  /* Write slot. */
+  e.in_use = true;
+  strlcpy (e.name, name, sizeof e.name);
+  e.inode_sector = inode_sector;
+  success = inode_write_at (dir->inode, &e, sizeof e, ofs) == sizeof e;
+
+ done:
+  return success;
+}
+
+/* Removes any entry for NAME in DIR.
+   Returns true if successful, false on failure,
+   which occurs only if there is no file with the given NAME. */
+bool
+dir_remove (struct dir *dir, const char *name) 
+{
+  struct dir_entry e;
+  struct inode *inode = NULL;
+  bool success = false;
+  off_t ofs;
+
+  ASSERT (dir != NULL);
+  ASSERT (name != NULL);
+
+  /* Find directory entry. */
+  if (!lookup (dir, name, &e, &ofs))
+    goto done;
+
+  /* Open inode. */
+  inode = inode_open (e.inode_sector);
+  if (inode == NULL)
+    goto done;
+
+  /* Erase directory entry. */
+  e.in_use = false;
+  if (inode_write_at (dir->inode, &e, sizeof e, ofs) != sizeof e) 
+    goto done;
+
+  /* Remove inode. */
+  inode_remove (inode);
+  success = true;
+
+ done:
+  inode_close (inode);
+  return success;
+}
+
+/* Reads the next directory entry in DIR and stores the name in
+   NAME.  Returns true if successful, false if the directory
+   contains no more entries. */
+bool
+dir_readdir (struct dir *dir, char name[NAME_MAX + 1])
+{
+  struct dir_entry e;
+
+  while (inode_read_at (dir->inode, &e, sizeof e, dir->pos) == sizeof e) 
+    {
+      dir->pos += sizeof e;
+      if (e.in_use)
+        {
+          strlcpy (name, e.name, NAME_MAX + 1);
+          return true;
+        } 
+    }
+  return false;
+}
diff --git a/filesys/directory.h b/filesys/directory.h
new file mode 100644
index 0000000..930acf9
--- /dev/null
+++ b/filesys/directory.h
@@ -0,0 +1,30 @@
+#ifndef FILESYS_DIRECTORY_H
+#define FILESYS_DIRECTORY_H
+
+#include <stdbool.h>
+#include <stddef.h>
+#include "devices/block.h"
+
+/* Maximum length of a file name component.
+   This is the traditional UNIX maximum length.
+   After directories are implemented, this maximum length may be
+   retained, but much longer full path names must be allowed. */
+#define NAME_MAX 14
+
+struct inode;
+
+/* Opening and closing directories. */
+bool dir_create (block_sector_t sector, size_t entry_cnt);
+struct dir *dir_open (struct inode *);
+struct dir *dir_open_root (void);
+struct dir *dir_reopen (struct dir *);
+void dir_close (struct dir *);
+struct inode *dir_get_inode (struct dir *);
+
+/* Reading and writing. */
+bool dir_lookup (const struct dir *, const char *name, struct inode **);
+bool dir_add (struct dir *, const char *name, block_sector_t);
+bool dir_remove (struct dir *, const char *name);
+bool dir_readdir (struct dir *, char name[NAME_MAX + 1]);
+
+#endif /* filesys/directory.h */
diff --git a/filesys/file.c b/filesys/file.c
new file mode 100644
index 0000000..d5fc10d
--- /dev/null
+++ b/filesys/file.c
@@ -0,0 +1,168 @@
+#include "filesys/file.h"
+#include <debug.h>
+#include "filesys/inode.h"
+#include "threads/malloc.h"
+
+/* An open file. */
+struct file 
+  {
+    struct inode *inode;        /* File's inode. */
+    off_t pos;                  /* Current position. */
+    bool deny_write;            /* Has file_deny_write() been called? */
+  };
+
+/* Opens a file for the given INODE, of which it takes ownership,
+   and returns the new file.  Returns a null pointer if an
+   allocation fails or if INODE is null. */
+struct file *
+file_open (struct inode *inode) 
+{
+  struct file *file = calloc (1, sizeof *file);
+  if (inode != NULL && file != NULL)
+    {
+      file->inode = inode;
+      file->pos = 0;
+      file->deny_write = false;
+      return file;
+    }
+  else
+    {
+      inode_close (inode);
+      free (file);
+      return NULL; 
+    }
+}
+
+/* Opens and returns a new file for the same inode as FILE.
+   Returns a null pointer if unsuccessful. */
+struct file *
+file_reopen (struct file *file) 
+{
+  return file_open (inode_reopen (file->inode));
+}
+
+/* Closes FILE. */
+void
+file_close (struct file *file) 
+{
+  if (file != NULL)
+    {
+      file_allow_write (file);
+      inode_close (file->inode);
+      free (file); 
+    }
+}
+
+/* Returns the inode encapsulated by FILE. */
+struct inode *
+file_get_inode (struct file *file) 
+{
+  return file->inode;
+}
+
+/* Reads SIZE bytes from FILE into BUFFER,
+   starting at the file's current position.
+   Returns the number of bytes actually read,
+   which may be less than SIZE if end of file is reached.
+   Advances FILE's position by the number of bytes read. */
+off_t
+file_read (struct file *file, void *buffer, off_t size) 
+{
+  off_t bytes_read = inode_read_at (file->inode, buffer, size, file->pos);
+  file->pos += bytes_read;
+  return bytes_read;
+}
+
+/* Reads SIZE bytes from FILE into BUFFER,
+   starting at offset FILE_OFS in the file.
+   Returns the number of bytes actually read,
+   which may be less than SIZE if end of file is reached.
+   The file's current position is unaffected. */
+off_t
+file_read_at (struct file *file, void *buffer, off_t size, off_t file_ofs) 
+{
+  return inode_read_at (file->inode, buffer, size, file_ofs);
+}
+
+/* Writes SIZE bytes from BUFFER into FILE,
+   starting at the file's current position.
+   Returns the number of bytes actually written,
+   which may be less than SIZE if end of file is reached.
+   (Normally we'd grow the file in that case, but file growth is
+   not yet implemented.)
+   Advances FILE's position by the number of bytes read. */
+off_t
+file_write (struct file *file, const void *buffer, off_t size) 
+{
+  off_t bytes_written = inode_write_at (file->inode, buffer, size, file->pos);
+  file->pos += bytes_written;
+  return bytes_written;
+}
+
+/* Writes SIZE bytes from BUFFER into FILE,
+   starting at offset FILE_OFS in the file.
+   Returns the number of bytes actually written,
+   which may be less than SIZE if end of file is reached.
+   (Normally we'd grow the file in that case, but file growth is
+   not yet implemented.)
+   The file's current position is unaffected. */
+off_t
+file_write_at (struct file *file, const void *buffer, off_t size,
+               off_t file_ofs) 
+{
+  return inode_write_at (file->inode, buffer, size, file_ofs);
+}
+
+/* Prevents write operations on FILE's underlying inode
+   until file_allow_write() is called or FILE is closed. */
+void
+file_deny_write (struct file *file) 
+{
+  ASSERT (file != NULL);
+  if (!file->deny_write) 
+    {
+      file->deny_write = true;
+      inode_deny_write (file->inode);
+    }
+}
+
+/* Re-enables write operations on FILE's underlying inode.
+   (Writes might still be denied by some other file that has the
+   same inode open.) */
+void
+file_allow_write (struct file *file) 
+{
+  ASSERT (file != NULL);
+  if (file->deny_write) 
+    {
+      file->deny_write = false;
+      inode_allow_write (file->inode);
+    }
+}
+
+/* Returns the size of FILE in bytes. */
+off_t
+file_length (struct file *file) 
+{
+  ASSERT (file != NULL);
+  return inode_length (file->inode);
+}
+
+/* Sets the current position in FILE to NEW_POS bytes from the
+   start of the file. */
+void
+file_seek (struct file *file, off_t new_pos)
+{
+  ASSERT (file != NULL);
+  ASSERT (new_pos >= 0);
+  file->pos = new_pos;
+}
+
+/* Returns the current position in FILE as a byte offset from the
+   start of the file. */
+off_t
+file_tell (struct file *file) 
+{
+  ASSERT (file != NULL);
+  return file->pos;
+}
diff --git a/filesys/file.h b/filesys/file.h
new file mode 100644
index 0000000..a33c5af
--- /dev/null
+++ b/filesys/file.h
@@ -0,0 +1,29 @@
+#ifndef FILESYS_FILE_H
+#define FILESYS_FILE_H
+
+#include "filesys/off_t.h"
+
+struct inode;
+
+/* Opening and closing files. */
+struct file *file_open (struct inode *);
+struct file *file_reopen (struct file *);
+void file_close (struct file *);
+struct inode *file_get_inode (struct file *);
+
+/* Reading and writing. */
+off_t file_read (struct file *, void *, off_t);
+off_t file_read_at (struct file *, void *, off_t size, off_t start);
+off_t file_write (struct file *, const void *, off_t);
+off_t file_write_at (struct file *, const void *, off_t size, off_t start);
+
+/* Preventing writes. */
+void file_deny_write (struct file *);
+void file_allow_write (struct file *);
+
+/* File position. */
+void file_seek (struct file *, off_t);
+off_t file_tell (struct file *);
+off_t file_length (struct file *);
+
+#endif /* filesys/file.h */
diff --git a/filesys/filesys.c b/filesys/filesys.c
new file mode 100644
index 0000000..7a53f5f
--- /dev/null
+++ b/filesys/filesys.c
@@ -0,0 +1,103 @@
+#include "filesys/filesys.h"
+#include <debug.h>
+#include <stdio.h>
+#include <string.h>
+#include "filesys/file.h"
+#include "filesys/free-map.h"
+#include "filesys/inode.h"
+#include "filesys/directory.h"
+
+/* Partition that contains the file system. */
+struct block *fs_device;
+
+static void do_format (void);
+
+/* Initializes the file system module.
+   If FORMAT is true, reformats the file system. */
+void
+filesys_init (bool format) 
+{
+  fs_device = block_get_role (BLOCK_FILESYS);
+  if (fs_device == NULL)
+    PANIC ("No file system device found, can't initialize file system.");
+
+  inode_init ();
+  free_map_init ();
+
+  if (format) 
+    do_format ();
+
+  free_map_open ();
+}
+
+/* Shuts down the file system module, writing any unwritten data
+   to disk. */
+void
+filesys_done (void) 
+{
+  free_map_close ();
+}
+
+/* Creates a file named NAME with the given INITIAL_SIZE.
+   Returns true if successful, false otherwise.
+   Fails if a file named NAME already exists,
+   or if internal memory allocation fails. */
+bool
+filesys_create (const char *name, off_t initial_size) 
+{
+  block_sector_t inode_sector = 0;
+  struct dir *dir = dir_open_root ();
+  bool success = (dir != NULL
+                  && free_map_allocate (1, &inode_sector)
+                  && inode_create (inode_sector, initial_size)
+                  && dir_add (dir, name, inode_sector));
+  if (!success && inode_sector != 0) 
+    free_map_release (inode_sector, 1);
+  dir_close (dir);
+
+  return success;
+}
+
+/* Opens the file with the given NAME.
+   Returns the new file if successful or a null pointer
+   otherwise.
+   Fails if no file named NAME exists,
+   or if an internal memory allocation fails. */
+struct file *
+filesys_open (const char *name)
+{
+  struct dir *dir = dir_open_root ();
+  struct inode *inode = NULL;
+
+  if (dir != NULL)
+    dir_lookup (dir, name, &inode);
+  dir_close (dir);
+
+  return file_open (inode);
+}
+
+/* Deletes the file named NAME.
+   Returns true if successful, false on failure.
+   Fails if no file named NAME exists,
+   or if an internal memory allocation fails. */
+bool
+filesys_remove (const char *name) 
+{
+  struct dir *dir = dir_open_root ();
+  bool success = dir != NULL && dir_remove (dir, name);
+  dir_close (dir); 
+
+  return success;
+}
+
+/* Formats the file system. */
+static void
+do_format (void)
+{
+  printf ("Formatting file system...");
+  free_map_create ();
+  if (!dir_create (ROOT_DIR_SECTOR, 16))
+    PANIC ("root directory creation failed");
+  free_map_close ();
+  printf ("done.\n");
+}
diff --git a/filesys/filesys.h b/filesys/filesys.h
new file mode 100644
index 0000000..c1cda84
--- /dev/null
+++ b/filesys/filesys.h
@@ -0,0 +1,20 @@
+#ifndef FILESYS_FILESYS_H
+#define FILESYS_FILESYS_H
+
+#include <stdbool.h>
+#include "filesys/off_t.h"
+
+/* Sectors of system file inodes. */
+#define FREE_MAP_SECTOR 0       /* Free map file inode sector. */
+#define ROOT_DIR_SECTOR 1       /* Root directory file inode sector. */
+
+/* Block device that contains the file system. */
+struct block *fs_device;
+
+void filesys_init (bool format);
+void filesys_done (void);
+bool filesys_create (const char *name, off_t initial_size);
+struct file *filesys_open (const char *name);
+bool filesys_remove (const char *name);
+
+#endif /* filesys/filesys.h */
diff --git a/filesys/free-map.c b/filesys/free-map.c
new file mode 100644
index 0000000..29ea4df
--- /dev/null
+++ b/filesys/free-map.c
@@ -0,0 +1,85 @@
+#include "filesys/free-map.h"
+#include <bitmap.h>
+#include <debug.h>
+#include "filesys/file.h"
+#include "filesys/filesys.h"
+#include "filesys/inode.h"
+
+static struct file *free_map_file;   /* Free map file. */
+static struct bitmap *free_map;      /* Free map, one bit per sector. */
+
+/* Initializes the free map. */
+void
+free_map_init (void) 
+{
+  free_map = bitmap_create (block_size (fs_device));
+  if (free_map == NULL)
+    PANIC ("bitmap creation failed--file system device is too large");
+  bitmap_mark (free_map, FREE_MAP_SECTOR);
+  bitmap_mark (free_map, ROOT_DIR_SECTOR);
+}
+
+/* Allocates CNT consecutive sectors from the free map and stores
+   the first into *SECTORP.
+   Returns true if successful, false if not enough consecutive
+   sectors were available or if the free_map file could not be
+   written. */
+bool
+free_map_allocate (size_t cnt, block_sector_t *sectorp)
+{
+  block_sector_t sector = bitmap_scan_and_flip (free_map, 0, cnt, false);
+  if (sector != BITMAP_ERROR
+      && free_map_file != NULL
+      && !bitmap_write (free_map, free_map_file))
+    {
+      bitmap_set_multiple (free_map, sector, cnt, false); 
+      sector = BITMAP_ERROR;
+    }
+  if (sector != BITMAP_ERROR)
+    *sectorp = sector;
+  return sector != BITMAP_ERROR;
+}
+
+/* Makes CNT sectors starting at SECTOR available for use. */
+void
+free_map_release (block_sector_t sector, size_t cnt)
+{
+  ASSERT (bitmap_all (free_map, sector, cnt));
+  bitmap_set_multiple (free_map, sector, cnt, false);
+  bitmap_write (free_map, free_map_file);
+}
+
+/* Opens the free map file and reads it from disk. */
+void
+free_map_open (void) 
+{
+  free_map_file = file_open (inode_open (FREE_MAP_SECTOR));
+  if (free_map_file == NULL)
+    PANIC ("can't open free map");
+  if (!bitmap_read (free_map, free_map_file))
+    PANIC ("can't read free map");
+}
+
+/* Writes the free map to disk and closes the free map file. */
+void
+free_map_close (void) 
+{
+  file_close (free_map_file);
+}
+
+/* Creates a new free map file on disk and writes the free map to
+   it. */
+void
+free_map_create (void) 
+{
+  /* Create inode. */
+  if (!inode_create (FREE_MAP_SECTOR, bitmap_file_size (free_map)))
+    PANIC ("free map creation failed");
+
+  /* Write bitmap to file. */
+  free_map_file = file_open (inode_open (FREE_MAP_SECTOR));
+  if (free_map_file == NULL)
+    PANIC ("can't open free map");
+  if (!bitmap_write (free_map, free_map_file))
+    PANIC ("can't write free map");
+}
diff --git a/filesys/free-map.h b/filesys/free-map.h
new file mode 100644
index 0000000..316cd1c
--- /dev/null
+++ b/filesys/free-map.h
@@ -0,0 +1,17 @@
+#ifndef FILESYS_FREE_MAP_H
+#define FILESYS_FREE_MAP_H
+
+#include <stdbool.h>
+#include <stddef.h>
+#include "devices/block.h"
+
+void free_map_init (void);
+void free_map_read (void);
+void free_map_create (void);
+void free_map_open (void);
+void free_map_close (void);
+
+bool free_map_allocate (size_t, block_sector_t *);
+void free_map_release (block_sector_t, size_t);
+
+#endif /* filesys/free-map.h */
diff --git a/filesys/fsutil.c b/filesys/fsutil.c
new file mode 100644
index 0000000..447f291
--- /dev/null
+++ b/filesys/fsutil.c
@@ -0,0 +1,222 @@
+#include "filesys/fsutil.h"
+#include <debug.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <ustar.h>
+#include "filesys/directory.h"
+#include "filesys/file.h"
+#include "filesys/filesys.h"
+#include "threads/malloc.h"
+#include "threads/palloc.h"
+#include "threads/vaddr.h"
+
+/* List files in the root directory. */
+void
+fsutil_ls (char **argv UNUSED) 
+{
+  struct dir *dir;
+  char name[NAME_MAX + 1];
+  
+  printf ("Files in the root directory:\n");
+  dir = dir_open_root ();
+  if (dir == NULL)
+    PANIC ("root dir open failed");
+  while (dir_readdir (dir, name))
+    printf ("%s\n", name);
+  printf ("End of listing.\n");
+}
+
+/* Prints the contents of file ARGV[1] to the system console as
+   hex and ASCII. */
+void
+fsutil_cat (char **argv)
+{
+  const char *file_name = argv[1];
+  
+  struct file *file;
+  char *buffer;
+
+  printf ("Printing '%s' to the console...\n", file_name);
+  file = filesys_open (file_name);
+  if (file == NULL)
+    PANIC ("%s: open failed", file_name);
+  buffer = palloc_get_page (PAL_ASSERT);
+  for (;;) 
+    {
+      off_t pos = file_tell (file);
+      off_t n = file_read (file, buffer, PGSIZE);
+      if (n == 0)
+        break;
+
+      hex_dump (pos, buffer, n, true); 
+    }
+  palloc_free_page (buffer);
+  file_close (file);
+}
+
+/* Deletes file ARGV[1]. */
+void
+fsutil_rm (char **argv) 
+{
+  const char *file_name = argv[1];
+  
+  printf ("Deleting '%s'...\n", file_name);
+  if (!filesys_remove (file_name))
+    PANIC ("%s: delete failed\n", file_name);
+}
+
+/* Extracts a ustar-format tar archive from the scratch block
+   device into the Pintos file system. */
+void
+fsutil_extract (char **argv UNUSED) 
+{
+  static block_sector_t sector = 0;
+
+  struct block *src;
+  void *header, *data;
+
+  /* Allocate buffers. */
+  header = malloc (BLOCK_SECTOR_SIZE);
+  data = malloc (BLOCK_SECTOR_SIZE);
+  if (header == NULL || data == NULL)
+    PANIC ("couldn't allocate buffers");
+
+  /* Open source block device. */
+  src = block_get_role (BLOCK_SCRATCH);
+  if (src == NULL)
+    PANIC ("couldn't open scratch device");
+
+  printf ("Extracting ustar archive from scratch device "
+          "into file system...\n");
+
+  for (;;)
+    {
+      const char *file_name;
+      const char *error;
+      enum ustar_type type;
+      int size;
+
+      /* Read and parse ustar header. */
+      block_read (src, sector++, header);
+      error = ustar_parse_header (header, &file_name, &type, &size);
+      if (error != NULL)
+        PANIC ("bad ustar header in sector %"PRDSNu" (%s)", sector - 1, error);
+
+      if (type == USTAR_EOF)
+        {
+          /* End of archive. */
+          break;
+        }
+      else if (type == USTAR_DIRECTORY)
+        printf ("ignoring directory %s\n", file_name);
+      else if (type == USTAR_REGULAR)
+        {
+          struct file *dst;
+
+          printf ("Putting '%s' into the file system...\n", file_name);
+
+          /* Create destination file. */
+          if (!filesys_create (file_name, size))
+            PANIC ("%s: create failed", file_name);
+          dst = filesys_open (file_name);
+          if (dst == NULL)
+            PANIC ("%s: open failed", file_name);
+
+          /* Do copy. */
+          while (size > 0)
+            {
+              int chunk_size = (size > BLOCK_SECTOR_SIZE
+                                ? BLOCK_SECTOR_SIZE
+                                : size);
+              block_read (src, sector++, data);
+              if (file_write (dst, data, chunk_size) != chunk_size)
+                PANIC ("%s: write failed with %d bytes unwritten",
+                       file_name, size);
+              size -= chunk_size;
+            }
+
+          /* Finish up. */
+          file_close (dst);
+        }
+    }
+
+  /* Erase the ustar header from the start of the block device,
+     so that the extraction operation is idempotent.  We erase
+     two blocks because two blocks of zeros are the ustar
+     end-of-archive marker. */
+  printf ("Erasing ustar archive...\n");
+  memset (header, 0, BLOCK_SECTOR_SIZE);
+  block_write (src, 0, header);
+  block_write (src, 1, header);
+
+  free (data);
+  free (header);
+}
+
+/* Copies file FILE_NAME from the file system to the scratch
+   device, in ustar format.
+
+   The first call to this function will write starting at the
+   beginning of the scratch device.  Later calls advance across
+   the device.  This position is independent of that used for
+   fsutil_extract(), so `extract' should precede all
+   `append's. */
+void
+fsutil_append (char **argv)
+{
+  static block_sector_t sector = 0;
+
+  const char *file_name = argv[1];
+  void *buffer;
+  struct file *src;
+  struct block *dst;
+  off_t size;
+
+  printf ("Appending '%s' to ustar archive on scratch device...\n", file_name);
+
+  /* Allocate buffer. */
+  buffer = malloc (BLOCK_SECTOR_SIZE);
+  if (buffer == NULL)
+    PANIC ("couldn't allocate buffer");
+
+  /* Open source file. */
+  src = filesys_open (file_name);
+  if (src == NULL)
+    PANIC ("%s: open failed", file_name);
+  size = file_length (src);
+
+  /* Open target block device. */
+  dst = block_get_role (BLOCK_SCRATCH);
+  if (dst == NULL)
+    PANIC ("couldn't open scratch device");
+  
+  /* Write ustar header to first sector. */
+  if (!ustar_make_header (file_name, USTAR_REGULAR, size, buffer))
+    PANIC ("%s: name too long for ustar format", file_name);
+  block_write (dst, sector++, buffer);
+
+  /* Do copy. */
+  while (size > 0) 
+    {
+      int chunk_size = size > BLOCK_SECTOR_SIZE ? BLOCK_SECTOR_SIZE : size;
+      if (sector >= block_size (dst))
+        PANIC ("%s: out of space on scratch device", file_name);
+      if (file_read (src, buffer, chunk_size) != chunk_size)
+        PANIC ("%s: read failed with %"PROTd" bytes unread", file_name, size);
+      memset (buffer + chunk_size, 0, BLOCK_SECTOR_SIZE - chunk_size);
+      block_write (dst, sector++, buffer);
+      size -= chunk_size;
+    }
+
+  /* Write ustar end-of-archive marker, which is two consecutive
+     sectors full of zeros.  Don't advance our position past
+     them, though, in case we have more files to append. */
+  memset (buffer, 0, BLOCK_SECTOR_SIZE);
+  block_write (dst, sector, buffer);
+  block_write (dst, sector, buffer + 1);
+
+  /* Finish up. */
+  file_close (src);
+  free (buffer);
+}
diff --git a/filesys/fsutil.h b/filesys/fsutil.h
new file mode 100644
index 0000000..cc73705
--- /dev/null
+++ b/filesys/fsutil.h
@@ -0,0 +1,10 @@
+#ifndef FILESYS_FSUTIL_H
+#define FILESYS_FSUTIL_H
+
+void fsutil_ls (char **argv);
+void fsutil_cat (char **argv);
+void fsutil_rm (char **argv);
+void fsutil_extract (char **argv);
+void fsutil_append (char **argv);
+
+#endif /* filesys/fsutil.h */
diff --git a/filesys/inode.c b/filesys/inode.c
new file mode 100644
index 0000000..3463563
--- /dev/null
+++ b/filesys/inode.c
@@ -0,0 +1,345 @@
+#include "filesys/inode.h"
+#include <list.h>
+#include <debug.h>
+#include <round.h>
+#include <string.h>
+#include "filesys/filesys.h"
+#include "filesys/free-map.h"
+#include "threads/malloc.h"
+
+/* Identifies an inode. */
+#define INODE_MAGIC 0x494e4f44
+
+/* On-disk inode.
+   Must be exactly BLOCK_SECTOR_SIZE bytes long. */
+struct inode_disk
+  {
+    block_sector_t start;               /* First data sector. */
+    off_t length;                       /* File size in bytes. */
+    unsigned magic;                     /* Magic number. */
+    uint32_t unused[125];               /* Not used. */
+  };
+
+/* Returns the number of sectors to allocate for an inode SIZE
+   bytes long. */
+static inline size_t
+bytes_to_sectors (off_t size)
+{
+  return DIV_ROUND_UP (size, BLOCK_SECTOR_SIZE);
+}
+
+/* In-memory inode. */
+struct inode 
+  {
+    struct list_elem elem;              /* Element in inode list. */
+    block_sector_t sector;              /* Sector number of disk location. */
+    int open_cnt;                       /* Number of openers. */
+    bool removed;                       /* True if deleted, false otherwise. */
+    int deny_write_cnt;                 /* 0: writes ok, >0: deny writes. */
+    struct inode_disk data;             /* Inode content. */
+  };
+
+/* Returns the block device sector that contains byte offset POS
+   within INODE.
+   Returns -1 if INODE does not contain data for a byte at offset
+   POS. */
+static block_sector_t
+byte_to_sector (const struct inode *inode, off_t pos) 
+{
+  ASSERT (inode != NULL);
+  if (pos < inode->data.length)
+    return inode->data.start + pos / BLOCK_SECTOR_SIZE;
+  else
+    return -1;
+}
+
+/* List of open inodes, so that opening a single inode twice
+   returns the same `struct inode'. */
+static struct list open_inodes;
+
+/* Initializes the inode module. */
+void
+inode_init (void) 
+{
+  list_init (&open_inodes);
+}
+
+/* Initializes an inode with LENGTH bytes of data and
+   writes the new inode to sector SECTOR on the file system
+   device.
+   Returns true if successful.
+   Returns false if memory or disk allocation fails. */
+bool
+inode_create (block_sector_t sector, off_t length)
+{
+  struct inode_disk *disk_inode = NULL;
+  bool success = false;
+
+  ASSERT (length >= 0);
+
+  /* If this assertion fails, the inode structure is not exactly
+     one sector in size, and you should fix that. */
+  ASSERT (sizeof *disk_inode == BLOCK_SECTOR_SIZE);
+
+  disk_inode = calloc (1, sizeof *disk_inode);
+  if (disk_inode != NULL)
+    {
+      size_t sectors = bytes_to_sectors (length);
+      disk_inode->length = length;
+      disk_inode->magic = INODE_MAGIC;
+      if (free_map_allocate (sectors, &disk_inode->start)) 
+        {
+          block_write (fs_device, sector, disk_inode);
+          if (sectors > 0) 
+            {
+              static char zeros[BLOCK_SECTOR_SIZE];
+              size_t i;
+              
+              for (i = 0; i < sectors; i++) 
+                block_write (fs_device, disk_inode->start + i, zeros);
+            }
+          success = true; 
+        } 
+      free (disk_inode);
+    }
+  return success;
+}
+
+/* Reads an inode from SECTOR
+   and returns a `struct inode' that contains it.
+   Returns a null pointer if memory allocation fails. */
+struct inode *
+inode_open (block_sector_t sector)
+{
+  struct list_elem *e;
+  struct inode *inode;
+
+  /* Check whether this inode is already open. */
+  for (e = list_begin (&open_inodes); e != list_end (&open_inodes);
+       e = list_next (e)) 
+    {
+      inode = list_entry (e, struct inode, elem);
+      if (inode->sector == sector) 
+        {
+          inode_reopen (inode);
+          return inode; 
+        }
+    }
+
+  /* Allocate memory. */
+  inode = malloc (sizeof *inode);
+  if (inode == NULL)
+    return NULL;
+
+  /* Initialize. */
+  list_push_front (&open_inodes, &inode->elem);
+  inode->sector = sector;
+  inode->open_cnt = 1;
+  inode->deny_write_cnt = 0;
+  inode->removed = false;
+  block_read (fs_device, inode->sector, &inode->data);
+  return inode;
+}
+
+/* Reopens and returns INODE. */
+struct inode *
+inode_reopen (struct inode *inode)
+{
+  if (inode != NULL)
+    inode->open_cnt++;
+  return inode;
+}
+
+/* Returns INODE's inode number. */
+block_sector_t
+inode_get_inumber (const struct inode *inode)
+{
+  return inode->sector;
+}
+
+/* Closes INODE and writes it to disk.
+   If this was the last reference to INODE, frees its memory.
+   If INODE was also a removed inode, frees its blocks. */
+void
+inode_close (struct inode *inode) 
+{
+  /* Ignore null pointer. */
+  if (inode == NULL)
+    return;
+
+  /* Release resources if this was the last opener. */
+  if (--inode->open_cnt == 0)
+    {
+      /* Remove from inode list and release lock. */
+      list_remove (&inode->elem);
+ 
+      /* Deallocate blocks if removed. */
+      if (inode->removed) 
+        {
+          free_map_release (inode->sector, 1);
+          free_map_release (inode->data.start,
+                            bytes_to_sectors (inode->data.length)); 
+        }
+
+      free (inode); 
+    }
+}
+
+/* Marks INODE to be deleted when it is closed by the last caller who
+   has it open. */
+void
+inode_remove (struct inode *inode) 
+{
+  ASSERT (inode != NULL);
+  inode->removed = true;
+}
+
+/* Reads SIZE bytes from INODE into BUFFER, starting at position OFFSET.
+   Returns the number of bytes actually read, which may be less
+   than SIZE if an error occurs or end of file is reached. */
+off_t
+inode_read_at (struct inode *inode, void *buffer_, off_t size, off_t offset) 
+{
+  uint8_t *buffer = buffer_;
+  off_t bytes_read = 0;
+  uint8_t *bounce = NULL;
+
+  while (size > 0) 
+    {
+      /* Disk sector to read, starting byte offset within sector. */
+      block_sector_t sector_idx = byte_to_sector (inode, offset);
+      int sector_ofs = offset % BLOCK_SECTOR_SIZE;
+
+      /* Bytes left in inode, bytes left in sector, lesser of the two. */
+      off_t inode_left = inode_length (inode) - offset;
+      int sector_left = BLOCK_SECTOR_SIZE - sector_ofs;
+      int min_left = inode_left < sector_left ? inode_left : sector_left;
+
+      /* Number of bytes to actually copy out of this sector. */
+      int chunk_size = size < min_left ? size : min_left;
+      if (chunk_size <= 0)
+        break;
+
+      if (sector_ofs == 0 && chunk_size == BLOCK_SECTOR_SIZE)
+        {
+          /* Read full sector directly into caller's buffer. */
+          block_read (fs_device, sector_idx, buffer + bytes_read);
+        }
+      else 
+        {
+          /* Read sector into bounce buffer, then partially copy
+             into caller's buffer. */
+          if (bounce == NULL) 
+            {
+              bounce = malloc (BLOCK_SECTOR_SIZE);
+              if (bounce == NULL)
+                break;
+            }
+          block_read (fs_device, sector_idx, bounce);
+          memcpy (buffer + bytes_read, bounce + sector_ofs, chunk_size);
+        }
+      
+      /* Advance. */
+      size -= chunk_size;
+      offset += chunk_size;
+      bytes_read += chunk_size;
+    }
+  free (bounce);
+
+  return bytes_read;
+}
+
+/* Writes SIZE bytes from BUFFER into INODE, starting at OFFSET.
+   Returns the number of bytes actually written, which may be
+   less than SIZE if end of file is reached or an error occurs.
+   (Normally a write at end of file would extend the inode, but
+   growth is not yet implemented.) */
+off_t
+inode_write_at (struct inode *inode, const void *buffer_, off_t size,
+                off_t offset) 
+{
+  const uint8_t *buffer = buffer_;
+  off_t bytes_written = 0;
+  uint8_t *bounce = NULL;
+
+  if (inode->deny_write_cnt)
+    return 0;
+
+  while (size > 0) 
+    {
+      /* Sector to write, starting byte offset within sector. */
+      block_sector_t sector_idx = byte_to_sector (inode, offset);
+      int sector_ofs = offset % BLOCK_SECTOR_SIZE;
+
+      /* Bytes left in inode, bytes left in sector, lesser of the two. */
+      off_t inode_left = inode_length (inode) - offset;
+      int sector_left = BLOCK_SECTOR_SIZE - sector_ofs;
+      int min_left = inode_left < sector_left ? inode_left : sector_left;
+
+      /* Number of bytes to actually write into this sector. */
+      int chunk_size = size < min_left ? size : min_left;
+      if (chunk_size <= 0)
+        break;
+
+      if (sector_ofs == 0 && chunk_size == BLOCK_SECTOR_SIZE)
+        {
+          /* Write full sector directly to disk. */
+          block_write (fs_device, sector_idx, buffer + bytes_written);
+        }
+      else 
+        {
+          /* We need a bounce buffer. */
+          if (bounce == NULL) 
+            {
+              bounce = malloc (BLOCK_SECTOR_SIZE);
+              if (bounce == NULL)
+                break;
+            }
+
+          /* If the sector contains data before or after the chunk
+             we're writing, then we need to read in the sector
+             first.  Otherwise we start with a sector of all zeros. */
+          if (sector_ofs > 0 || chunk_size < sector_left) 
+            block_read (fs_device, sector_idx, bounce);
+          else
+            memset (bounce, 0, BLOCK_SECTOR_SIZE);
+          memcpy (bounce + sector_ofs, buffer + bytes_written, chunk_size);
+          block_write (fs_device, sector_idx, bounce);
+        }
+
+      /* Advance. */
+      size -= chunk_size;
+      offset += chunk_size;
+      bytes_written += chunk_size;
+    }
+  free (bounce);
+
+  return bytes_written;
+}
+
+/* Disables writes to INODE.
+   May be called at most once per inode opener. */
+void
+inode_deny_write (struct inode *inode) 
+{
+  inode->deny_write_cnt++;
+  ASSERT (inode->deny_write_cnt <= inode->open_cnt);
+}
+
+/* Re-enables writes to INODE.
+   Must be called once by each inode opener who has called
+   inode_deny_write() on the inode, before closing the inode. */
+void
+inode_allow_write (struct inode *inode) 
+{
+  ASSERT (inode->deny_write_cnt > 0);
+  ASSERT (inode->deny_write_cnt <= inode->open_cnt);
+  inode->deny_write_cnt--;
+}
+
+/* Returns the length, in bytes, of INODE's data. */
+off_t
+inode_length (const struct inode *inode)
+{
+  return inode->data.length;
+}
diff --git a/filesys/inode.h b/filesys/inode.h
new file mode 100644
index 0000000..cb42310
--- /dev/null
+++ b/filesys/inode.h
@@ -0,0 +1,23 @@
+#ifndef FILESYS_INODE_H
+#define FILESYS_INODE_H
+
+#include <stdbool.h>
+#include "filesys/off_t.h"
+#include "devices/block.h"
+
+struct bitmap;
+
+void inode_init (void);
+bool inode_create (block_sector_t, off_t);
+struct inode *inode_open (block_sector_t);
+struct inode *inode_reopen (struct inode *);
+block_sector_t inode_get_inumber (const struct inode *);
+void inode_close (struct inode *);
+void inode_remove (struct inode *);
+off_t inode_read_at (struct inode *, void *, off_t size, off_t offset);
+off_t inode_write_at (struct inode *, const void *, off_t size, off_t offset);
+void inode_deny_write (struct inode *);
+void inode_allow_write (struct inode *);
+off_t inode_length (const struct inode *);
+
+#endif /* filesys/inode.h */
diff --git a/filesys/off_t.h b/filesys/off_t.h
new file mode 100644
index 0000000..9caff4d
--- /dev/null
+++ b/filesys/off_t.h
@@ -0,0 +1,15 @@
+#ifndef FILESYS_OFF_T_H
+#define FILESYS_OFF_T_H
+
+#include <stdint.h>
+
+/* An offset within a file.
+   This is a separate header because multiple headers want this
+   definition but not any others. */
+typedef int32_t off_t;
+
+/* Format specifier for printf(), e.g.:
+   printf ("offset=%"PROTd"\n", offset); */
+#define PROTd PRId32
+
+#endif /* filesys/off_t.h */