As long as kytos is down, please submit on Collab under the Assignments tab (top-left).

Changelog:

Until 8 April 2020, the version of fat_test.cc we distributed sometimes mislabelled “actual” and “expected” output. You can download a fixed version that should resolve this.

Your Task

  1. Download the skeleton code (link — last updated 8 April 2020) containing library function declarations, the beginnings of some testing code, and a sample Makefile.

  2. Write a C++ library to read from a FAT32 filesystem (without relying on the underlying OS supporting FAT itself), except that
    • You may assume filenames only contain 7-bit ASCII characters.
    • You may assume that the filesystem is small enough to map into memory, such as with mmap.
    • You do not need to support “Long Directory Entries” (including any filenames longer than 8 characters plus a 3 character extension, case preserving filenames, etc.)

    You will be given the contents of the FAT32 disk as a file to read from, which we call a “disk image” below.

    Your library should support a POSIX-like API (but using “file descriptors” your library tracks internally rather than ones tracked by the OS) including the following functions, which are declared in fat.h (and much exactly match these prototypes).

    Refer to the references below for precise information about the layout of the FAT filesystem, since our lecture slides gloss over some important details, like the size of FAT entries or the actual mapping from cluster numbers to locations on the disk.

    Whenever a path within the filesystem is required, paths must start with a /, and are relative to the root directory of the filesystem. For example /foo.txt refers to a file named foo.txt in the root directory of the filesystem, and /bar/quux.txt refers to a file named quux.txt in the bar directory in the root directory of the filesystem. The path / always refers to the root directory.

    • bool fat_mount(const std::string &path) – open the specified FAT disk image and use it for all subsequent fat_* calls. In this function only path is a path on the underlying OS’s filesystem instead of a path in the FAT volume. This should return true if the disk image is successfully opened, and false on any error.
    • int fat_open(const std::string &path) – open the specified file within the filesystem image previously passed to fat_mount. Directories in the path are seperated by “/”. Returns an integer file descriptor (one used by your library, not a real file descriptor on the underlying OS) that your library will accept for other calls. On failure, returns -1 instead; you must fail if you ask to open a file that does not exist. You must support opening at least 128 files at a time; after 128 files are opened you may return an error if more are opened. You may (but are not required to) also return an error when a directory is opened.
    • bool fat_close(int fd) – close the specified file descriptor returned by fat_open. Returns false on failure (e.g. file not open).
    • int fat_pread(int fd, void *buffer, int count, int offset) – copy count bytes starting with byte number offset in the previously opened file. Byte offsets start with 0, so reading with an offset of 0 and a count equal to the size of the file will read the entire file. Returns the number of bytes read, which will be less than count if the caller asks to read past the end-of-file. Returns -1 if the read fails (e.g. fd was not opened). Reading 0 bytes succesfully, such as when count is 0 or when offset is past the end of file should return 0, not -1.
    • vector<AnyDirEntry> fat_readdir(const std::string & path) – return an vector of directory entries for a directory identified by path within the filesystem image previously passed to fat_mount. AnyDirEntry is a struct declared in the supplied file fat.h. These directory entries should be exactly as found on disk. You need not filter out unused entries. In the event of an error, return an empty vector.

    You should include a Makefile that builds your library as libfat.a, like our sample Makefile will.

  3. For the checkpoint, implement any three of the following:
    • fat_readdir of a single-cluster root directory
    • fat_readdir of single-cluster directories contained within a single-cluster root directory
    • fat_readdir of a multi-cluster root directory
    • fat_readdir of single-cluster subdirectories of directories contained within a single-cluster root directory
    • fat_open of a single-cluster file in a single-cluster root directory, followed by fat_pread of the file using an offset of 0 and a size equal to its real size
    • fat_open of a single-cluster file in subdirectories of the root directory, followed by a fat_pread of the file using an offset of 0 and size equal to its real size
    • fat_open of a multi-cluster file in the root directory, followed by fat_pread of the file using an offset of 0 and a size equal to its real size
    • fat_open of a multi-cluster file in the root directory, followed by fat_pread to read an arbitrary part of the file, possibly using a size or offset that should result in the pread call returning less than the count requested
  4. Create a tar.gz archive like the one our supplied Makefile does with make archive, and submit it via [the submission site](https://kytos.cs.virginia.edu/cs4414/submit/){:target="_top"} the assignments tab on Collab.

References

  1. Refer to the FAT specification. This specification documents FAT32, FAT16, and FAT12, but you are only required to implement FAT32.

  2. https://wiki.osdev.org/FAT may be a convenient reference.

  3. Here are some disk images to test with:

Included files

  1. We include a fat.h which includes the prototypes necessary for AnyDirEntry. AnyDirEntry has the exact same layout in memory that the directory entries have on disk, so you do not need to convert field-by-field.

  2. We include a fat_internal.h which includes a struct that has the same layouts as the Bios Parameter Block to keep you from needing to worry about the details of converting that to a C struct.

  3. The structs declared in fat.h and fat_internal.h are laid out so that values in memory have the exact same layout that have one disk. This allows you to convert the bytes on disk directly to the struct rather than copying variable-by-variable.

    To make this work, in addition to setting the size of each variable in the struct, we’ve used __attribute__((packed)) to tell GCC to not add any extra space between each of the values in the struct.

  4. We include two testing programs that will be built and linked by the supplied Makefile:

    • one called fat_shell that lets you have a shell-like interface to the filesystem.

      Type help in this utility to see a brief description of the commands it offers.

      This utility, or custom test programs you write (perhaps by modifying this or our other test program), should be the primary way you check that your filesystem works correctly.

      You are welcome to read the source code to fat_shell. If you find something you want to use in your fat.cc, this is fine so long as you clearly indicate that this in your submission.

      Due to an oversight, fat_shell’s pread commands do not support counts of 0. You can fix this by editing std::vector<char> buffer(count); to std::vector<char> buffer(count <= 0 ? 1 : count);

    • one called fat_test that runs some fixed tests for the testdisk1.raw image linked above. Note that we may run different tests when grading your submission, including tests that cover functionality not exercised by this test. Some of the tests included in this are:

      • reading from the multi-cluster root directory in testdisk1.raw
      • reading the single-cluster file congrats.txt in the root directory
      • reading from the contiguous multi-cluster file gamecopy.txt in the root directory
      • reading from the noncontiguous multi-cluster file gamefrag.txt in the root directory (which contains the same text as gamecopy.txt)
      • reading from files with non-3-character extensions like foo.a
      • reading from files in subdirectories and subsubdirectories which requires traversing multi-cluster directories and directory entries that are marked as deleted

      Until 8 April 2020, the version of fat_test.cc we distributed sometimes mislabelled “actual” and “expected” output. You can download a fixed version that should resolve this.

      Look at the source code (in particular the mounted_tests() function) for complete information.

Hints

Viewing FAT filesystems for testing/debugging

  1. You may find a hex editor like bless helpful to examine the contents of a FAT32 disk image.

  2. You can mount a FAT disk image in your VM (that is, setup the disk image so you can access its files like other files in the VM) with the mount command. After creating a directory like /mnt to which to mount it, run something like

    sudo mount -o umask=0000 the-fat-disk-image.img /mnt

    to mount it. Then you can look in /mnt to view its files. The umask=0000 option ensures that the files in the filesystem are accessible to all users, which is probably simplest on a VM, but not secure on a multiuser system. Alternately, you could replace umask=0000 with uid=XXX where XXX is the user ID number printed out with the id command.

    You can then unmount it with

    sudo umount /mnt

    . If you’re worried about accidentally modifying the disk image this way, you can also mount it read-only with a command like

    sudo mount -o ro,umask=0000 the-fat-disk-image.img /mnt

Important specification details

Locating clusters by cluster number

  1. Our slides suggested that cluster 0 was located at the beginning of the disk. The way the FAT specification specifies to interpret cluster numbers in the filesystem is a bit more complex than this.

Locating the end of a list of clusters

  1. In lecture, we represent FAT entries as having the value -1 to indicate the end of a linked list of clusters. In the actual FAT format, different values are possible/likely. See the FAT specification for details.

Representing filenames

  1. In directory entries, filenames are represented using 11-character arrays which are not nul-terminated. Page 24 of the specification has examples of how filenames are mapped to array values.

  2. One way of loading a non-nul-terminated character array into a C++ string is to use the constructor that takes two arguments, a pointer to the start of the character array and a pointer to the end of the character array like:

    char some_array[11] = {'A','B','C','D','E','F','G','H','I','J','K'};
std::string array_as_string(&some_array[0], &some_array[11]);

    There are also several other constructors that could be useful, or you could work with character arrays directly instead of C++ strings, or you could copy a non-nul-terminated character array into a nul-termianted character array and then use functions that expect nul-terminated C-style strings.

Possible order of implementation

This is what I used for my reference implementation, you can do something different.

  1. Load the BPB (the “header” indicating where the FAT and root directory are) from the disk into the supplied struct.

  2. Write a function to read a particular cluster; use this to read the first cluster of the root directory (whose location is specified by information in the BPP) and implement readdir (for only the root directory, and only its first cluster).

  3. Write a function to read a particular entry from the FAT. Use this to implement readdir for when the root directory takes up multiple clusters.

  4. Write code for open and close that handles allocating and deallocating file descriptors, tracked by some global data structure. For now, don’t use a path yet, just open a file based on the number of its first cluster (and whatever else you need to track a file descriptor). The purpose of this step is just to have the code which chooses file descriptor numbers working.

  5. Write code for open that handles paths in the root directory only and fails if the filename would be in the root directory but does not exist.

  6. Write code for pread that handles reading from the first cluster of files only. You will need to modify your open code to store information needed to find this cluster.

  7. Write code for pread that handles reading from more than the first cluster of files.

  8. Modify readdir and open to traverse directories. You will probably want to create a shared utility function that looks up directory entries by pathname for both of these.

C++ tricks

Handy library functions

  1. You may find the std::toupper function in <cctype> helpful for comparing filenames.

  2. std::string has a find method and substr method you might consider using (see documentation). Or you can simply iterate through character-by-character for string opertaions.

  3. You can get the size of a file by seeking to the end and reading the location then seeking back to the beginning. You can also use the POSIX functions fstat or stat.

Reading into structs

  1. Given a char* that contains data read from disk that contains the bytes of an array of structs Foo, you can convert it into a Foo* by casting. This is how I would recommend reading the array of directory entries from a directory.

On paths with . and ..

  1. FAT directories except the root directories should contain . and .. entries that point to the itself and the parent directory, so your filesystem should handle paths like foo/../bar as equivalent to bar “for free” — except that:

    • you will need to treat these paths specially because they don’t have an extension like .txt and don’t use the extension part of the filename field of the directory entry
    • FAT uses cluster number 0 in directory entries to represent the root directory, even if it is stored in a different cluster number.

    We do not care if handle the directories /.. or /. (though a real OS would do this, even though the root directory does not contain these directory entries)