EE469 Spring 2004 Lab 5: File System Implementation
Due 2004 Apr 26, Monday, 11:59PM
EXTENSION: Due 2004 Apr 29, Thursday, 11:59PM EST.

Overview

Copy the file /home/shay/g/ee469/labs/common/lab5.tar to your ee469 directory and untar it (tar -xvf lab5.tar). This will create a directory lab5. When you change over to this directory, you will find three directories, one for each part. You have to implement each of the following parts in each of these directories. DO NOT modify this directory structure. If you modify it, you may loose substantial points (you may even get a zero grade). Follow the instructions in each of the following parts as to which files to modify.

Assignments

1. (20 points) Lower-level file system support

   Initialize and format the file system (superblocks,inodes), and raw disk I/O support to the simulated disk.

   File System:

   • We will simulate the file system using a Unix file, named "/tmp/ee469gXFileSystem.dlxos", where the "X" is your group number. You should use this name to avoid conflicts with other ECE469 teams working on the same project. We recommend that you delete this file between runs of the DLX simulator, to prevent your file system code from behaving unexpectedly. This filename is hardcoded into the source file fsys.c; find the line #define FILESYSTEMNAME "/tmp/FileSystem.dlxos" and change it to the new, group-specific name. This file will store all the necessary information related to a filesystem such as the superblock, inodes, and data blocks. When the file system is opened, the stored metadata of the filesystem should be copied to the variables specified in fsys.h (superblock -> sb, i-nodes -> inodes, free block vector -> fbv). The file will consist of blocks of size 1 Kbytes. Here is the format of the file system:
     • 0th block: In regular file systems the first block is usually used for booting, but since we do not have to deal with booting we will leave the first block empty.
     • 1st block (Superblock): Second block will be used for the superblock. Superblock contains all the information about the file system, (valid bit, size, number of inodes, used/free inodes, etc.
     • 2nd - 9th blocks (inodes): Inodes are used to keep track of files in the file system. Each inode represents a file, and contains the information about the number of blocks used for the file, size of the file in bytes, pointers to blocks, etc. Our file system supports 128 inodes.
     • 10 - 11th block (free block vector): This block is used to keep track of which data blocks are used and which ones are free. Each bit in this block represents a block, so 16k blocks are represented by two 1KB (8 bits each) blocks. So each free block vector is an array of uint32s of size 512.
     • 12th - 16383th blocks (data blocks): the last 16k blocks are used to store the data the files contain.

   • Using Unix files with dlxos
     • int NewFileSys(): Creates a new file system using the specifications given above. (Use "/tmp/ee469gXFileSystem.dlxos" as the name of the file.) The first block should be empty, superblock should have s_valid = 1; and the correct filesystem size should be written. All other values in the filesystem should be set to 0 when the filesystem is created initially. You can do that by using bzero() to set a string equal to zero and writing this string, over and over to the "/tmp/ee469gXFileSystem.dlxos". Returns 0 if successful, and -1 when there is an error.
     • int OpenFileSys(): Opens an existing file system, or creates one if there is none. When the file system is opened, the superblock, inodes and free block vectors are copied to the memory for easier and faster access. If the opened file system is not valid (e.g. it has not been shutdown properly (s_valid != 1)), overwrite the file system and create a new one. After opening the file system set the s_valid flag of the superblock to 0 on the disk. To make sure that the next OpenFileSys() will fail without a ShutdownFileSys() call. Returns 0 if successful, and -1 when there is an error.
     • int ShutdownFileSys(): Shutdown the file system by copying the superblock, inodes and free block vectors from memory to the file. And set the valid bit equal to one. You should write the superblock after writing the other blocks, so that the file system stays invalid if the shutdown function is interrupted. Returns 0 if successful, and -1 when there is an error.

   • To make your life easier in implementing the above functions, we provide with the following kernel functions.

     Note: Because you cannot write to or read from an unallocated block with the provided Read/WriteRawData functions, you have to use a flag (new_flag) in these functions when you try to read/write information from the file system. When this flag is set equal to 1, you can read/write to any block in the filesystem. But when the flag is set to 0, you can only read/write to the allocated data blocks (starting with the 12th block).

     • uint32 AllocateBlock(): Allocates a free block for an inode to use. Returns the (absolute) index of the block (the first data block has an offset 12, because the first 12 blocks are used for storing other information. The free block vector (fbv) only stores information about the data blocks, therefore the 0th block in the fbv is actually the 12th block in the filesystem.). Returns 0 if there is an error.
     • int FreeBlock(uint32 blocknum): Frees an already allocated block, and updates the free block vector. You cannot free blocks 0-11. Returns 0 if successful, and -1 when there is an error.
     • int WriteRawData(void *memory, uint32 blocknum, char *diskname ): Write one block from memory to the block (blocknum) of file (diskname). To write to the filesystem the filename should be "/tmp/ee469gXFileSystem.dlxos". Returns 0 if successful, and -1 when there is an error.
     • int ReadRawData(void *memory, uint32 blocknum, char *diskname): Read one block from block (blocknum) of file (filename) to memory. To read from the filesystem the filename should be "/tmp/ee469gXFileSystem.dlxos". Returns 0 if successful, and -1 when there is an error.

     For your information, we implemented the above provided functions using Unix file functions. There are several functions dealing with Unix files, as defined in filesys.c and filesys.h. These functions are wrappers. They in turn invoke C functions like fopen, fclose, fseek, fwrite and fread. In implementing OpenFileSys(), you will need to use FsOpen() to check whether "/tmp/ee469gXFileSystem.dlxos" exists. If the file does not exist, you will need to use FsOpen() to create it. Remember to call FsClose() to close it.

   Testing and grading: Put your code in fsys.c, where a skeleton has been created for you. Note that all of the functions are kernel functions, meaning that you don't have user interfaces to them. You should test your program by creating system processes. In your test, you should be able to use the provided kernel to create and open a filesystem and be able to successfully close it.

2. (40 points) Basic file operations

   For this part, you will write simple system level file operation. A file table to store information about opened files has been created for you. You will also need to write the following system routines:

   • inode_t MkNod(unsigned char Permission, unsigned char type, unsigned char ownerid): Try to allocate an inode and setup its data structure. Return error (-1) if there is no more inode to use. All the fields in the inode structure need to be initialized correctly
   • int file_open(inode_t inode, int Mode): take an inode and return a newly allocated file handle. It will set up the file table data structure according to the Mode, which can be R,W or RW. It will return error (-1) if the open file limit is reach or the process doesn't have permission to that file. Note that our permission is similar to Unix, except that we don't have group permission (only owner and other) Upon file open the current position is always set to 0. The function should not change the inode in any way. When you facilitate file I/O with filenames in part3, you will need to explicitly truncate the file if you wish to write to it.
   • int file_read(int filehandle, char *to, uint32 size ): read size byte from current position of the file filehandle to the buffer and return number of byte actually read. It should return an error (-1) if the file isn't opened for reading. For file read and write, you should adjust the current position according to the actual bytes read or written
   • int file_write(int filehandle , char* from, uint32 size ): write size byte to current position of the file filehandle from the buffer and return number of byte actually written. It should return an error (-1) if the file isn't opened for writing. In this function you should leave the unmodified data in the file intact. i.e: if you call file_write on a 34 byte file and write 1 byte at the beginning, the file will remain 34 byte with the 1st byte change.
   • int file_close(int filehandle): close the file and free up its file table entry
   • int file_seek(int filehandle, int offset, uint32 reference): seek to new file position by offset. It can seek from beginning, end or current position base on value of reference (SEEK_SET, SEEK_END, SEEK_CUR) return an error (-1) if the file is not opened. The function should not seek beyond file's limit. If you try to seek beyond EOF, the function should set currpos to the end of file (EOF).If you try to seek before the beginning, the currpos should be set to the beginning. Note that these are not errors. The only error you can have in this function is that the file is not opened by the calling process.
   • int file_chmod (inode_t inode, unsigned char Permission): Change permission of the file. Only the owner can change the file permission. The file permission is organize as a bit vector as follow:

   ur uw ux or ow ox

   Where u is for the user that owns the file and o is for other processes. It should return an error (-1) if the calling process doesn't own the file.

   • int inode_clear_resources(inode_t inode): remove any resources(blocks) of inode. And set the file size and number of block used to 0. Other info of the inode remains unchanged. It will return -1 if the inode is not in use. You don't have to check permissions explicitly within this function. Instead, you will check the permissions before calling this function while implementing corresponding functions in part 3.
   • int file_delete(inode_t inode): delete the inode and all resources associated with it. Return -1 if the inode is not in use. You don't have to check permissions explicitly within this function. Instead, you will check the permissions before calling this function while implementing corresponding functions in part 3.

   Testing and grading: Put your code in inode.c, where a skeleton has been created for you. Note that all of the functions are kernel functions, meaning that you don't have user interfaces to them. You should test your program by creating system processes. In your test, you should be able to use the provided kernel to create and write files and use your kernel to read them and vice versa. The user interface that eventually call these functions only support 100 bytes of data. Therefore it is ok to assume the maximal size that you have to read or write is 100 bytes or less per function call.

3. (40 points) Multi-level directory support

   Using the system-level file support in the previous part, implement a directory structure for dlxos. We will specify the filenames the same way they are specified in Unix. Thus the filename "/a/b" means file "b" in directory "a" located in the root directory (denoted by "/"). Also the filename "a/b" means the file "b" in directory "a", which in turn is located in the current directory. Thus you need to maintain the current directory information on per-process basis. We recommend you maintain this in the PCB under an integer field currentDIR, where you would store the inode number of the current directory. To simplify the problem, we do not support the special directory entries "." and "..". Thus the path to any file or directory can be specified only from the root directory or the current directory. To specify the path of a file from the current directory, the file needs to be a child of the current directory in the directory hierarchy.

   Fundamentals of Directories: At the system level, we will treat the directories and the files almost identically. This is evident from the fact that we asked you to write common system-level handlers for files and directories. Directories are special files that are written in a proper structure. We will use a convention similar to that in Unix. A directory will be a sequence of fixed-length directory entries. Each directory entry is 34 bytes wide. The first 30 bytes contain the file name, and the last 4 bytes contain the inode number corresponding to that file. Thus a filename can at most be 30 bytes long. If the filename is shorter than 30 characters, the character after the filename should be '\0', thus clearly marking the end of the filename. Also, if the first character in a directory entry is '\0', then it means that the directory entry is empty, and can be used for creating further files. The character '/' is not a legal character in the filename, and hence the directory entry should not have this character. Note that a directory should be considered to be empty if and only if all of its directory entries are empty. Thus to remove a file (or a directory) from the file system, all you have to do is mark the beginning of the corresponding directory entry by '\0', and release the resources associated with that file (or directory). You have written functions for releasing the resources in the previous part. Also, to create a file or directory, you need to create an inode with proper attributes, and create a directory entry for that inode.

   Directory and File permissions: As mentioned in the previous part, permissions for a directory or a file are stored in the corresponding inode. These are stored in the format uruwuxorowox, where r, w, and x have their usual meanings. As per the Unix convention, we treat the x (EXECUTE) permission for a directory to be the permission to change over to that directory. To open a file, the calling process needs to have at least EXECUTE permission to all the directories along that path, and required permissions for a specified file. To change over to a directory, a process needs to have execute permission for all the directories along the path. Thus, to open the file "/a/b" in read mode, the process needs to have execute permission to "/", and "a" and read permission to "b". Also, to change over to the directory "/a/c", the process needs to have execute permission to all the three directories "/", "a", and "c". Note that deleting a file (or a directory) is equivalent to writing to its parent directory. Thus, to delete a file or a directory, you need to have write and execute permission to its parent directory, and execute permission to all the other directories along the path. As already mentioned, the permissions are divided into two sets, user (u) and the others (o). Thus to check permissions, each process needs to know its userid. We have modified process.c so that the userid of a process gets stored in the PCB whenever it is created. You will have to compare this field with the ownerid of the file (ownerid of a file is the userid of the process that created it), and check the appropriate set of permissions accordingly.

   You will have to support the following functions:

   1. file_t fopen(char *path, char *mode)
      Open the specified file in the specified mode. The path is either specified from the current directory, or from the root directory. The modes supported are "r", "w" "rw", "a", and "ra". "r" stands for read, "w" stands for write, and "a" stands for append. On success, the function should return a valid file handle. The various modes and success requirements are as follows:
      1. "r": All the directories along the path should exist (note that all the names in the path except for the leaf name needs to be a directory name) and should have EXECUTE permission. Also the leaf node needs to exist and should have read permission. The file should be opened in read mode. The position in the file should be set to the beginning of the file.
      2. "w": All the directories along the path should exist (note that all the names in the path except for the leaf name needs to be a directory name) and should have EXECUTE permission. Also the leaf node needs to exist and should have write permissions. In addition, the leaf node should be a  file (not a directory, you should not let users open directories for writing). The file should be opened in write mode. The position in the file should be set to the beginning of the file. The file should be truncated to size 0 (i.e. all existing data in the file should be deleted, and all the disk blocks freed). Also, if the leaf node does not exist, a file by that name should be created (for this the parent of the leaf should have write permission, otherwise it is an error).
      3. "rw": All the directories along the path should exist (note that all the names in the path except for the leaf name needs to be a directory name) and should have EXECUTE permission. Also the leaf node needs to exist and should have read and write permissions. In addition, the leaf node should be a  file (not a directory, you should not let users open directories for writing). The file should be opened in read and write mode. The position in the file should be set to the beginning of the file. The file should be truncated to size 0 (i.e. all existing data in the file should be deleted, and all the disk blocks freed). Also, if the leaf node does not exist, a file by that name should be created (for this the parent of the leaf should have write permission, otherwise it is an error).
      4. "a": All the directories along the path should exist (note that all the names in the path except for the leaf name needs to be a directory name) and should have EXECUTE permission. Also the leaf node needs to exist and should have write permissions. In addition, the leaf node should be a file (not a directory, you should not let users open directories for writing). The file should be opened in write mode. The position in the file should be set to the end of the file. The file should NOT be truncated to size 0 (i.e. unless an explicit write occurs, the contents of the file should not be changed). Also, if the leaf node does not exist, a file by that name should be created (for this the parent of the leaf should have write permission, otherwise it is an error).
      5. "ra": All the directories along the path should exist (note that all the names in the path except for the leaf name needs to be a directory name) and should have EXECUTE permission. Also the leaf node needs to exist and should have read and write permissions. In addition, the leaf node should be file (not a directory, you should not let users open directories for writing). The file should be opened in read and write mode. The position in the file should be set to the end of the file. The file should NOT be truncated to size 0 (i.e. unless an explicit write occurs, the contents of the file should not be changed). Also, if the leaf node does not exist, a file by that name should be created (for this the parent of the leaf should have write permission, otherwise it is an error).
      Example usage:
      fd = fopen("/a/b/c", "r");
      fd = fopen("d/e/f", "ra");
      
      When someone opens an already opened file, then a new file handle should be returned, irrespecitve of the mode in which the file is (being) opened. So
      fd1 = fopen("/a/b/c", some_mode);
      and
      fd2 = fopen("/a/b/c", maybe_some_other_mode);
      should return different file handles.
   2. int fclose(file_t fd)
      Close the opened file corresponding to the file descriptor fd. On success the function should return 0, otherwise it should return -1. The function would fail if the specified file is not opened.
      Example Usage:
      result = fclose(fd);
   3. int fread(file_t fd, char *buff, uint32 size)
      Read size bytes from the file corresponding to fd. For this function to succeed, the file should have been opened in "r", "rw", or "ra" mode. Note that the trap interface we have provided for this function can read at most 100 bytes from a file at a time. Hence you can assume that size is always less than or equal to 100. The buffer should have enough space to hold size bytes. The function returns the number of bytes read, which is equal to size, unless an end of file is reached before reading size bytes. The function should increment the current position in the file by the number of bytes read. You just need to call file_read() from this function.
      Example Usage:
      size = fread(fd, buff, 5);
   4. int fwrite(file_t fd. char *buff, uint32 size)
      Write size bytes to the file corresponding to fd. For this function to succeed, the file should have been opened in "w", "rw", "a", or "ra" mode. Note that the trap interface we have provided for this function can write at most 100 bytes to a file at a time. Hence you can assume that size is always less than or equal to 100. The buffer is assumed to hold atleast size bytes. The function returns the number of bytes written, which is equal to size, unless maximum allowable size is reached (or disk gets full) before writing size bytes. The function should increment the current position in the file by the number of bytes written. You just need to call file_write() from this function. The call to this function should modify only the bytes written, and should leave all the other bytes in the file untouched.
      Example Usage:
      sz = fwrite(fd, "abcdefg", 5);
   5. int fremove(char *path)
      Remove the file specified by the path. For this function to succeed, all the directories on the path should have EXECUTE permission. The leaf node itself should be a regular file (not a directory, there is a separate function for removing directories). In addition to execute, the parent directory of the leaf node should also have WRITE permission. On success, this function should clear the directory entry corresponding to the leaf node, and free all the resources associated with the leaf node. Also on success, this function should return 0, otherwise it should return a non-zero value.
      Example Usage:
      result = fremove("a/c");
   6. int chmod(char *path, int mode)
      Change the permissions of the file or directory identified by the specified path. For this function to succeed, all the directories along the path, except for the leaf node need to have EXECUTE permission. Also the ownerid of the leaf node should match the userid of the calling process. On success, this function should modify the permissions of the file, and return 0. On failure, it should return a non-zero value without modifying the permissions.
      Example Usage:
      result = chmod("a/c", 077);
   7. int mkdir(char *path, int permissions)
      Create a directory along the specified path with appropriate permissions. For this function to succeed, all the directories along the path should have execute permission. In addition, the leaf node should not exist, and the parent directory of the leaf should have write permission. On success, it returns 0, otherwise it returns a non-zero value.
      Example Usage:
      result = mkdir("/a", 077);
   8. int rmdir(char *path)
      This function works exactly like fremove(), except for that it removes a directory, and not a file. Unlike for fremove(), this function also needs that the leaf directory be empty (i.e. all the directory entries in this directory be marked by '\0') in order to succeed. If called to remove the root directory, this function should fail even if the root directory is empty. If the leaf directory is not empty, this function fails. On success, it returns 0, otherwise it returns a non-zero value.
      Example Usage:
      result = rmdir("/a");
   9. int chdir(char *path)
      Change the current directory of the calling process to the specified path. For this function to succeed, all the nodes along the path (including the leaf node) need to be directories. All these nodes also need to have EXECUTE permission. On success, it should set the currentDIR field in the PCB to the inode of the leaf node, and should return 0. Otherwise it should return a non-zero value.
      Example Usage:
      result = chdir("/a");
       
   API Provided: We have provided all the trap interfaces required for this part. The system functions that these trap interfaces call are specified in the file lab5-api.h. You will have to modify these system functions.

   Implementation Issues: Implement all your code in the files treestruct.c and treestruct.h located in the directory lab5_3. Also copy the file inode.c from the previous part (lab5_2) to this directory, as you will be using the functionality that you have implemented in that file. Do not modify the makefile as it is going to be replaced during grading. Even if you do modify the makefile, make sure that you are still able to build the kernel with the old makefile.
   For this part you can assume that the depth of the directory structure is less than or equal to 10. That might simplify your life while parsing the filename and checking various permissions. Note, you do not have to assume this. But it's ok if you do it. We won't test your code beyond the depth of 10.
   The definitions of various error conditions in treestruct.h are only for your convenience. You do not have to use or return those specific error values. We are not going to grade you based on what error values you return. As long as your function returns an error when there is an error, you are fine.

   Testing and grading: For your convenience, we have provided some test cases in userprog.c. In no way are these cases exhaustive. While grading your program we will run a number of test cases. You should make sure that your program conforms to the specifications.

Submission Guidelines

After doing make clean, change over to the directory that contains the lab5 directory, and then execute the command

turnin -c ee469 -p labX-Y lab5

It is extremely important that you do not change the directory structure. Also, while implementing the various parts, modify only those files that you are asked to. If you modify other files, your program may not compile as we are going to replace many of the other files to grade your submissions. If you want to add any new user programs, you can do that. Again, since we are going to replace the makefile, any files that you add will not compile when we grade your programs.