File system project updates:
authorBen Pfaff <blp@cs.stanford.edu>
Mon, 22 May 2006 18:47:19 +0000 (18:47 +0000)
committerBen Pfaff <blp@cs.stanford.edu>
Mon, 22 May 2006 18:47:19 +0000 (18:47 +0000)
Require support for . and ...
Add inumber system call, so getcwd can be implemented,
and inode_get_inumber() function.
Implement these features in the reference solution.
Add "pwd" example program and require explanation of it in design
document.
Implement "cd" in shell.
Add -l option to "ls" example program.
Describe interpretation of unusual file names.
Remove filesys_self_test().
Update TODO.

14 files changed:
doc/filesys.texi
doc/filesys.tmpl
src/examples/.cvsignore
src/examples/Makefile
src/examples/ls.c
src/examples/pwd.c [new file with mode: 0644]
src/filesys/filesys.c
src/filesys/filesys.h
src/filesys/inode.c
src/filesys/inode.h
src/lib/syscall-nr.h
src/lib/user/syscall.c
src/lib/user/syscall.h
tests/.cvsignore

index 8e4dc4f964b4f352f7ffc30c6b672f2bda8573c5..49117a502ae1fad37b20f1ba9ff1a77b3cb79c44 100644 (file)
@@ -176,18 +176,17 @@ not an external program.)
 Update the existing system calls so that, anywhere a file name is
 provided by the caller, an absolute or relative path name may used.
 The directory separator character is forward slash (@samp{/}).
 Update the existing system calls so that, anywhere a file name is
 provided by the caller, an absolute or relative path name may used.
 The directory separator character is forward slash (@samp{/}).
-You may support @file{.} and @file{..} for a small amount of extra
-credit.
+You must also support special file names @file{.} and @file{..}, which
+have the same meanings as they do in Unix.
 
 Update the @code{remove} system call so that it can delete empty
 
 Update the @code{remove} system call so that it can delete empty
-directories in addition to regular files.  Directories can only be
-deleted if they do not contain any files or subdirectories.
+directories in addition to regular files.  Directories may only be
+deleted if they do not contain any files or subdirectories (other than
+@file{.} and @file{..}).
 
 Update the @code{open} system call so that it can also open directories.
 
 Update the @code{open} system call so that it can also open directories.
-Passing @file{.} as the argument to @code{open} must open the current
-directory, regardless of whether @file{.} and @file{..} are fully
-implemented.  Of the existing system calls, only @code{close} needs to
-accept a file descriptor for a directory.
+Of the existing system calls, only @code{close} needs to accept a file
+descriptor for a directory.
 
 Implement the following new system calls:
 
 
 Implement the following new system calls:
 
@@ -213,8 +212,7 @@ name in @var{name}, which must have room for @code{READDIR_MAX_LEN + 1}
 bytes, and returns true.  If no entries are left in the directory,
 returns false.
 
 bytes, and returns true.  If no entries are left in the directory,
 returns false.
 
-@file{.} and @file{..} should not be returned by @code{readdir},
-regardless of whether they are implemented.
+@file{.} and @file{..} should not be returned by @code{readdir}.
 
 If the directory changes while it is open, then it is acceptable for
 some entries not to be read at all or to be read multiple times.
 
 If the directory changes while it is open, then it is acceptable for
 some entries not to be read at all or to be read multiple times.
@@ -230,14 +228,24 @@ Returns true if @var{fd} represents a directory,
 false if it represents an ordinary file.
 @end deftypefn
 
 false if it represents an ordinary file.
 @end deftypefn
 
+@deftypefn {System Call} int inumber (int @var{fd})
+Returns the @dfn{inode number} of the inode associated with @var{fd}.
+Applicable to file descriptors for both files and directories.
+
+An inode number persistently identifies a file or directory.  It is
+unique during the file's existence.  In Pintos, the sector number of the
+inode is suitable for use as an inode number.
+@end deftypefn
+
 We have provided @command{ls} and @command{mkdir} user programs, which
 We have provided @command{ls} and @command{mkdir} user programs, which
-are straightforward once the above syscalls are implemented.  The
-@command{shell} program implements @command{cd} internally.
+are straightforward once the above syscalls are implemented.  
+We have also provided @command{pwd}, which is not so straightforward.
+The @command{shell} program implements @command{cd} internally.
 
 The @code{pintos} @option{put} and @option{get} commands should now
 accept full path names, assuming that the directories used in the
 
 The @code{pintos} @option{put} and @option{get} commands should now
 accept full path names, assuming that the directories used in the
-paths have already been created.  This should not require any extra
-effort on your part.
+paths have already been created.  This should not require any significant
+extra effort on your part.
 
 @node Buffer Cache
 @subsection Buffer Cache
 
 @node Buffer Cache
 @subsection Buffer Cache
@@ -385,13 +393,6 @@ modified by the reference solution.
  30 files changed, 2721 insertions(+), 286 deletions(-)
 @end verbatim
 
  30 files changed, 2721 insertions(+), 286 deletions(-)
 @end verbatim
 
-@item What extra credit opportunities are available?
-
-You may implement Unix-style support for @file{.} and @file{..} in
-relative paths in their projects.
-
-You may submit with VM enabled.
-
 @item Can @code{DISK_SECTOR_SIZE} change?
 
 No, @code{DISK_SECTOR_SIZE} is fixed at 512.  This is a fixed property
 @item Can @code{DISK_SECTOR_SIZE} change?
 
 No, @code{DISK_SECTOR_SIZE} is fixed at 512.  This is a fixed property
@@ -419,16 +420,20 @@ You'll need to consider this when deciding your inode organization.
 @subsection Subdirectories FAQ
 
 @table @b
 @subsection Subdirectories FAQ
 
 @table @b
-@item How should a file name like @samp{//a//b} be interpreted?
+@item How should a file name like @samp{a//b} be interpreted?
 
 Multiple consecutive slashes are equivalent to a single slash, so this
 
 Multiple consecutive slashes are equivalent to a single slash, so this
-file name is the same as @samp{/a/b}.
+file name is the same as @samp{a/b}.
 
 @item How about a file name like @samp{/../x}?
 
 
 @item How about a file name like @samp{/../x}?
 
-If you don't implement @file{.} and @file{..}, then this is not a
-special case.  If you do, then it is equivalent to @samp{/x}.  That is,
-the root directory is its own parent.
+The root directory is its own parent, so it is equivalent to @samp{/x}.
+
+@item How should a file name that ends in @samp{/} be treated?
+
+Most Unix systems allow a slash at the end of the name for a directory,
+and reject other names that end in slashes.  We will allow this
+behavior, as well as simply rejecting a name that ends in a slash.
 @end table
 
 @node Buffer Cache FAQ
 @end table
 
 @node Buffer Cache FAQ
index 1b978e99c24a49c81c753b03669290e8c510134d..63329abea80c7131684b372518e7d2e67b30a489 100644 (file)
@@ -72,6 +72,9 @@ FirstName LastName <email@domain.example>
 >> Describe your code for traversing a user-specified path.  How do
 >> traversals of absolute and relative paths differ?
 
 >> Describe your code for traversing a user-specified path.  How do
 >> traversals of absolute and relative paths differ?
 
+>> Look over "pwd.c" in src/examples.  Briefly explain how it
+>> determines the present working directory.
+
 ---- SYNCHRONIZATION ----
 
 >> How do you prevent races on directory entries?  For example, only one
 ---- SYNCHRONIZATION ----
 
 >> How do you prevent races on directory entries?  For example, only one
index a0725c622bf8389c4b54886edada3abc1e746323..a9e09d73308ea73514230cc3b437b5435c85b268 100644 (file)
@@ -8,6 +8,7 @@ ls
 mcat
 mcp
 mkdir
 mcat
 mcp
 mkdir
+pwd
 rm
 shell
 bubsort
 rm
 shell
 bubsort
index 66bc626d40fb3d9abb8d6c0a6908a6115b7be2e7..2128cc22ff88410aa3f44178fd5e071d78f5c235 100644 (file)
@@ -3,27 +3,32 @@ SRCDIR = ..
 # Test programs to compile, and a list of sources for each.
 # To add a new test, put its name on the PROGS list
 # and then add a name_SRC line that lists its source files.
 # Test programs to compile, and a list of sources for each.
 # To add a new test, put its name on the PROGS list
 # and then add a name_SRC line that lists its source files.
-PROGS = cat cmp cp echo halt hex-dump ls mcat mcp mkdir rm shell \
+PROGS = cat cmp cp echo halt hex-dump ls mcat mcp mkdir pwd rm shell \
        bubsort insult lineup matmult recursor
 
        bubsort insult lineup matmult recursor
 
+# Should work from project 2 onward.
 cat_SRC = cat.c
 cmp_SRC = cmp.c
 cp_SRC = cp.c
 echo_SRC = echo.c
 halt_SRC = halt.c
 hex-dump_SRC = hex-dump.c
 cat_SRC = cat.c
 cmp_SRC = cmp.c
 cp_SRC = cp.c
 echo_SRC = echo.c
 halt_SRC = halt.c
 hex-dump_SRC = hex-dump.c
+insult_SRC = insult.c
+lineup_SRC = lineup.c
 ls_SRC = ls.c
 ls_SRC = ls.c
-mcat_SRC = mcat.c
-mcp_SRC = mcp.c
-mkdir_SRC = mkdir.c
+recursor_SRC = recursor.c
 rm_SRC = rm.c
 rm_SRC = rm.c
-shell_SRC = shell.c
 
 
+# Should work in project 3; also in project 4 if VM is included.
 bubsort_SRC = bubsort.c
 bubsort_SRC = bubsort.c
-insult_SRC = insult.c
-lineup_SRC = lineup.c
 matmult_SRC = matmult.c
 matmult_SRC = matmult.c
-recursor_SRC = recursor.c
+mcat_SRC = mcat.c
+mcp_SRC = mcp.c
+
+# Should work in project 4.
+mkdir_SRC = mkdir.c
+pwd_SRC = pwd.c
+shell_SRC = shell.c
 
 include $(SRCDIR)/Make.config
 include $(SRCDIR)/Makefile.userprog
 
 include $(SRCDIR)/Make.config
 include $(SRCDIR)/Makefile.userprog
index 5907a6cedb90ab507e6f4feee4502f385c1bcdd7..d927bc1da696763fae6c2a844d7a4df7c1062eac 100644 (file)
@@ -5,8 +5,8 @@
    named.
 
    By default, only the name of each file is printed.  If "-l" is
    named.
 
    By default, only the name of each file is printed.  If "-l" is
-   given as the first argument, the type and size of each file is
-   also printed. */
+   given as the first argument, the type, size, and inumber of
+   each file is also printed.  This won't work until project 4. */
 
 #include <syscall.h>
 #include <stdio.h>
 
 #include <syscall.h>
 #include <stdio.h>
@@ -25,7 +25,12 @@ list_dir (const char *dir, bool verbose)
   if (isdir (dir_fd))
     {
       char name[READDIR_MAX_LEN];
   if (isdir (dir_fd))
     {
       char name[READDIR_MAX_LEN];
-      printf ("%s:\n", dir);
+
+      printf ("%s", dir);
+      if (verbose)
+        printf (" (inumber %d)", inumber (dir_fd));
+      printf (":\n");
+
       while (readdir (dir_fd, name)) 
         {
           printf ("%s", name); 
       while (readdir (dir_fd, name)) 
         {
           printf ("%s", name); 
@@ -34,14 +39,7 @@ list_dir (const char *dir, bool verbose)
               char full_name[128];
               int entry_fd;
 
               char full_name[128];
               int entry_fd;
 
-              if (strcmp (dir, "."))
-                snprintf (full_name, sizeof full_name, "%s/%s", dir, name);
-              else 
-                {
-                  /* This is a special case for implementations
-                     that don't fully understand . and .. */
-                  strlcpy (full_name, name, sizeof full_name); 
-                }
+              snprintf (full_name, sizeof full_name, "%s/%s", dir, name);
               entry_fd = open (full_name);
 
               printf (": ");
               entry_fd = open (full_name);
 
               printf (": ");
@@ -51,6 +49,7 @@ list_dir (const char *dir, bool verbose)
                     printf ("directory");
                   else
                     printf ("%d-byte file", filesize (entry_fd));
                     printf ("directory");
                   else
                     printf ("%d-byte file", filesize (entry_fd));
+                  printf (", inumber %d", inumber (entry_fd));
                 }
               else
                 printf ("open failed");
                 }
               else
                 printf ("open failed");
diff --git a/src/examples/pwd.c b/src/examples/pwd.c
new file mode 100644 (file)
index 0000000..b2441f5
--- /dev/null
@@ -0,0 +1,152 @@
+/* pwd.c
+   
+   Prints the absolute name of the present working directory. */
+
+#include <syscall.h>
+#include <stdbool.h>
+#include <stdio.h>
+#include <string.h>
+
+static bool getcwd (char *cwd, size_t cwd_size);
+
+int
+main (void) 
+{
+  char cwd[128];
+  if (getcwd (cwd, sizeof cwd)) 
+    {
+      printf ("%s\n", cwd);
+      return 0; 
+    }
+  else 
+    {
+      printf ("error\n");
+      return 1; 
+    }
+}
+\f
+/* Stores the inode number for FILE_NAME in *INUM.
+   Returns true if successful, false if the file could not be
+   opened. */
+static bool
+get_inumber (const char *file_name, int *inum) 
+{
+  int fd = open (file_name);
+  if (fd >= 0) 
+    {
+      *inum = inumber (fd);
+      close (fd);
+      return true;
+    }
+  else
+    return false;
+}
+
+/* Prepends PREFIX to the characters stored in the final *DST_LEN
+   bytes of the DST_SIZE-byte buffer that starts at DST.
+   Returns true if successful, false if adding that many
+   characters, plus a null terminator, would overflow the buffer.
+   (No null terminator is actually added or depended upon, but
+   its space is accounted for.) */
+static bool
+prepend (const char *prefix,
+         char *dst, size_t *dst_len, size_t dst_size) 
+{
+  size_t prefix_len = strlen (prefix);
+  if (prefix_len + *dst_len + 1 <= dst_size) 
+    {
+      *dst_len += prefix_len;
+      memcpy ((dst + dst_size) - *dst_len, prefix, prefix_len);
+      return true;
+    }
+  else
+    return false;
+}
+
+/* Stores the current working directory, as a null-terminated
+   string, in the CWD_SIZE bytes in CWD.
+   Returns true if successful, false on error.  Errors include
+   system errors, directory trees deeper than MAX_LEVEL levels,
+   and insufficient space in CWD. */
+static bool
+getcwd (char *cwd, size_t cwd_size) 
+{
+  size_t cwd_len = 0;   
+  
+#define MAX_LEVEL 20
+  char name[MAX_LEVEL * 3 + 1 + READDIR_MAX_LEN + 1];
+  char *namep;
+
+  int child_inum;
+
+  /* Make sure there's enough space for at least "/". */
+  if (cwd_size < 2)
+    return false;
+
+  /* Get inumber for current directory. */
+  if (!get_inumber (".", &child_inum))
+    return false;
+
+  namep = name;
+  for (;;)
+    {
+      int parent_inum, parent_fd;
+
+      /* Compose "../../../..", etc., in NAME. */
+      if ((namep - name) > MAX_LEVEL * 3)
+        return false;
+      *namep++ = '.';
+      *namep++ = '.';
+      *namep = '\0';
+
+      /* Open directory. */
+      parent_fd = open (name);
+      if (parent_fd < 0)
+        return false;
+      *namep++ = '/';
+
+      /* If parent and child have the same inumber,
+         then we've arrived at the root. */
+      parent_inum = inumber (parent_fd);
+      if (parent_inum == child_inum)
+        break;
+
+      /* Find name of file in parent directory with the child's
+         inumber. */
+      for (;;)
+        {
+          int test_inum;
+          if (!readdir (parent_fd, namep) || !get_inumber (name, &test_inum)) 
+            {
+              close (parent_fd);
+              return false; 
+            }
+          if (test_inum == child_inum)
+            break;
+        }
+      close (parent_fd);
+
+      /* Prepend "/name" to CWD. */
+      if (!prepend (namep - 1, cwd, &cwd_len, cwd_size))
+        return false;
+
+      /* Move up. */
+      child_inum = parent_inum;
+    }
+
+  /* Finalize CWD. */
+  if (cwd_len > 0) 
+    {
+      /* Move the string to the beginning of CWD,
+         and null-terminate it. */
+      memmove (cwd, (cwd + cwd_size) - cwd_len, cwd_len);
+      cwd[cwd_len] = '\0';
+    }
+  else 
+    {
+      /* Special case for the root. */
+      strlcpy (cwd, "/", cwd_size); 
+    }
+  
+  return true;
+}
index 5df0d9d6b01145d7b132fab8cfa4577c039097da..fedda08e1d6730421a129e286117298821fd75fb 100644 (file)
@@ -91,65 +91,6 @@ filesys_remove (const char *name)
   return success;
 }
 \f
   return success;
 }
 \f
-static void must_succeed_function (int, bool) NO_INLINE;
-#define MUST_SUCCEED(EXPR) must_succeed_function (__LINE__, EXPR)
-
-/* Performs basic sanity checks on the file system.
-   The file system should not contain a file named `foo' when
-   called. */
-void
-filesys_self_test (void)
-{
-  static const char s[] = "This is a test string.";
-  static const char zeros[sizeof s] = {0};
-  struct file *file;
-  char s2[sizeof s];
-  int i;
-
-  filesys_remove ("foo");
-  for (i = 0; i < 2; i++) 
-    {
-      /* Create file and check that it contains zeros
-         throughout the created length. */
-      MUST_SUCCEED (filesys_create ("foo", sizeof s));
-      MUST_SUCCEED ((file = filesys_open ("foo")) != NULL);
-      MUST_SUCCEED (file_read (file, s2, sizeof s2) == sizeof s2);
-      MUST_SUCCEED (memcmp (s2, zeros, sizeof s) == 0);
-      MUST_SUCCEED (file_tell (file) == sizeof s);
-      MUST_SUCCEED (file_length (file) == sizeof s);
-      file_close (file);
-
-      /* Reopen file and write to it. */
-      MUST_SUCCEED ((file = filesys_open ("foo")) != NULL);
-      MUST_SUCCEED (file_write (file, s, sizeof s) == sizeof s);
-      MUST_SUCCEED (file_tell (file) == sizeof s);
-      MUST_SUCCEED (file_length (file) == sizeof s);
-      file_close (file);
-
-      /* Reopen file and verify that it reads back correctly.
-         Delete file while open to check proper semantics. */
-      MUST_SUCCEED ((file = filesys_open ("foo")) != NULL);
-      MUST_SUCCEED (filesys_remove ("foo"));
-      MUST_SUCCEED (filesys_open ("foo") == NULL);
-      MUST_SUCCEED (file_read (file, s2, sizeof s) == sizeof s);
-      MUST_SUCCEED (memcmp (s, s2, sizeof s) == 0);
-      MUST_SUCCEED (file_tell (file) == sizeof s);
-      MUST_SUCCEED (file_length (file) == sizeof s);
-      file_close (file);
-    }
-  
-  printf ("filesys: self test ok\n");
-}
-
-/* If SUCCESS is false, panics with an error complaining about
-   LINE_NO. */
-static void 
-must_succeed_function (int line_no, bool success) 
-{
-  if (!success)
-    PANIC ("filesys_self_test: operation failed on line %d", line_no);
-}
-\f
 /* Formats the file system. */
 static void
 do_format (void)
 /* Formats the file system. */
 static void
 do_format (void)
index 5a03f81c99d0f5923f2f45f1027272fcab4517b8..caef83c45c17f4986a3fc8838769a64d7a1e7606 100644 (file)
@@ -17,6 +17,4 @@ bool filesys_create (const char *name, off_t initial_size);
 struct file *filesys_open (const char *name);
 bool filesys_remove (const char *name);
 
 struct file *filesys_open (const char *name);
 bool filesys_remove (const char *name);
 
-void filesys_self_test (void);
-
 #endif /* filesys/filesys.h */
 #endif /* filesys/filesys.h */
index 17f4b4680f656fdbda2e8344b36366ba478a6315..d890ed8d3c7f0375dc9f3a6a1178254d2c2db011 100644 (file)
@@ -143,13 +143,20 @@ inode_open (disk_sector_t sector)
 
 /* Reopens and returns INODE. */
 struct inode *
 
 /* Reopens and returns INODE. */
 struct inode *
-inode_reopen (struct inode *inode) 
+inode_reopen (struct inode *inode)
 {
 {
-  if (inode != NULL) 
+  if (inode != NULL)
     inode->open_cnt++;
   return inode;
 }
 
     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. */
 /* 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. */
index e8aac13b838fc6c550725799ed870235416814d2..be7df634ef499bf83390647d75a92edb4532ecc8 100644 (file)
@@ -11,6 +11,7 @@ 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 *);
 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);
 void inode_close (struct inode *);
 void inode_remove (struct inode *);
 off_t inode_read_at (struct inode *, void *, off_t size, off_t offset);
index eb1e0ee907dd62d22265d90e0e9e38db8b51f067..21a7af952f8728f93b77d6867ebbf60a7699864c 100644 (file)
@@ -27,7 +27,8 @@ enum
     SYS_CHDIR,                  /* Change the current directory. */
     SYS_MKDIR,                  /* Create a directory. */
     SYS_READDIR,                /* Reads a directory entry. */
     SYS_CHDIR,                  /* Change the current directory. */
     SYS_MKDIR,                  /* Create a directory. */
     SYS_READDIR,                /* Reads a directory entry. */
-    SYS_ISDIR                   /* Tests if a fd represents a directory. */
+    SYS_ISDIR,                  /* Tests if a fd represents a directory. */
+    SYS_INUMBER                 /* Returns the inode number for a fd. */
   };
 
 #endif /* lib/syscall-nr.h */
   };
 
 #endif /* lib/syscall-nr.h */
index 858b77c7d45d47ef7aca231f921ce88f5a257c6f..a9c5bc8500c517f58169a52c1dee5f1b78a3edff 100644 (file)
@@ -176,3 +176,9 @@ isdir (int fd)
 {
   return syscall1 (SYS_ISDIR, fd);
 }
 {
   return syscall1 (SYS_ISDIR, fd);
 }
+
+int
+inumber (int fd) 
+{
+  return syscall1 (SYS_INUMBER, fd);
+}
index 340d1b15fea253155bbe30c50eb7bc9cb73ee383..d9487d3df7b73ad67872be69dae90697990095f3 100644 (file)
@@ -31,5 +31,6 @@ bool chdir (const char *dir);
 bool mkdir (const char *dir);
 bool readdir (int fd, char name[READDIR_MAX_LEN + 1]);
 bool isdir (int fd);
 bool mkdir (const char *dir);
 bool readdir (int fd, char name[READDIR_MAX_LEN + 1]);
 bool isdir (int fd);
+int inumber (int fd);
 
 #endif /* lib/user/syscall.h */
 
 #endif /* lib/user/syscall.h */
index 4179500890498c98bcff4c6a5331d0ad32ada14a..dfb6a5dc4b323f56e7ee98c9a8ff9dad3278c500 100644 (file)
@@ -1,3 +1,4 @@
+examples
 filesys
 list
 p1
 filesys
 list
 p1