16 files changed, 1271 insertions, 0 deletions

diff --git a/src/filesys/.cvsignore b/src/filesys/.cvsignore
new file mode 100644
index 0000000..6d5357c
--- /dev/null
+++ b/src/filesys/.cvsignore
@@ -0,0 +1,3 @@
+build
+bochsrc.txt
+bochsout.txt
diff --git a/src/filesys/Make.vars b/src/filesys/Make.vars
new file mode 100644
index 0000000..d8050cd
--- /dev/null
+++ b/src/filesys/Make.vars
@@ -0,0 +1,13 @@
+# -*- makefile -*-
+
+os.dsk: 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.
+#os.dsk: DEFINES += -DVM
+#KERNEL_SUBDIRS += vm
+#TEST_SUBDIRS += tests/vm
+#GRADING_FILE = $(SRCDIR)/tests/filesys/Grading.with-vm
diff --git a/src/filesys/Makefile b/src/filesys/Makefile
new file mode 100644
index 0000000..34c10aa
--- /dev/null
+++ b/src/filesys/Makefile
@@ -0,0 +1 @@
+include ../Makefile.kernel
diff --git a/src/filesys/directory.c b/src/filesys/directory.c
new file mode 100644
index 0000000..0d265d5
--- /dev/null
+++ b/src/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 
+  {
+    disk_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 (disk_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, disk_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/src/filesys/directory.h b/src/filesys/directory.h
new file mode 100644
index 0000000..7955937
--- /dev/null
+++ b/src/filesys/directory.h
@@ -0,0 +1,30 @@
+#ifndef FILESYS_DIRECTORY_H
+#define FILESYS_DIRECTORY_H
+
+#include <stdbool.h>
+#include <stddef.h>
+#include "devices/disk.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 (disk_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, disk_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/src/filesys/file.c b/src/filesys/file.c
new file mode 100644
index 0000000..bd19f9c
--- /dev/null
+++ b/src/filesys/file.c
@@ -0,0 +1,140 @@
+#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. */
+  };
+
+/* 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;
+
+      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)
+    {
+      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);
+}
+
+
+/* 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/src/filesys/file.h b/src/filesys/file.h
new file mode 100644
index 0000000..d01d556
--- /dev/null
+++ b/src/filesys/file.h
@@ -0,0 +1,26 @@
+#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);
+
+
+/* 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/src/filesys/filesys.c b/src/filesys/filesys.c
new file mode 100644
index 0000000..97a3f04
--- /dev/null
+++ b/src/filesys/filesys.c
@@ -0,0 +1,114 @@
+#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"
+#include "devices/disk.h"
+#include "threads/synch.h"
+
+/* The disk that contains the file system. */
+struct disk *filesys_disk;
+
+static void do_format (void);
+
+/* Initializes the file system module.
+   If FORMAT is true, reformats the file system. */
+void
+filesys_init (bool format) 
+{
+  filesys_disk = disk_get (0, 1);
+  if (filesys_disk == NULL)
+    PANIC ("hd0:1 (hdb) not present, file system initialization failed");
+
+  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) 
+{
+  disk_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;
+  struct file *file = NULL;
+
+  if (dir != NULL)
+    dir_lookup (dir, name, &inode);
+  dir_close (dir);
+
+  file = file_open (inode);
+  
+  return file;
+}
+
+void
+filesys_close (struct file *file)
+{
+  file_close(file);
+}
+
+/* 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/src/filesys/filesys.h b/src/filesys/filesys.h
new file mode 100644
index 0000000..71efb16
--- /dev/null
+++ b/src/filesys/filesys.h
@@ -0,0 +1,23 @@
+#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. */
+
+/* Disk used for file system. */
+extern struct disk *filesys_disk;
+
+void filesys_init (bool format);
+void filesys_done (void);
+
+bool filesys_create (const char *name, off_t initial_size);
+bool filesys_remove (const char *name);
+
+struct file *filesys_open (const char *name);
+void         filesys_close (struct file *file);
+
+#endif /* filesys/filesys.h */
diff --git a/src/filesys/free-map.c b/src/filesys/free-map.c
new file mode 100644
index 0000000..65d8843
--- /dev/null
+++ b/src/filesys/free-map.c
@@ -0,0 +1,88 @@
+#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 disk sector. */
+
+
+/* Initializes the free map. */
+void
+free_map_init (void) 
+{
+  free_map = bitmap_create (disk_size (filesys_disk));
+  if (free_map == NULL)
+    PANIC ("bitmap creation failed--disk 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 all sectors were
+   available. */
+bool
+free_map_allocate (size_t cnt, disk_sector_t *sectorp) 
+{
+  disk_sector_t sector;
+  
+  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 (disk_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/src/filesys/free-map.h b/src/filesys/free-map.h
new file mode 100644
index 0000000..ce08f5c
--- /dev/null
+++ b/src/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/disk.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, disk_sector_t *);
+void free_map_release (disk_sector_t, size_t);
+
+#endif /* filesys/free-map.h */
diff --git a/src/filesys/fsutil.c b/src/filesys/fsutil.c
new file mode 100644
index 0000000..14a4507
--- /dev/null
+++ b/src/filesys/fsutil.c
@@ -0,0 +1,197 @@
+#include "filesys/fsutil.h"
+#include <debug.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include "filesys/directory.h"
+#include "filesys/file.h"
+#include "filesys/filesys.h"
+#include "devices/disk.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);
+}
+
+/* Copies from the "scratch" disk, hdc or hd1:0 to file ARGV[1]
+   in the file system.
+
+   The current sector on the scratch disk must begin with the
+   string "PUT\0" followed by a 32-bit little-endian integer
+   indicating the file size in bytes.  Subsequent sectors hold
+   the file content.
+
+   The first call to this function will read starting at the
+   beginning of the scratch disk.  Later calls advance across the
+   disk.  This disk position is independent of that used for
+   fsutil_get(), so all `put's should precede all `get's. */
+void
+fsutil_put (char **argv) 
+{
+  static disk_sector_t sector = 0;
+
+  const char *file_name = argv[1];
+  struct disk *src;
+  struct file *dst;
+  off_t size;
+  void *buffer;
+
+  printf ("Putting '%s' into the file system...\n", file_name);
+
+  /* Allocate buffer. */
+  buffer = malloc (DISK_SECTOR_SIZE);
+  if (buffer == NULL)
+    PANIC ("couldn't allocate buffer");
+
+  /* Open source disk and read file size. */
+  src = disk_get (1, 0);
+  if (src == NULL)
+    PANIC ("couldn't open source disk (hdc or hd1:0)");
+
+  /* Read file size. */
+  disk_read (src, sector++, buffer);
+  if (memcmp (buffer, "PUT", 4))
+    PANIC ("%s: missing PUT signature on scratch disk", file_name);
+  size = ((int32_t *) buffer)[1];
+  if (size < 0)
+    PANIC ("%s: invalid file size %d", file_name, size);
+  
+  /* 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 > DISK_SECTOR_SIZE ? DISK_SECTOR_SIZE : size;
+      disk_read (src, sector++, buffer);
+      if (file_write (dst, buffer, chunk_size) != chunk_size)
+        PANIC ("%s: write failed with %"PROTd" bytes unwritten",
+               file_name, size);
+      size -= chunk_size;
+    }
+
+  /* Finish up. */
+  file_close (dst);
+  free (buffer);
+}
+
+/* Copies file FILE_NAME from the file system to the scratch disk.
+
+   The current sector on the scratch disk will receive "GET\0"
+   followed by the file's size in bytes as a 32-bit,
+   little-endian integer.  Subsequent sectors receive the file's
+   data.
+
+   The first call to this function will write starting at the
+   beginning of the scratch disk.  Later calls advance across the
+   disk.  This disk position is independent of that used for
+   fsutil_put(), so all `put's should precede all `get's. */
+void
+fsutil_get (char **argv)
+{
+  static disk_sector_t sector = 0;
+
+  const char *file_name = argv[1];
+  void *buffer;
+  struct file *src;
+  struct disk *dst;
+  off_t size;
+
+  printf ("Getting '%s' from the file system...\n", file_name);
+
+  /* Allocate buffer. */
+  buffer = malloc (DISK_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 disk. */
+  dst = disk_get (1, 0);
+  if (dst == NULL)
+    PANIC ("couldn't open target disk (hdc or hd1:0)");
+  
+  /* Write size to sector 0. */
+  memset (buffer, 0, DISK_SECTOR_SIZE);
+  memcpy (buffer, "GET", 4);
+  ((int32_t *) buffer)[1] = size;
+  disk_write (dst, sector++, buffer);
+  
+  /* Do copy. */
+  while (size > 0) 
+    {
+      int chunk_size = size > DISK_SECTOR_SIZE ? DISK_SECTOR_SIZE : size;
+      if (sector >= disk_size (dst))
+        PANIC ("%s: out of space on scratch disk", 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, DISK_SECTOR_SIZE - chunk_size);
+      disk_write (dst, sector++, buffer);
+      size -= chunk_size;
+    }
+
+  /* Finish up. */
+  file_close (src);
+  free (buffer);
+}
diff --git a/src/filesys/fsutil.h b/src/filesys/fsutil.h
new file mode 100644
index 0000000..abebfe2
--- /dev/null
+++ b/src/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_put (char **argv);
+void fsutil_get (char **argv);
+
+#endif /* filesys/fsutil.h */
diff --git a/src/filesys/inode.c b/src/filesys/inode.c
new file mode 100644
index 0000000..daa185f
--- /dev/null
+++ b/src/filesys/inode.c
@@ -0,0 +1,336 @@
+#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"
+#include "threads/synch.h"
+
+
+/* Identifies an inode. */
+#define INODE_MAGIC 0x494e4f44
+
+/* On-disk inode.
+   Must be exactly DISK_SECTOR_SIZE bytes long. */
+struct inode_disk
+  {
+    disk_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, DISK_SECTOR_SIZE);
+}
+
+/* In-memory inode. */
+struct inode 
+  {
+    struct list_elem elem;              /* Element in inode list. */
+    disk_sector_t sector;               /* Sector number of disk location. */
+    int open_cnt;                       /* Number of openers. */
+    bool removed;                       /* True if deleted, false otherwise. */
+    struct inode_disk data;             /* Inode content. */
+  };
+
+
+/* Returns the disk sector that contains byte offset POS within
+   INODE.
+   Returns -1 if INODE does not contain data for a byte at offset
+   POS. */
+static disk_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 / DISK_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
+   disk.
+   Returns true if successful.
+   Returns false if memory or disk allocation fails. */
+bool
+inode_create (disk_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 == DISK_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))
+        {
+          disk_write (filesys_disk, sector, disk_inode);
+          if (sectors > 0) 
+            {
+              static char zeros[DISK_SECTOR_SIZE];
+              size_t i;
+              
+              for (i = 0; i < sectors; i++) 
+                disk_write (filesys_disk, 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 (disk_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;
+  }
+  
+  list_push_front (&open_inodes, &inode->elem);
+  
+  /* Initialize. */
+  inode->sector = sector;
+  inode->open_cnt = 1;
+  inode->removed = false;
+  
+  disk_read (filesys_disk, 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. */
+disk_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. */
+      list_remove (&inode->elem);
+      
+ 
+      /* Deallocate blocks if the file is marked as removed. */
+      if (inode->removed) 
+        {
+          free_map_release (inode->sector, 1);
+          free_map_release (inode->data.start,
+                            bytes_to_sectors (inode->data.length)); 
+        }
+
+      free (inode);
+      return;
+    }
+}
+
+/* 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. */
+      disk_sector_t sector_idx = byte_to_sector (inode, offset);
+      int sector_ofs = offset % DISK_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 = DISK_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 == DISK_SECTOR_SIZE) 
+        {
+          /* Read full sector directly into caller's buffer. */
+          disk_read (filesys_disk, sector_idx, buffer + bytes_read); 
+        }
+      else 
+        {
+          /* Read sector into bounce buffer, then partially copy
+             into caller's buffer. */
+          if (bounce == NULL) 
+            {
+              bounce = malloc (DISK_SECTOR_SIZE);
+              if (bounce == NULL)
+                break;
+            }
+          disk_read (filesys_disk, 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;
+
+    
+  while (size > 0) 
+    {
+      /* Sector to write, starting byte offset within sector. */
+      disk_sector_t sector_idx = byte_to_sector (inode, offset);
+      int sector_ofs = offset % DISK_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 = DISK_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 == DISK_SECTOR_SIZE) 
+        {
+          /* Write full sector directly to disk. */
+          disk_write (filesys_disk, sector_idx, buffer + bytes_written); 
+        }
+      else 
+        {
+          /* We need a bounce buffer. */
+          if (bounce == NULL) 
+            {
+              bounce = malloc (DISK_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) 
+            disk_read (filesys_disk, sector_idx, bounce);
+          else
+            memset (bounce, 0, DISK_SECTOR_SIZE);
+          memcpy (bounce + sector_ofs, buffer + bytes_written, chunk_size);
+          disk_write (filesys_disk, sector_idx, bounce); 
+        }
+
+      /* Advance. */
+      size -= chunk_size;
+      offset += chunk_size;
+      bytes_written += chunk_size;
+    }
+  free (bounce);
+
+  return bytes_written;
+}
+
+/* Returns the length, in bytes, of INODE's data. */
+off_t
+inode_length (const struct inode *inode)
+{
+  return inode->data.length;
+}
+
diff --git a/src/filesys/inode.h b/src/filesys/inode.h
new file mode 100644
index 0000000..ff3042e
--- /dev/null
+++ b/src/filesys/inode.h
@@ -0,0 +1,22 @@
+#ifndef FILESYS_INODE_H
+#define FILESYS_INODE_H
+
+#include <stdbool.h>
+#include "filesys/off_t.h"
+#include "devices/disk.h"
+
+struct bitmap;
+
+
+void inode_init (void);
+bool inode_create (disk_sector_t, off_t);
+struct inode *inode_open (disk_sector_t);
+struct inode *inode_reopen (struct inode *);
+disk_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);
+off_t inode_length (const struct inode *);
+
+#endif /* filesys/inode.h */
diff --git a/src/filesys/off_t.h b/src/filesys/off_t.h
new file mode 100644
index 0000000..9caff4d
--- /dev/null
+++ b/src/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 */