USFAT is a fictional file system invented just for CS2106 ! It draws inspirations from the basic FAT based file allocation scheme and the MS-DOS FAT16 file system. Your tasks in this lab is to understand and provide functionalities that interact with the underlying USFAT file system.
Note that a “logical block” is the same size as a “sector” in USFAT and we use the two terms interchangeably.
There are a total of 129 sectors (with absolute index 0 to 128) and each sector is 256 bytes. So, a typical USFAT file system is 129 * 256 = 33,024 bytes in size. The FAT table occupies one sector and is located at sector 0. All remaining sectors (128) are used for data storage.
Each FAT entry is 2 bytes in size, i.e. the FAT contains 256 / 2 = 128 entries. Note that the FAT index refers only to blocks in the file data region. For ease of reference (and coding), we will use data sector number to indicate sectors in the data region. For example, the status of data sector 2 can be found in FAT, but the actual storage on the “hard disk” is at sector 3. So, pay attention to whether you are using data sector number of the absolute sector number during coding to avoid “off-by-one” errors.
Each FAT entry can contain one of the following values:
|0xFFFA||The sector is free.|
|0xFFF7||The sector is bad (i.e. not working, don’t store any content here).|
|0xFFFF||The sector is the END of a linked sector chain.|
|0x0000 to 0x007F||The sector leads to the indicated sector as part of a linked sector chain.|
From the FAT printout above, we can see that the data sector 0x0000 is free; the data sectors 0x004a0x004b0x004c (end) is part of a linked sector chain, etc.
Under USFAT, directory and file both use the file data sectors to store information. For a directory, the data sector stores directory entries, which contains information about files under that directory. For a file, the data sector stores the actual file content.
For simplicity, the USFAT media provided in this lab has the following limitations:
- There is only one directory, the Root Directory. It is located at data sector 5.
- Directory uses only 1 sector for its directory entries, which place an upper limit on the number of files it can store.
- Your code only need to work with these limitations in place.
- Note: These limits are imposed to simplify the exercises, the design of the USFAT is much more general / flexible.
Each of the directory entry in a directory’s data sector occupies 32 bytes and has the following layout:
The name uses the old “8+3” format, where the file name is 8 characters long and the extension takes up 3 characters, e.g., a file with name “sample.cc” is stored as:
Note that the filename is right aligned to the “.” while the extension is left aligned.
The “.” itself is not stored. We use ‘’ represents a space, i.e. ‘ ‘.
The attribute is a single byte (8 bits):
For our exercises, you can assume that all files have an attribute 0x01, i.e. readable, not hidden, not a system file and not a directory.
Since each directory entry is 32 bytes and the directory in USFAT can utilize only 1 sector for directory entries, this gives us 256 bytes / 32 bytes = 8 files under a directory at most.
There are a number of “disk image” files provided for this lab, e.g. 4files.img, empty.img, etc. Each of the file represents a complete USFAT file system. You can imagine they represent simulated storage media like a hard disk, etc.
A large number of library calls are provided for you to focus on “high level” file system functionalities. In the common/ directory, take a look at the USFAT.h header files which defines all important system parameters and the available library calls. Essentially, “low level” functionalities that deals with reading / write information from / to the media, e.g. sector / FAT reading / writing, etc are available for use.
In addition, a “debug inspector” program, known as USFATI (USFAT Insepctor) is also available so that you can view the raw content on a USFAT media easily. Instructions to setup the inspector etc is given in Section 2.
There is one additional folder common/ with the following files:
|USFAT.h||USFAT header file with all key definitions and declarations.|
|USFAT_Util.c||Implementation of all USFAT library functions.|
|USFAT_Insepct.c||The debug inspector utility program. Compiles into the “USFATI” executable.|
|Various *.img||Backup copies of all USFAT disk images. In exercise 3, your program will modify the USFAT disk image, so if you ever need to “reset” the disk images, copy the backup over.|
|makefile||For compiling the USFATI debug inspector as mentioned above. reset.sh: A simple script file to copy the backup images to the exercise directories.|
- Go into the common/ folder and type “make” to produce the USFATI executable.
- Enable the “reset.sh” script file by “chmod 700 reset.sh”
- Execute the “reset.sh” script file “./reset.sh”, this copy a fresh set of disk images to the exercise directories. Use this step whenever you need to reset your disk images.
Main task: Display the file content of a file under the root directory.
The main function is already written for you. The main function will repeatedly print the directory content of the root directory (i.e. similar to a “ls”), then prompt the user for a file to display (i.e. similar to a “cat” / “less” command). Your task is to implement the function
read_file(FAT_RUNTIME* rt, char filename) which returns:
- 0 if the file with filename cannot be found under the root directory.
- 1 if the operation is successful.
This function attempts to locate the directory entry for the file filename, then read all data sectors of this print and print them to the screen. Note: use the
print_as_text() function when you need to print out the content of a file data sector. This ensure your output format is exactly the same as ours to facilitate checking.
Several key criteria:
- Entire content of the file should be shown (duh!). This requires you to follow the “linked sector chain” by traversing in the FAT
- Note that the last sector may not be full! You need to print out only the valid content. (hint: use file size..).
- You are allowed to define as many helper functions as you need.
- You can add / change the parameter(s) of the read_file() function if needed.
- The main function should not be changed except the function call to read_file() can be modified with new parameters if you change them.
Main task: Import a normal file into the USFAT file system.
Similar to exercise 2, the main function is already coded for you. You only need to provide the implementation of the
import_file() function. This function returns:
- -1: if there is any error. Full error lists is given below. OR
- Non-negative value: Actual number of bytes copied over.
To facilitate explanation, let us assume we make the following call using the given function prototype:
import_file( &runtime, "example.txt", 25);
The function should perform the following checks:
- Ensure the normal file “example.txt” can be opened. You can assume the filename given by user follows the “8+3” filename restriction.
- Ensure the root directory of the USFAT media does not have another file with the same filename as “example.txt” as filename should be unique under a directory.
- Ensure the root directory is not full, i.e. has less than 8 files currently.
- If any of the above fails, the function returns “-1”.
- Once checks are all cleared, the function will now attempt to copy the “example.txt” into the data sectors.
- The function will try to use the first sector as specified (data sector 25) in this example. If the sector is free, copying can start there. Otherwise, you should check subsequent data sectors (e.g. 26, 27, 28 ..) and wraps around if needed. If there are no free data sector, the function terminates and return -1.
- Once copying starts, data sector chain needs to be constructed if you need more than one data sector. The logic for getting the next sector is the same: look for the free data sector in the subsequent indices and wrap around if needed. Remember to modify the FAT entries accordingly as you move along.
- Copy stops when i) the input file e.g. “example.txt” has been copied fully OR ii) there are no more free data sectors. Remember to “terminate” your sector chain by setting the END flag in the FAT.
- The function will also add a new directory entry with the right information into the root directory.
- Don’t forget to flush the FAT into the actual USFAT media.
- Finally, the function returns the total number of bytes copied to the caller.
- Note that this exercise changes the disk images. Use the “reset.sh” to restore the images if needed.
Hints and Tips:
- Browse the library calls. You have many helpful functions there to keep your pain in check.
- Define useful helper functions to reduce code spaghetti
- The sample solution is about 120+lines (with newlines, debug code, comments included).
- You can use your ex2.c to check whether the files are imported properly.
- Use the utility program USFATI to monitor the changes of sectors.
Several notable observations:
- “Hello.txt” is in sector 6, where the FAT entry is indicated with the END flag as it occupies only 1 sector.
- “Mystery.abc” starts from sector 0, follow the linked sector list to understand the requirement better (use adjacent if possible, otherwise search forward for free sector).
As exercise 3 is “a bit” challenging, I have decided to drop the bonus questions.
However, I hope you have the curiosity (and time) to explore further. Several things you can try (in increasing insanity order):
- Expand the directory to use multiple sectors. This removes the 8 files per directory limitation. Your code in ex2 can help.
- Implement subdirectory. (Rather straightforward actually).
- With (2), extend ex2 and ex3 to support subdirectory, i.e. read file with full path “/dir1/dir2/example.txt”, import file for deeper directory structure etc.