Description
1. What is required as part of this assignment?
In this assignment, you are expected to design and implement a simple file system (SFS) that can be mounted by the user under a directory in the user’s machine. You need to demonstrate the SFS working only in Linux. The SFS introduces many limitations such as restricted filename lengths, no user concept, no protection among files, no support for concurrent access, etc. You could introduce additional restrictions in your design. However, such restrictions should be reasonable to not oversimplify the implementation and should be documented in your submission. Even with the said restrictions, the file system you are implementing is highly useable for embedded applications. Here is a list of restrictions of the simple file system as specified in the handout:
-
Limited length filenames (select an upper limit such as 16)
-
Limited length file extensions (could be set to 3 – following the common extension length)
-
No subdirectories (only a single root directory – this is a severe restriction – relaxing this would enable your file system to run many applications)
-
Your file system is implemented over an emulated disk system, which is provided to you. Here is a schematic that illustrates the overall concept of the mountable simple file system.
The suggested API for SFS is given below. The API is based on C language. It is strongly suggested that you retain the functionality provided by the API if you decide to change it.
writing. The CCdisk is implemented as a file on the actual file system. Therefore, the data you store in the CCdisk is persistent across program invocations. To mimic the real disk, the CCdisk is divided into sectors of fixed size. For example, we can split the space into 1024 byte sectors. The number of sectors times the size of a sector gives the total size of the disk. In addition to holding the actual file and directory data, we need to store auxiliary data (meta data) that describes the files and directories in the disk. The structure and number of bytes spent on meta data storage depends on the file system design, which is the concern in this assignment.
On-disk data structures of the file system include a “super” block, the root directory, free block list, and i-Node table. The figure below shows a schematic of the on-disk organization of SFS.
The directory is a mapping table to convert the file name to the i-Node. Remember a file name can have an extension too. You can limit the extension to 3 characters max. The file name (without extension) could be limited as well (16 characters is suggested). A directory entry is a structure that contains two fields (at least): i-Node and file name. You could add other fields (if you find necessary). Remember the i-Node also has some attributes such as mode, etc. Depending on the number of entries you have in the directory, the directory could be spanning across multiple blocks in the disk. The i-Node pointing to the root directory is stored in the super block so we know how to access the root directory. We assume that the SFS root directory would not grow larger than the max file size we could accommodate in SFS.
In addition to the on-disk data structures, we need a set of in-memory data structures to implement the file system. The in-memory data structures improve the performance of the file system by caching the on disk information in memory. Two data structures should be used in this assignment: directory table and i-Node cache. The directory table keeps a copy of the directory block in memory. Don’t make the simplification of limiting the root directory to a single block (this would severely restrict the size of the disk
– by limiting the number of files in disk). Instead, you could either read the whole directory into the memory or have a cache for the currently used directory block. The later one could be hard to get right.
Further, when you want to create, delete, read, or write a file, first operation is to find the appropriate directory entry. Therefore, directory table is a highly accessed data structure and is a good candidate to keep in memory. Another data structure to cache in the memory is the free block list. See the class notes for different implementation strategies for the free block list.
The figure below shows the in-memory data structure and how it connects to the other components. We need at least a table that combines the open file descriptor tables (the per-process one and system-wide one) in a UNIX-like operating system. We simplify the situation because we assume that only one process is accessing a file at any given time.
When a file is opened, we create an entry in this table. The index of the newly created entry is the “file descriptor” that is return by the file opening activity. That is the return value of the sfs_fopen() is this index. The entry created in the file descriptor table has at least two pieces of important information: i-Node number and a read/write pointer. The i-Node number is the one that is the one that corresponds to the file. Remember just like there is an i-Node for the root directory, there is one i-Node associated with each file. When a file is opened that i-Node is number is recorded in this table entry. The read/write pointer is also set according to the file system operating rule. For instance, in this assignment (SFS), you are going to set the read/write pointer to the end of the file at open so that data written into the file will be appended to the file. In SFS, sfs_fseek() is a direct way of setting the read/write pointer value. The interesting problem you could be faced with is what to do when you perform a read or write after setting the read/write pointer. Specifically, if we have a single pointer then sfs_fread() would also advance the “write” pointer and similarly sfs_fwrite() would advance the “read” pointer as well. We can simplify the complexity and let it be that way. You could opt to implement the SFS with two independent read and write pointers as well. In that case, the sfs_fseek() needs to have a parameter to specify whether the read, write, or both pointers should be moved by the seek operation.
As shown in the figure below, we have in-memory data structures and on-disk data structures in a file system. The in-memory data structures are activated as soon as the file system is up and running and they are updated every time a file system operation is carried out. While designing and implementing a given file system operation you need to think of the actions that should be carried out on the in-memory and on-disk data structures. In addition to the Open File Descriptor Table, we have variety of different caches for i-Nodes, disk blocks and the root directory. Your design could implement all of them or some of them. File system performance is not a concern for this assignment – correct operation is what we need.
ECSE427/COMP310 (Revision 2) Page 4 of 7
4. More About Running the File System
We have given you a Makefile, disk emulator (C and Header), SFS test files, and FUSE wrappers. The Makefile given has five configurations. The first three use hand coded test files to test your implementation. Getting your implementing running with these three test files will get you a maximum of 95% grade. If you get it working with all five tests you can get a maximum of 110% (10% bonus). Note you should edit the EXECUTABLE value to reflect your name.
Also with the assignment package, we have given a working SFS file system that uses FUSE. You can use this file system in the Trottier Lab machines. Log into the labX-Y.cs.mcgill.ca (e.g., lab2-2) machines. Create a temporary directory in the folder that contains your SFS executable (e.g., mytemp). Now run the command
MyFilesystem_sfs mytemp
Run the ls command on mytemp and you will see nothing – it is an empty directory. That is the file system is empty. Now you copy some files over there or launch an editor like vi or emacs and create some files. You will see fs.sfs file in the folder where you ran the MyFilesystem_sfs from. This file is your file system. The data in the files you copied or created are stored over here. To check the contents of the file, load it into an editor that will let you examine binary data (e.g., emacs). To un-mount the file system, find the process that is running the file system and kill it. Sometimes killing the process will leave the mount point corrupted (i.e., you cannot run the file system on the same mount point). Use the following command to clean up the corrupted mount point.
fusermount -u mytemp
5. How is the Assignment Graded?
Part I: If you are starting this assignment few days before deadline, it is very likely that you won’t complete this assignment. The best you could do is write a very detailed pseudo code with as much detail as possible. Your pseudo code should be such that someone should be able to take that pseudo code and write a C program. You can get up to 40% of the grade. You will be judged on the quality and completeness of the pseudo code. There is no fixed convention on writing pseudo code – it should be highly readable (the more a pseudo code should be readable the harder it is to write!). Your pseudo code must be complete – capture all details that you consider important to actually create the file system (i.e., answers the questions you would have if you were coding it).
Part IIa: You have actually coded the SFS, but it does not run at all. Your code will be evaluated – you get up to 50%. Comment your code very well and make it super easy for the grader to go through it. If the grader is not happy, you lose marks.
Part IIb: Your program is working. It passes sfs_test0.c. You can expect around 60-70%.
Part IIc: Your program is passing sfs_test[0-1].c. You can expect around 70-80%.
Part IId: Your program is passing sfs_test[0-2].c. You can expect around 80-95%.
ECSE427/COMP310 (Revision 2) Page 6 of 7
We have 5% for code structure, documentation, and being easy to grade. So, if you are passing all tests up to and including sfs_test2.c you are going to get 100% with a very well documented and structured code.
Part IIe: FUSE works in addition to the rest. You get the bonus 110% (100% + 10%). If you have sfs_test2.c working flawlessly, FUSE should work, unless there are some design decisions that are creating issues for FUSE. So, this is actually a bonus!
ECSE427/COMP310 (Revision 2) Page 7 of 7
