On Linux, /dev/zero is a special file that provides as many \0 as are read from it. The dd command performs low-level copying of raw data. Therefore, you can use it to generate an arbitrary-size file full of zeros.

For example, to create a 256KB empty file named fat32.disk:

Read man dd for its usage. You will use this file as the disk image.

You can use the mkfs.fat command to create a FAT32 file system. The most basic usage is:

(You can ignore the warning of not enough clusters.)

You can specify a variety of options. For example:

Here are the meanings of each option:

• -F: type of FAT (FAT12, FAT16, or FAT32).
• -f: number of FATs.
• -S: number of bytes per sector.
• -s: number of sectors per cluster.
• -R: number of reserved sectors.

The fsck.fat command can check and repair FAT file systems. You can invoke it with -v to see the FAT details. For example:

You can see that there are 2 FATs, 512 bytes per sector, 512 bytes per cluster, and 32 reserved sectors. These numbers match our specified options in Step 2. You can try different options yourself.

You can use the mount command to mount a file system to a mount point. The mount point can be any empty directory. For example, you can create one at /mnt/disk:

Then, you can mount fat32.disk at that mount point:

After the file system is mounted, you can do whatever you like on it, such as creating files, editing files, or deleting files. In order to avoid the hassle of having long filenames in your directory entries, it is recommended that you use only 8.3 filenames, which means:

• The filename contains at most eight characters, followed optionally by a . and at most three more characters.
• The filename contains only uppercase letters, numbers, and the following special characters: ! # $ % & ' ( ) - @ ^ _ ` { } ~.

For example, you can create a file named HELLO.TXT:

For the purpose of this lab, after you write anything to the disk, make sure to flush the file system cache using the sync command:

(Otherwise, if you create a file and immediately delete it, the file may not be written to the disk at all and is unrecoverable.)

When you finish playing with the file system, you can unmount it:

You can examine the file system using the xxd command. You can specify a range using the -s (starting offset) and -l (length) options.

For example, to examine the root directory:

(It’s normal that the bytes containing timestamps are different from the example above.)

To examine the contents of HELLO.TXT:

Note that the offsets may vary depending on how the file system is formatted.

There are several ways to invoke your nyufile program. Here is its usage:

The first argument is the filename of the disk image. After that, the options can be one of the following:

• -i
• -l
• -r filename
• -r filename -s sha1
• -R filename -s sha1

You need to check if the command-line arguments are valid. If not, your program should print the above usage information verbatim and exit.

If your nyufile program is invoked with option -i, it should print the following information about the FAT32 file system:

• Number of FATs;
• Number of bytes per sector;
• Number of sectors per cluster;
• Number of reserved sectors.

Your output should be in the following format:

For all milestones, you can assume that nyufile is invoked while the disk is unmounted.

If your nyufile program is invoked with option -l, it should list all valid entries in the root directory with the following information:

• Filename. Similar to /bin/ls -p, if the entry is a directory, you should append a / indicator.
• File size if the entry is a file (not a directory).
• Starting cluster if the entry is not an empty file.

You should also print the total number of entries at the end. Your output should be in the following format:

Here are a few assumptions:

• You should not list entries marked as deleted.
• You don’t need to print the details inside subdirectories.
• For all milestones, there will be no long filename (LFN) entries. (If you have accidentally created LFN entries when you test your program, don’t worry. You can just skip the LFN entries and print only the 8.3 filename entries.)
• Any file or directory, including the root directory, may span more than one cluster.
• There may be empty files.

If your nyufile program is invoked with option -r filename, it should recover the deleted file with the specified name. The workflow is better illustrated through an example:

For all milestones, you only need to recover regular files (including empty files, but not directory files) in the root directory. When the file is successfully recovered, your program should print filename: successfully recovered (replace filename with the actual file name).

For all milestones, you can assume that no other files or directories are created or modified since the deletion of the target file. However, multiple files may be deleted.

Besides, for all milestones, you don’t need to update the FSINFO structure because most operating systems don’t care about it.

Here are a few assumptions specifically for Milestone 4:

• The size of the deleted file is no more than the size of a cluster.
• At most one deleted directory entry matches the given filename. If no such entry exists, your program should print filename: file not found (replace filename with the actual file name).

Now, you will recover a file that is larger than one cluster. Nevertheless, for Milestone 5, you can assume that such a file is allocated contiguously. You can continue to assume that at most one deleted directory entry matches the given filename. If no such entry exists, your program should print filename: file not found (replace filename with the actual file name).

In Milestones 4 and 5, you assumed that at most one deleted directory entry matches the given filename. However, multiple files whose names differ only in the first character would end up having the same name when deleted. Therefore, you may encounter more than one deleted directory entry matching the given filename. When that happens, your program should print filename: multiple candidates found (replace filename with the actual file name) and abort.

This scenario is illustrated in the following example:

To solve the aforementioned ambiguity, the user can provide a SHA-1 hash via command-line option -s sha1 to help identify which deleted directory entry should be the target file.

In short, a SHA-1 hash is a 160-bit fingerprint of a file, often represented as 40 hexadecimal digits. For the purpose of this lab, you can assume that identical files always have the same SHA-1 hash, and different files always have vastly different SHA-1 hashes. Therefore, even if multiple candidates are found during recovery, at most one will match the given SHA-1 hash.

This scenario is illustrated in the following example:

When the file is successfully recovered with SHA-1, your program should print filename: successfully recovered with SHA-1 (replace filename with the actual file name).

Note that you can use the sha1sum command to compute the SHA-1 hash of a file:

Also note that it is possible that the file is empty or occupies only one cluster. The SHA-1 hash for an empty file is da39a3ee5e6b4b0d3255bfef95601890afd80709.

If no such file matches the given SHA-1 hash, your program should print filename: file not found (replace filename with the actual file name). For example:

The OpenSSL library provides a function SHA1(), which computes the SHA-1 hash of d[0...n-1] and stores the result in md[0...SHA_DIGEST_LENGTH-1]:

You need to add the linker option -lcrypto to link with the OpenSSL library.

Finally, the clusters of a file are no longer assumed to be contiguous. You have to try every permutation of unallocated clusters on the file system in order to find the one that matches the SHA-1 hash.

The command-line option is -R filename -s sha1. The SHA-1 hash must be given.

Note that it is possible that the file is empty or occupies only one cluster. If so, -R behaves the same as -r, as described in Milestone 7.

For Milestone 8, you can assume that the entire file is within the first 20 clusters, and the file content occupies no more than 5 clusters, so a brute-force search is feasible.

If you cannot find a file that matches the given SHA-1 hash, your program should print filename: file not found (replace filename with the actual file name).

This lab requires significant programming effort. Therefore, start as early as possible! Don’t wait until the last week.

• Before you start, use xxd to examine the disk image to get an idea of the FAT32 layout. Keep a backup of the hexdump.
• After you create a file or delete a file, use xxd to compare the hexdump of the disk image against your backup to see what has changed.
• You can also use xxd -r to convert a hexdump back to a binary file. You can use it to “hack” a disk image. In this way, you can try recovering a file manually before writing a program to do it. You can also create a non-contiguously allocated file artificially for testing in this way.
• Always umount before using xxd or running your nyufile program.
• When updating FAT, remember to update all FATs.
• Using mmap() to access the disk image is more convenient than read() or fread(). You may need to open the disk image with O_RDWR and map it with PROT_READ | PROT_WRITE and MAP_SHARED in order to update the underlying file. Once you have mapped your disk image, you can cast any address to the FAT32 data structure type, such as (DirEntry *)(mapped_address + 0x5000). You can also cast the FAT to int[] for easy access.
• The milestones have diminishing returns. Easier milestones are worth more points. Make sure you get them right before trying to tackle the harder ones.

This lab has borrowed some ideas from Dr. T. Y. Wong.