Overview

For the final project, you will implement a virtual file system to work with your minithreads package. We have provided a block-based disk interface in disk.h, which simulates a disk by translating block reads and writes to accesses to a single file.

You should implement a hierarchical, Unix-like file system on top of the disk emulator that supports the following operations:

minifile_t minifile_creat(char *filename);
minifile_t minifile_open(char *filename, char *mode);
int minifile_read(minifile_t file, char *data, int maxlen);
int minifile_write(minifile_t file, char *data, int len);
int minifile_close(minifile_t file);
int minifile_unlink(char *filename);
int minifile_mkdir(char *dirname);
int minifile_rmdir(char *dirname);
int minifile_stat(char *path);
int minifile_cd(char *path);
char **minifile_ls(char *path);
char* minifile_pwd(void);

To get an idea of what these functions should do, look them up (omitting the "minifile_" prefix) via man pages on a Unix system. The only exception is that our minifile_open takes arguments like the fopen call, instead of open. Don't worry about reporting detailed error codes when something goes wrong, returning -1 from the function (or some other appropriate error value) is good enough. Your file system should support variable-sized files via a Unix-like inode mechanism, and reuse of blocks from unlinked (deleted) files. It is vital that your file system has concurrency control, so that it can cope with simultaneous accesses by multiple threads.

If you stick to the interface above, you should be able to compile and run the shell program included with this version of the code. You should then be able to create files and directories from the command line.

The Details

Disk simulator

The disk simulator is relatively straightforward. To initialize the disk, use the disk_initialize() function. You can specify the disk initialization behavior by changing the following global variables: use_existing_disk, disk_name, disk_flags and disk_size. To create a disk, set use_existing_disk to 0, and specify the disk_name, disk_size and disk_flags. To start an existing disk, set use_existing_disk to 1 and specify the disk_name. Upon starting up the disk, disk_size and disk_flags will be set appropriately.

Since you are not asked to support mount points, there should be only one file-system in your implementation. This unique file-system should reside on a virtual disk that uses the file MINIFILESYSTEM in the current directory. Make sure you write a C program, called mkfs.exe, that creates an empty file-system in this virtual disk. This initial file-system created by mkfs.exe should contain only one directory (the root directory) with no entries.

Using the disk

Before sending requests to the disk, the disk must already have been initialized using disk_initialize(), and the interrupt handler installed. Once these steps have been completed, disk requests can be issued through the disk_send_request() function. The format of the requests is shown in disk.h. When requests complete, the disk controller signals the completion by raising an interrupt. As with previous assignments, you need to write an interrupt handler that will handle these interrupts appropriately.

Recall from the course discussion that the disk controller may reorder your requests in any arbitrary order. In fact, an efficient controller will reorder requests quite aggressively. Consequently, if you have a series of blocks that need to be written with a well-defined order (e.g. block A before B before C), then you must, in your file-system code, make sure that you do not issue request B before the request for A has been completed.

Disk handler implementation

The disk driver code (disk.[ch]) sends a disk interrupt after a read/write request is processed. The disk interrupt is processed by the disk handler that receives an argument of disk_interrupt_arg_t type. The disk handler is installed using the install_disk_handler function.

Relation to other minithread components

Note that not all of the functions are file operations. For instance, the concept of the "current working directory" is not a global abstraction that applies to the filesystem, but a piece of local state kept with each process (minithread). Similarly, minifile_pwd() returns the path to the current working directory associated with the calling thread. Your file system should NOT have any such state as global variables shared across independent minithreads.

Concurrency

Applications may access the file system concurrently. For this project, you will implement UNIX semantics for concurrent accesses. You will allow multiple applications to open the same file for writing concurrently and to issue concurrent write requests to the same file. You will invoke the end-to-end argument and say that multiple applications performing concurrent accesses to the disk need to coordinate among themselves if they want to retain application-level guarantees of atomicity, and that the FS is not the appropriate subsystem in which to enforce synchronization constraints. Therefore, your FS can leave aside any guarantee of integrity of file contents when the file is accessed concurrently. Specifically, if thread A writes blocks 0 with data A0 and block 1 with data A1, and thread B writes the same blocks with data B0 and B1, the file may end up with "A0, A1", or "A0, B1" or "B0, A1" or "B0, B1", all depending on who performed the last write.

This approach is quite simple to implement. But you must ensure that your code guarantees the integrity of the filesystem. For instance, concurrent accesses should not cause your FS to generate orphaned data blocks (as would happen when a naive write() implementation that overwrites an existing inode is used concurrently by multiple threads).

Similarly, your FS must define a reasonable set of semantics when multiple applications concurrently access the file and delete or rename it at the same time. For example, suppose a thread is writing to a file when another thread unlinks that file. Once again, you will follow UNIX semantics in your implementation. The file is made unreachable (i.e. it is taken out of the directory hierarchy) at the time the unlink is issued. However, the inode and the file's data blocks are not placed back on the free list until all applications that have an open file descriptor to that file close their descriptors. This permits applications to continue working on a file which has been deleted, and permits concurrent applications to make forward progress. It can be implemented with a simple reference count of open handles to each file. Make sure that the last person who closes the deleted file places the (now-deleted) blocks back on the free list. Any changes made to the file are lost if the file got deleted while it was being modified.