Reduced FAT File System Project. Part 2
by: burt rosenberg
at: university of miami
date: nov 2023
US Patent US4905110 A
Goals
Recall from Part 1:
-
We will make a severe restriction for this project — all files require
exactly one cluster of storage. This will put off the discusion of how the FAT
table really works. Under the assumption of small files, the FAT table only
keeps track of what blocks are used and what are unused.
In this part we remove the restriction and undetake that discussion.
We also introduce a new command dd, which is a helpful diagnostic command
that prints the cluster chain, as determined by the FAT table, for a given file.
The MAN Page
NAME
fat-reduced
SYNOPSIS
fat-reduced [-v]
DESCRIPTION
An interactive program to simulate the operation of the File Allocation
Table of a very much simplified FAT file system.
OPTIONS
-v verbose output. Can be used multiple times.
COMMANDS
ls
to list the file names, data lengths, and directory index
qu
to quit. this is an administrative command
rd _filename_
to print the contents of file _filename_. Error if it does not exist.
rm _filename_
to remove the file _filename_. Error if it does not exist.
wr _filename_ _content_
to create or update the file _filename_ with content _content_. Although
the file can contain binary values, this command creates files with ASCII
content only.
dd _filename_
to dislay the cluster chain associated with the named file
Filenames are at most 15 characters. Values are 64 bytes.
HISTORY
Created for the 241 edition of CSC421 (2023-2024 academic year).
BUGS
The FAT Table
To store files that are larger than a cluster, a chain of clusters is allocated
for the file.
The FAT table keeps track of the cluster chain.
For each cluster i, corresponds the FAT table index i. When
we had a single cluster in allocated for the file, the DirEnt indicated the cluster
number i and fat_table[i] was -1 to indicated two things,
- That cluster i is not free.
- That cluster i is the last cluster in the cluster chain.
If the file needed two cluster, say i1 and i2, in that order, then
- The DirEnt field starting_cluster is set to i1.
- The FAT table indicates that i2 follows i1 by setting fat_table[i1] to i2.
- The FAT table signals that there are no more clusters following t2 by setting
fat_table[i2] to -1.
In general, a chain of clusters will be required,
This will always be reprsented by,
- The Dirent stores x1
- The FAT table has fat_table[x(i-1)]:=xi
- fat_table[xk]:=-1
An example
2. After creating 3 files.
+---+
0 | 1 |
+---+
1 |-1 |
+---+
2 | 3 |
+---+
3 |-1 |
+---+
4 | 5 |
+---+
5 |-1 |
+---+
6 | 0 |
+---+
7 | 0 |
+---+
1. An initialized FAT table
+---+
0 | 0 |
+---+
1 | 0 |
+---+
2 | 0 |
+---+
3 | 0 |
+---+
4 | 0 |
+---+
5 | 0 |
+---+
6 | 0 |
+---+
7 | 0 |
+---+
-
We begin with a FAT table all zeros, since all blocks are free.
-
Three files are created, each requiring two blocks.
- The first chains clusters 0 and 1, 0->1.
- The second chains clusters 2 and 3, 2->3.
- The third chains clusters 4 and 5, 4->5.
The clusters 6 and 7 are still free.
4. After creating a fourth file.
+---+
0 | 1 |
+---+
1 |-1 |
+---+
2 | 3 |
+---+
3 | 6 |
+---+
4 | 5 |
+---+
5 |-1 |
+---+
6 |-1 |
+---+
7 | 0 |
+---+
3. After deleted the second file
+---+
0 | 1 |
+---+
1 |-1 |
+---+
2 | 0 |
+---+
3 | 0 |
+---+
4 | 5 |
+---+
5 |-1 |
+---+
6 | 0 |
+---+
7 | 0 |
+---+
-
We delete the file that occupied clusters 2 and 3. The FAT entries are zero.
-
Finally, a file requiring 3 clusters is created. It takes the first 3 free clusters
available and chains them into the cluster chain 2->3->6.
The action functions
- wr_action() function to implement the wr operation.
- Command takes two arguments: the filename and the file contents.
- If the file does not exist, create it with the given contents.
- If the file exists, appende the given to the contents
- Clusters are allocated as needed, but never more than necessary to contain the file.
- The content is assumed to be binary.
- The actual content size is recorded in the DirEnt.
- Output: The action has no output.
- Errors:
- ERR_DIRFULL: no more DirEnt's available.
- ERR_FATFULL: no more FAT table entries available.
- ERR_DISKFULL: no more clusters available.
- rm_action() to implement that rm operation to remove a file.
- Command takes one argument: the filename.
- Remove the file by setting the filename to the empty string and freeing all clusters
in the files cluster chain.
- Output: The action has no output.
- Errors:
- ERR_NOEXIST: if the file to remove does not exist.
- dd_action() to implement that dd operation to dump the files metadata.
- Command takes one argument: the filename.
- Output: Displays the cluster chain for the file named.
- Errors:
- ERR_NOEXIST: if the file to remove does not exist.
Implementation Notes
As was noted in class, the activities that would be needed for Part 1 include,
- Walking the directory array for all valid DirEnts.
- Walking the directory array to find an available DirEnt.
- Waltking the FAT table to find an available cluster.
The FAT table is an array implementation of a linked list. There is a lot of documentation
on-line about such a data structure technique. The operations the FAT table will support are,
- The creation of a cluster chain.
- The walking of a cluster chain.
- The extending of a cluster chain.
- The deletion of a cluster chain.
The cluster chain structure provides storage for the data in units of clusters. The data
fits into a sequence of clusters using all bytes in the clusters with the possible
exception of the final cluster. The final cluster can have the 0 through CLUSTER_SIZE-1
bytes unused, and they will be the bytes of highest index in the cluster. The unused
bytes are called the slack space.
-
Writing to a new file, zero or more full clusters are allocated and one final cluster.
The final cluster can be full or have slack, but will not be entirely slack.
-
Writing to an existing file might possibly extend the cluster chain to make room
for the additional data.
-
If the file had slack in its final cluster, this slack is used for
the additional data. If this is sufficient, no clusters are added.
-
Else, if the slack is insufficient, the slack is used and zero or more full clusters and a final cluster
are appended to the chain. The final cluster may be full or have slack, but it will not be entirely slack.
Original file with contents "abcdef"; stored in two 4 byte clusters with 2 bytes of slack
+---+---+---+---+ +---+---+---+---+
| a | b | c | d |--->| e | f | | |
+---+---+---+---+ +---+---+---+---+
Wrote "ghijkl" to the file; slack used and one more 4 byte cluster added
+---+---+---+---+ +---+---+---+---+ +---+---+---+---+
| a | b | c | d |--->| e | f | g | h |--->| i | j | k | l |
+---+---+---+---+ +---+---+---+---+ +---+---+---+---+
The following implementation details must also be followed,
- If a filename is too long, truncate to the maximum length.
- When finding free DirEnt's or Clusters, find and use the one with smallest index.
- Use these formats to implement the dd command:
