CSS 430
Final Project: File System
Due date: See the syllabus
In this project, you will build a Unix-like file system for ThreadOS. The file system you [re]create will allow user thread programs to interface with the file system through stream-oriented files (e.g., SysLib.read() and SysLib.write()) rather than through the slower raw access to disk blocks (e.g., SysLib.rawreaad() and SysLib.rawwrite()).
Use the standard ThreadOS distribution files, except for Kernel.java, for which you should substitute Kernel_org.java. The access permissions for this file have been changed to make it readable by others, and it is recommended that you start from fresh by simply copying all the files from the ThreadOS distribution directory (uw1-320-lab.uwb.edu:/usr/apps/CSS430/ThreadOS) and then copying the Kernel_org.java file into Kernel.java.
In your work on this assignment, you will be modifying or [re]creating the following files:
The root directory ("/") is the only directory predefined by this file system and permanently available for user threads to store their files. No other directories are provided by the system nor may they be created by users dynamically. Any and all files are maintained in the "/" root directory. The file system must provide user threads with system calls that allow them to format, delete, open, close, read, write, update the seek file pointer and get the size of files.
Each user thread needs to keep track of all files it has opened. For this purpose, it should maintain a table of those open files in its TCB. This table is called a user file descriptor table. It has 32 entries. Whenever a thread opens a file, it must allocate to this file a new table entry, termed a file descriptor. Each file descriptor includes the file access mode and the reference to the corresponding file table entry. The file access mode indicates "read only", "write only", "read/write", or "append". The file table is a system-maintained table shared among all user threads, each entry of which maintains the seek pointer and the inode number of a file. Depending on the access mode, the seek pointer is set to the first or the tail of the file, and keeps track of a next position to read from and to write to the file. It is entirely possible for one thread to open the same file many times, thus having several entries in the corresponding TCB's user file descriptor table. Although each of those user file descriptor table entries refer to a different file (structure) table entry with its own seek pointer, all of them eventually points to the same inode.
The file system you create must implement the following system calls in SysLib.java (with supporting code in other files):
| Methods | Description |
| int format( int files ) | formats the disk, (i.e., Disk's data contents). The parameter files specifies the maximum number of files to be created, (i.e., the number of inodes to be allocated) in your file system. The return value is 0 on success, otherwise -1. |
| int open( String fileName, String mode ) |
opens the file specified by the fileName string in the given
mode:
|
| int read( int fd, byte buffer[] ) | reads up to buffer.length bytes from the file associated with file descriptor fd, starting at the current position of the seek pointer. If bytes remaining between the current seek pointer and the end of file are less than buffer.length, as many bytes as possible are read, putting them into the beginning of buffer. The seek pointer is incremented by the number of bytes that have been read. The return value is the number of bytes that have been read, or a negative value upon an error. |
| int write( int fd, byte buffer[] ) | writes the contents of buffer to the file associated with file descriptor fd, starting at the current position of the seek pointer. The operation may overwrite existing data in the file and/or append to the end of the file. The seek pointer is incremented by the number of bytes to have been written. The return value is the number of bytes that have been written, or a negative value upon an error. |
| int seek( int fd, int offset, int whence ) |
Updates the seek pointer corresponding to fd
depending on the value of whence and offset as follows:
|
| int close( int fd ) | closes the file corresponding to fd, commits all file transactions on this file, and unregisters fd from the user file descriptor table of the calling thread's TCB. The return value is 0 if success, otherwise -1. |
| int delete( String fileName ) | deletes the file specified by fileName. If the file is currently open, it is not deleted until the last open on it is closed, but new attempts to open it will fail. |
| int fsize( int fd ) | returns the size in bytes of the file indicated by fd. |
Unless specified otherwise, each of the above system calls returns -1 if an error occurs.
The disk block 0 is called the Superblock and used to store information about
You will need to create Superblock.java.
class Superblock {
public int totalBlocks; // the number of disk blocks
public int totalInodes; // the number of inodes
public int freeList; // the block number of the free list's head
}
The disk blocks immediately following the Superblock are Inode blocks, each containing room for 16 32-byte Inodes. Each Inode describes one file, and so the number of Inode blocks is determined by the number of files specified by a parameter to the formatting method (all blocks after the Inode blocks are data blocks that can be allocated for files). Our Inode is a simplified version of the Unix inode (as explained in our textbook). It includes 12 pointers of an index block. The first 11 of these pointers point to direct blocks. The last pointer points to an indirect block. In addition, each Inode must include
You will need to create Inode.java.
public class Inode {
private final static int iNodeSize = 32; // fix to 32 bytes
private final static int directSize = 11; // # direct pointers
public int length; // file size in bytes
public short count; // # file-table entries pointing to this
public short flag; // 0 = unused, 1 = used, ...
public short direct[] = new short[directSize]; // direct pointers
public short indirect; // a indirect pointer
Inode() { // a default constructor
length = 0;
count = 0;
flag = 1;
for ( int i = 0; i < directSize; i++ )
direct[i] = -1;
indirect = -1;
}
Inode( short iNumber ) { // retrieving inode from disk
// for you to design
}
int toDisk( short iNumber ) { // save to disk as the i-th inode
// for you to design
}
}
You will need to implement the second constructor that retrieves an existing Inode from the disk into memory. Given an Inode number - its iNumber - this constructor reads the corresponding disk block, locates the corresponding Inode information in that block, and initializes a new Inode with this information.
The system must avoid any Inode inconsistency among different user threads. There are two aspects to maintaining consistency:
The "/" root directory maintains each file in a different directory entry that contains its file name (in maximum 30 characters = in max. 60 bytes in Java) and the corresponding Inode number. The directory receives the maximum number of Inodes to be created, (i.e., thus the max. number of files to be created) and keeps track of which Inode numbers (iNumbers) are in use. Since the directory itself is considered as a file, its contents are maintained by an Inode, specifically saying Inode 0. This can be located in the first 32 bytes of the disk block 1.
Upon a boot, the file system instantiates the following Directory class as the root directory through its constructor, reads the file from the disk that can be found at Inode 0 (the first 32 bytes of the disk block 1), and initializes the Directory instance with the file contents. Upon shutdown, the file system must write back the Directory information onto the disk. The bytes2directory() method will initialize the Directory instance with a byte array read from the disk and the directory2bytes() method converts the Directory instance into a byte array that can be written back to the disk.
You will need to create Directory.java.
public class Directory {
private static int maxChars = 30; // max characters of each file name
// Directory entries
private int fsizes[]; // each element stores a different file size.
private char fnames[][]; // each element stores a different file name.
public Directory( int maxInumber ) { // directory constructor
fsizes = new int[maxInumber]; // maxInumber = max files
for ( int i = 0; i < maxInumber; i++ )
fsizes[i] = 0; // all file size initialized to 0
fnames = new char[maxInumber][maxChars];
String root = "/"; // entry (inode) 0 is "/"
fsizes[0] = root.length(); // fsize[0] is the size of "/".
root.getChars( 0, fsizes[0], fnames[0], 0 ); // fnames[0] includes "/"
}
public int bytes2directory( byte data[] ) {
// assumes data[] received directory information from disk
// initializes the Directory instance with this data[]
}
public byte[] directory2bytes( ) {
// converts Directory information into a plain byte array and returns it
// this byte array will be written back to disk
// note: only meaningful directory information should be converted
// into bytes.
}
public short ialloc( String filename ) {
// filename is the one of a file to be created.
// allocates a new inode number for this filename
}
public boolean ifree( short iNumber ) {
// deallocates this inumber (inode number)
// the corresponding file will be deleted.
}
public short namei( String filename ) {
// returns the inumber corresponding to this filename
}
}
The FileSystem maintains a system-wide FileTable shared among all user threads. A user thread opens a filename in a specified mode (via SysLib.open()), using the following sequence:
[Note: FileTableEntry.java already exists; you will not have to make any changes to this class definition.]
public class FileTableEntry { // Each table entry should have
public int seekPtr; // a file seek pointer
public final Inode inode; // a reference to its inode
public final short iNumber; // this inode number
public int count; // # threads sharing this entry
public final String mode; // "r", "w", "w+", or "a"
public FileTableEntry ( Inode i, short inumber, String m ) {
seekPtr = 0; // the seek pointer is set to the file top
inode = i;
iNumber = inumber;
count = 1; // at least on thread is using this entry
mode = m; // once access mode is set, it never changes
if ( mode.compareTo( "a" ) == 0 ) // if mode is append,
seekPtr = inode.length; // seekPtr points to the end of file
}
}
You will need to create FileTable.java. The system-wide open FileTable class is defined as follows:
public class FileTable {
private Vector table; // the actual entity of this file table
private Directory dir; // the root directory
public FileTable( Directory directory ) { // constructor
table = new Vector(); // instantiate a file table
dir = directory; // receive a reference to the Director
} // from the file system
// major public methods
public synchronized FileTableEntry falloc( String filename, String mode ) {
// allocate a new file table entry for this file name
// allocate/retrieve and register the corresponding inode using dir
// increment this inode's count
// immediately write back this inode to the disk
// return a reference to this file table entry
}
public synchronized boolean ffree( FileTableEntry e ) {
// receive a file table entry reference
// save the corresponding inode to the disk
// free this file table entry.
// return true if this file table entry found in my table
}
public synchronized boolean fempty() {
return table.isEmpty(); // return if table is empty
} // should be called before starting a format
}
Each user thread maintains a user file descriptor table in its own TCB. Every time it opens a file, it allocates a new file table entry (ftEnt) including a reference to the corresponding FileTableEntry in the system-wide open FileTable. Whenever a thread spawns a new child thread, it passes a copy of its TCB to this child which thus has a copy of its parent's user file descriptor table. This in turn means the both the parent and the child refer to the same FileTableEntry set in the system-wide open FileTable and eventually share the same files.
The user file descriptor table entries can either be copied as part of the TCB constructor or immediately after a new TCB is created (in Scheduler.addThread()).
Here is the distribution version of TCB.java for reference:
public class TCB {
private Thread thread = null;
private int tid = 0;
private int pid = 0;
private boolean terminate = false;
// User file descriptor table:
// each entry pointing to a file table entry
public FileTableEntry[] ftEnt = null;
public TCB( Thread newThread, int myTid, int parentTid ) {
thread = newThread;
tid = myTid;
pid = parentTid;
terminated = false;
// The following code is added for the file system
ftEnt = new FileTableEntry[32];
System.err.println( "threadOS: a new thread "
+ "(thread=" + thread
+ " tid=" + tid
+ " pid=" + pid + ")");
}
Note that the file descriptors 0, 1, and 2 are reserved for the
standard input, standard output and standard error,
and thus those entires must remain null.
Design and implement the file system in ThreadOS as specified above. This will involve creating or modifying the following files:
Run Test5.java that is found in the ThreadOS directory. This test program will test the functionality of every system listed above and check the data consistency and fault tolerance of your file system:
[Note: Test5.java subject to change]
[Note: Requirements for submission subject to change]
This FAQ could answer some of your questions about this assignment. Please check there first before emailing the professor :-).
A set of CSS430 Final Project slides [PDF] offers a number of diagrams and code snippets that you may find helpful. The source PPT file is not available, so please note the following corrections: