Part I: Due by 11:59PM EST on Saturday, November 10, 2018
Part II: Due by 11:59PM EST on Saturday, November 24, 2018
Part III: Due by 11:59PM EST on Saturday, December 8, 2018
Monday, November 12 — Part III - Initial version
Sunday, November 4 — Part II - Initial version
Tuesday, October 30 — Part I - Add unused area to root block to clarify its layout a little bit.
Saturday, October 27 — Part I - Initial version
In this project, you will take a deeper look at how filesystems are designed and implemented in modern computer systems. This project will focus on the creation of a filesystem driver to add support to Linux for reading and writing to a filesystem within a disk image file. However, before the filesystem driver itself can be implemented, this project will require the creation of a tool to format the filesystem.
This project will involve creating a new filesystem driver, which we will call VMUFS. This new filesystem driver will be implemented using the FUSE framework, which allows the creation of filesystem drivers entirely in user-space. Also, a tool to create a disk image file of a fixed size and to format it as a valid VMUFS driver will be required in this project. There is a possibility for extra credit on this assignment if an in-kernel filesystem driver (as a loadable kernel module) is developed in addition to the FUSE-based filesystem module and the formatting tool.
Before you begin on Parts I and II of the project, you will have to create the GitHub repository for that part (there will be three parts in total, but Parts II and III will share their repositories). The links to create each repository will be posted on the course Piazza page, as with previous projects. Unlike previous projects, this project will not require you to make any changes directly in the Linux kernel — the filesystem driver you develop in Part II and III will be done as a user-space program using the FUSE framework. However, you will still be basing the code on the same version of the kernel used in previous projects. This will be covered in more detail in Part II of the assignment.
To begin, we recommend that you create an appropriate amount of space on your VM to aid in development. At this point, you are unlikely to have received a final grade on Project 1, so we do not recommend deleting your Project 1 code from your VM, however, it would be very helpful to run the make clean command in your /usr/src/project1 directory to remove all the built components of the kernel for that version. You may wish to keep the /usr/src/vanilla-project1 directory in case you attempt the extra credit in Parts II and III, as the in-kernel filesystem module will need to be based on the clean 4.18.6 kernel that you have been using as a base for the previous projects.
One of the nice things about using GitHub for submitting assignments is that it lends itself nicely to an incremental development process. As they say, Rome wasn't built overnight — nor is most software. Part of our goal in using GitHub for assignment submission is to give all of the students in the class experience with using an source control system for incremental development.
You are encouraged in this project to plan out an incremental development process for yourself — one that works for you. There is no one-size-fits-all approach here. One suggested option is to break the assignment down into steps and implement things as you go. For instance, the locking/thread safety portions of the assignment can be easily added after the main functionality is implemented, in most cases. You are also encouraged to seek out the review of your TAs to determine whether an approach might be feasible.
You should not attempt to complete this entire project in one sitting. Also, we don't want you all waiting until the last minute to even start on the assignment. Doing either of these will usually lead to students getting poor grades on the assignment. To this end, we are requiring you to make at least 8 non-trivial commits to your GitHub repository for the assignment. These eight commits must be made on different dates and at least four must be completed by the due date for Part II of the project. You may make more than eight commits during the timeline of the project — eight is only the minimum that will be required for full credit.
A non-trivial commit is defined for this assignment as one that meets all of these requirements:
Failure to adhere to these requirments will result in a significant deduction in your score for the assignment. This deduction will be applied after the rest of your score is calculated, much like a deduction for turning in the assigment with a late penalty.
The filesystem you will design in this project will follow a very specific format, to ensure that all students should be able to design code that is interoperable with each other. That filesystem is described below.
The VMUFS filesystem is a simple file allocation table based filesystem with a fixed volume size of 128KiB (256 total blocks of 512 bytes each), a single-level directory structure, and 16-bit entries in its FAT. This filesystem was used for the memory cards on the Sega Dreamcast video game console (which were called Visual Memory Units or VMUs).
A VMUFS filesystem consists of a user data area (200 blocks), a normally unused area (41 blocks), the single-level directory (13 blocks), the file allocation table (1 block), and a root block (1 block). The user data area is used for storing files on the filesystem, and has no specific format. The unused area should always be initialized with 0 bytes and should never be used. The directory, file allocation table, and root blocks each have a specific format, which will be described below. All multi-byte values are stored in little endian byte ordering.
The VMUFS root block is always stored as the last block in the volume. As all VMUFS volumes are 128KiB in size, this is block 255 in the volume (assuming that the first block is block 0). The root block is responsible for directing the filesystem driver to various important pieces of data in the volume and recording some basic information that is set when the volume is formatted. The format of the root block is described below.
| Offset | Size (bytes) |
Description |
|---|---|---|
| 0x000 | 16 | Filesystem Signature - Set all bytes to 0x55 |
| 0x010 | 1 | Set to 1 to mark the next four bytes as a color value used for the filesystem on a memory card. To use a default color code instead, set to 0. |
| 0x011 | 1 | Color code blue component |
| 0x012 | 1 | Color code green component |
| 0x013 | 1 | Color code red component |
| 0x014 | 1 | Color code alpha component (255 = opaque, 0 = completely transparent) |
| 0x015 | 27 | Unused, set to 0 |
| 0x030 | 8 | Filesystem creation timestamp (Binary Coded Decimal format) |
| 0x038 | 14 | Unused, set all bytes to 0 |
| 0x046 | 2 | Starting block of the FAT, set to 0x00FE (254) |
| 0x048 | 2 | Size of the FAT, in blocks; set to 0x0001 |
| 0x04A | 2 | Last block of the directory, set to 0x00FD (253) |
| 0x04C | 2 | Size of the directory, in blocks; set to 0x000D (13) |
| 0x04E | 2 | Icon for the filesystem, valid values are 0-130 |
| 0x050 | 2 | Number of user blocks, set to 0x00C8 (200) |
| 0x052 | 430 | Unused, set all bytes to 0 |
Timestamps (both in the root block and in the directory) on VMUFS are stored in a format known as Binary-Coded Decimal (BCD, for short). In Binary-Coded Decimal, each byte represents two digits, with 4 bits for each digit. If you look at a BCD number in hexadecimal (and ignore any indication it is in hex), it will conveniently have the decimal value of the number. This is easiest to demonstrate with a few examples:
| Decimal Value | Binary (BCD) | Hexadecimal (BCD) |
| 20 | 0010 0000 | 0x20 |
| 18 | 0001 1000 | 0x18 |
| 31 | 0011 0001 | 0x31 |
| 5 | 0000 0101 | 0x05 |
Timestamps in VMUFS are always stored in the following order:
The VMUFS file allocation table is an array of 16 bit values. The entire FAT fits in one block of 512 bytes on the volume, and has one entry for every block on the volume (including the block it resides in). For an overview of how the FAT scheme works for allocation, see Chapter 12 of the textbook for the course. The basics of the file allocation table scheme used in VMUFS are as follows:
The directory is treated as a special file that is allocated starting at block 253 of the volume, with each subsequent block preceeding that. That is to say that the second block of the directory is allocated at block 252, the third at block 251, and so on until the thirteenth block which is allocated at block 241 of the volume. The directory appears in the FAT as a normal file chain, which has been set up as described above.
At format time, this means that entries 0-240 in the FAT should be set to 0xFFFC, entry 241 should be set to 0xFFFA, entries 242-253 should be set to their entry number minus 1, and entries 254 and 255 should be set to 0xFFFA.
Each file on a VMUFS filesystem has an entry in the directory structure that describes some basic information about the file. Each entry in the directory is 32 bytes long. With 13 blocks of 512 bytes allocated for the directory at formatting time, this gives us a maximum of 200 possible files on each filesystem. Files are always allocated in block size increments, like any sensible filesystem, so the limit of 200 possible files allows for the maximum number of files that we could have on a filesystem anyway (since there are only 200 blocks available for files). Each entry in the directory follows the format described below:
| Offset | Size (bytes) |
Description |
|---|---|---|
| 0x00 | 1 | File Type (0x00 = unused, 0x33 = data file, 0xcc = program) |
| 0x01 | 1 | Use copy protection? (0x00 = no, 0xff = yes) |
| 0x02 | 2 | Location of the first block of the file |
| 0x04 | 12 | Filename (ASCII string, fill unused bytes with zero bytes) |
| 0x10 | 8 | BCD timestamp of the last write to the file |
| 0x18 | 2 | File size, in blocks |
| 0x1A | 2 | Header offset within file (set to 0) |
| 0x1C | 4 | Unused, set to 0 |
Part I of this project is to create the user-space program to create a new VMUFS filesystem. The GitHub repository you create for this part of the project will be blank. You are responsible for writing all the code for the formatting tool. You must also include a Makefile that can be used to build your tool simply by running make.
Your tool must work as follows:
If you wish to implement support for passing additional parameters to your tool (for instance, to specify a color code or icon), you may do so. Please document any additional flags you accept in a README. However, if you add additional flags, they must be optional! We will be running your program as "mkvmufs filename.img" and not passing any additional arguments. Your program must be named mkvmufs, and must have a Makefile that builds it.
In Part II of the project, you will begin to develop your filesystem driver to access files stored on a VMUFS image. In this part of the assignment, you will be building a limited version of the driver which only supports a few basic operations for reading files on an image.
Before you begin, you will need to install a few dependencies in your VM that will be needed for developing your VMUFS driver. Specifically, you will need the FUSE libraries (and development versions thereof). You can install these prerequisites by running the following commands as root:
apt-get update apt-get install fuse libfuse2 libfuse-dev
For this portion of the project, you are only required to build a driver that can read files stored on a VMUFS image. You are not required to implement any write support in Part II of the assignment. A basic read-only filesystem driver in FUSE has only a few functions that must be implemented for the driver to function. Specifically, you will need to implement the following functions of the fuse_operations structure in your filesystem: getattr, readdir, open, read. It is highly suggested that you look to the examples linked to in the resources (the "hello_ll" example should be of help to show the basics of how things work, for instance). You may find it useful to implement support for additional FUSE functions in your read-only driver — the ones listed above are only the absolute minimum.
Your filesystem driver should accept two arguments. The first argument will be the name of the image file to read from and the second argument will be the mount point to mount the filesystem at. Your filesystem driver program must be named "vmufs". You must provide a Makefile with which your driver can be built. You may write your filesystem driver in C or C++, as you see fit, however you may not require any additional external libraries to build/use your driver beyond FUSE, its dependencies, and the standard C or C++ library (as appropriate).
Make sure when submitting your code for Part II of the project that you use the new repository called "yourGitHubUsername-project2" for your code. Please remember to provide your source code files; a Makefile with which we can build your FUSE driver; and a README describing your approach to this portion of the assignment, any references you used outside of the ones provided on this assignment, and any other information you would like the TA grading your assignment to know about. Please also use the git tag functionality to tag your final submission for Part II with a tag called "part2" (hint: you had to use the tag functionality in Homework 1 as well). This tag does not have to contain any extra credit code (so do not update it if you submit the extra credit later).
For extra credit (up to 10%), you may also choose to provide an in-kernel version of your read-only VMUFS driver as a loadable kernel module. Keep in mind that when building code for the kernel, you are a lot more limited in what you can do and what functions you have available (remember, the kernel does not allow C++ code, for instance). The kernel module you build must be able to be built on the 4.18.6 version of the kernel (from your vanilla-project1, for instance).
Refer to the "Notes on Extra Credit" section below (under the submission instructions for some general notes about extra credit on this assignment.
If you wish to implement the extra credit for this assignment, please make a "kernel" directory in your project2 repository and put your kernel module source code in it and a Makefile with which to build the kernel module. You must also inform the TA that you have attempted the extra credit by mentioning this in your README file.
As this is extra credit on the assignment, you should expect the in-kernel driver to require a significant amount of effort. The TAs (and instructors) will offer no help on the extra credit portions of this assignment — you are on your own to figure it out. Please do not ask any questions specifically about the extra credit on Piazza.
You may work on the extra credit for Part II up until the final due date for Part III of the assignment. The TAs will not be checking for it until that time.
In Part III of this project, your task is to extend the driver from Part II to support writing to the filesystem. This includes adding support for all of the following to your filesystem driver:
Your implementation of Part III of this assignment should directly extend your Part II driver. You will be using the same Git repository for Part III as you did for Part II (so there is no new link on Piazza to create a new repository).
Upon completion of Part III of the project, your filesystem driver should work much like any other filesystem in your VM. That is to say that you should be able to do things like listing the directory with ls; creating a new file with touch or any other tool that creates files; editing text files with tools like nano, vi, or emacs; deleting files with rm; moving files with mv; and so on.
In this part of the project, you will be expected to explore the FUSE documentation, examples, and code yourself in order to ascertain the functionality that you must implement. Keep in mind that functionality that is not useful for VMUFS (such as creating or removing directories) may still require a small function to be written to signal that the operations are not allowed on the filesystem and return the appropriate error codes.
Once you have completed Part III of the project, please be sure to add a new tag to your git repository called "part3" containing all of your changes to create the new functionality.
Like with Part II, upon completion of your FUSE driver for Part III, you may attempt to also add a Read/Write driver for VMUFS as a kernel module. The same basic rules from Part II apply to this extra credit as well. Completing the writing portion of the extra credit kernel driver will allow you to earn up to 10% extra credit on this assignment. Thus, completing both the extra credit for Part II and for Part III can allow you to earn up to a total of 20% extra credit on this assignment. Please note that this extra credit applies to the grade on this project — that is to say that you can earn up to a 120% on this assignment if you complete both of the extra credit parts.
Submission of this project largely follows the same procedures as for previous projects, with the main difference being that you will have two repositories to commit to. Please be sure to include a README file with each of your repositories.
Details on what can be done for extra credit on this project will be included in the Part II and Part III sections of the project as they are posted, however the following will apply to the extra credit.
Extra credit portions of the assignment cannot be used to make up for portions of the assignment that are completely unimplemented. That is to say, extra credit is for boosting the final grade of an assignment where a reasonable attempt was made to complete all the other features. This is not to say that everything must be implemented pefectly, but if a submission does not include the mkvmufs tool (for instance), then extra credit cannot be used to make up for that portion of the assignment. You must make a reasonable attempt at all three parts of the assignment to qualify for any extra credit!
The TAs judgements on what constitutes a reasonable attempt to implement the filesystem features will be considered final.
Below is a list of references that you may find useful in your quest to complete this project:
Any of the following will cause a significant point loss on this project.
Please do not make us take off points for any of these things!
Last modified Tuesday, 01-Sep-2020 18:43:30 EDT