From bfc9e18a6723b2315ef521282a8b42119338ece9 Mon Sep 17 00:00:00 2001 From: Ben Pfaff Date: Mon, 22 May 2006 18:47:19 +0000 Subject: [PATCH] File system project updates: 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. --- doc/filesys.texi | 57 ++++++++------- doc/filesys.tmpl | 3 + src/examples/.cvsignore | 1 + src/examples/Makefile | 21 +++--- src/examples/ls.c | 21 +++--- src/examples/pwd.c | 152 ++++++++++++++++++++++++++++++++++++++++ src/filesys/filesys.c | 59 ---------------- src/filesys/filesys.h | 2 - src/filesys/inode.c | 11 ++- src/filesys/inode.h | 1 + src/lib/syscall-nr.h | 3 +- src/lib/user/syscall.c | 6 ++ src/lib/user/syscall.h | 1 + tests/.cvsignore | 1 + 14 files changed, 230 insertions(+), 109 deletions(-) create mode 100644 src/examples/pwd.c diff --git a/doc/filesys.texi b/doc/filesys.texi index 8e4dc4f..49117a5 100644 --- a/doc/filesys.texi +++ b/doc/filesys.texi @@ -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{/}). -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 -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. -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: @@ -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. -@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. @@ -230,14 +228,24 @@ Returns true if @var{fd} represents a directory, 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 -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 -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 @@ -385,13 +393,6 @@ modified by the reference solution. 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 @@ -419,16 +420,20 @@ You'll need to consider this when deciding your inode organization. @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 -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}? -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 diff --git a/doc/filesys.tmpl b/doc/filesys.tmpl index 1b978e9..63329ab 100644 --- a/doc/filesys.tmpl +++ b/doc/filesys.tmpl @@ -72,6 +72,9 @@ FirstName LastName >> 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 diff --git a/src/examples/.cvsignore b/src/examples/.cvsignore index a0725c6..a9e09d7 100644 --- a/src/examples/.cvsignore +++ b/src/examples/.cvsignore @@ -8,6 +8,7 @@ ls mcat mcp mkdir +pwd rm shell bubsort diff --git a/src/examples/Makefile b/src/examples/Makefile index 66bc626..2128cc2 100644 --- a/src/examples/Makefile +++ b/src/examples/Makefile @@ -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. -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 +# 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 +insult_SRC = insult.c +lineup_SRC = lineup.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 -shell_SRC = shell.c +# Should work in project 3; also in project 4 if VM is included. bubsort_SRC = bubsort.c -insult_SRC = insult.c -lineup_SRC = lineup.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 diff --git a/src/examples/ls.c b/src/examples/ls.c index 5907a6c..d927bc1 100644 --- a/src/examples/ls.c +++ b/src/examples/ls.c @@ -5,8 +5,8 @@ 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 #include @@ -25,7 +25,12 @@ list_dir (const char *dir, bool verbose) 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); @@ -34,14 +39,7 @@ list_dir (const char *dir, bool verbose) 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 (": "); @@ -51,6 +49,7 @@ list_dir (const char *dir, bool verbose) printf ("directory"); else printf ("%d-byte file", filesize (entry_fd)); + printf (", inumber %d", inumber (entry_fd)); } else printf ("open failed"); diff --git a/src/examples/pwd.c b/src/examples/pwd.c new file mode 100644 index 0000000..b2441f5 --- /dev/null +++ b/src/examples/pwd.c @@ -0,0 +1,152 @@ +/* pwd.c + + Prints the absolute name of the present working directory. */ + +#include +#include +#include +#include + +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; + } +} + +/* 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; +} diff --git a/src/filesys/filesys.c b/src/filesys/filesys.c index 5df0d9d..fedda08 100644 --- a/src/filesys/filesys.c +++ b/src/filesys/filesys.c @@ -91,65 +91,6 @@ filesys_remove (const char *name) return success; } -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); -} - /* Formats the file system. */ static void do_format (void) diff --git a/src/filesys/filesys.h b/src/filesys/filesys.h index 5a03f81..caef83c 100644 --- a/src/filesys/filesys.h +++ b/src/filesys/filesys.h @@ -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); -void filesys_self_test (void); - #endif /* filesys/filesys.h */ diff --git a/src/filesys/inode.c b/src/filesys/inode.c index 17f4b46..d890ed8 100644 --- a/src/filesys/inode.c +++ b/src/filesys/inode.c @@ -143,13 +143,20 @@ inode_open (disk_sector_t sector) /* 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; } +/* 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. */ diff --git a/src/filesys/inode.h b/src/filesys/inode.h index e8aac13..be7df63 100644 --- a/src/filesys/inode.h +++ b/src/filesys/inode.h @@ -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 *); +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); diff --git a/src/lib/syscall-nr.h b/src/lib/syscall-nr.h index eb1e0ee..21a7af9 100644 --- a/src/lib/syscall-nr.h +++ b/src/lib/syscall-nr.h @@ -27,7 +27,8 @@ enum 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 */ diff --git a/src/lib/user/syscall.c b/src/lib/user/syscall.c index 858b77c..a9c5bc8 100644 --- a/src/lib/user/syscall.c +++ b/src/lib/user/syscall.c @@ -176,3 +176,9 @@ isdir (int fd) { return syscall1 (SYS_ISDIR, fd); } + +int +inumber (int fd) +{ + return syscall1 (SYS_INUMBER, fd); +} diff --git a/src/lib/user/syscall.h b/src/lib/user/syscall.h index 340d1b1..d9487d3 100644 --- a/src/lib/user/syscall.h +++ b/src/lib/user/syscall.h @@ -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); +int inumber (int fd); #endif /* lib/user/syscall.h */ diff --git a/tests/.cvsignore b/tests/.cvsignore index 4179500..dfb6a5d 100644 --- a/tests/.cvsignore +++ b/tests/.cvsignore @@ -1,3 +1,4 @@ +examples filesys list p1 -- 2.30.2