Reduced FAT File System Project. Part 1

by: burt rosenberg
at: university of miami
date: nov 2023

US Patent US4905110 A

Goals

File systems are an example of data persistence. Computer operating systems make the file system one of their core provisions to the user. Modern operating systems allow for a variety of file systems to be in use at the same time.

A very popular file system is FAT. It was Microsoft's original file system, even before windows, and continues to this day in many devices. This file system is a reduced version of the FAT file system, retaining many of the key concepts. Some of the simplifications are because the history of FAT complicated its implementation. But some simplifications do represent reduced functionality.

All file systems must keep track of disk space associated with a file. Disk space is allocated in units of blocks or clusters, so that filesystem must keep for each file an ordered sequence of clusters. The file system also needs to be able to identify a file by name, or by the file name in a hierarchy of directory names.

The FAT file system did these tasks using two important data structures,

1. The FAT Table, standing for File Allocation Table.
2. The DIRENT, the directory entry structure.

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.

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.
   
   Filenames are at most 15 characters. Values are 64 bytes.

HISTORY
    Created for the 241 edition of CSC421 (2023-2024 academic year).
    
BUGS

The Phony Disk

1. The root directory, an array of DIRENT structures.
2. The FAT, an array of cluster numes (integers).
3. The cluster table, an array of clusters hold the file contents.

1. The first few blocks are the Superblock, which describes the filesystem.
2. The next set of blocks are sufficient to store the FAT array.
3. The remainder of the blocks store the directory structures and the file content structures intermingled.

The Directory and DIRENTS

In FAT a directory is a sequence of DIRENTS that themselves form a file. We shall implement an even simpler filesystem where all DIRENT's are stored in a fixed array. We will not have directories inside directories.

Project Details

Note: the details might differ from the current source code.

#define FILENAME_LEN 15
#define CLUSTER_SIZE 32
#define DIR_N 64
#define FAT_N 128
#define CLUSTER_N (FAT_N)

#define FAT_FREE 0
#define FAT_LAST -1

struct  DirEnt {
    char name[FILENAME_LEN+1] ;  // null terminated file name. empty string if entry is free
    unsigned int len ;         // length of file in bytes
    unsigned int starting_cluster ; // cluster number of first cluster
} ;

 struct Cluster {
    char data[CLUSTER_SIZE] ;
} ;

// these are static because we are simulating a disk, which
// is a globally referenceable unique entity.

static struct DirEnt root_dir[DIR_N] ;
static unsigned int fat_table[FAT_N] ;
static struct Cluster cluster_table[CLUSTER_N] ;

To receive full credit for the project, certain operations must be done in strict conformance with this specification.

• When searching for an empty directory enty, choose that one with the smallest index.
• The values in the FAT table are either FAT_FREE or FAT_LAST.

Callout Table

The code uses a function call-out table to jump to the code implementing these operations. The functions have the signature,

     int (*action_function)(int actc,char * actv[])

Refer to the code how the actv array is filled-out. It mimics the argc, argv parameters to a C main function. They are the parsed command lines so the first (entry 0) will be the command name. For example, the wr command will receive an actv,

1. actc: will be 3.
2. actv[0]: the string "wr".
3. actv[1]: the filename, as a string.
4. actv[2]: the content, as a string.

The action functions

• qu_action() to implement the qu operation quit the program.
  • Command takes no arguments.
  • Output: The action has no output.
  • Errors: ERR_ABORT: returned always.
• ls_action() function to implement that ls operation to list the root directory.
  • Command takes no arguments.
  • Output:
    • A printf format is provided, so output matches reference.
    • The listing gives the DirEnt number, the file length, and file name.
    • The listing is in order of the DirEnt index.
    • Empty Dirent's are not listed.
  • Errors: None.
• wr_action() function to implement the wr operation.
  • Command takes two arguments: the filename and the file contents.
  • Create the new file with the given filename and the given contents.
  • A cluster is allocated from the FAT table.
  • The content is assumed to be binary, and is no more than cluster size bytes.
  • 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.
    • ERR_CREATE: trying to write over an existing file.
• rd_action() to implement the rd operation to print the file contents.
  • Command takes one argument: the filename.
  • Output:
    • The format must be precisely as specified.
    • You may assume that the contents are printable ascii.
  • Errors:
    • ERR_NOEXIST: if the file to read does not exist.
• 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 the attached cluster.
  • Output: The action has no output.
  • Errors:
    • ERR_NOEXIST: if the file to remove does not exist.

Implementation Notes

• If a filename is too long, truncate to the maximum length.
• If file contents are too long, truncate to maximum cluster length.
• Data length is as in DirEnt.len, not according to a null byte. Your code might be tested on this.
• When finding free DirEnt's or Clusters, find and use the one with smallest index. This is for purposes of automatic grading.
• Use this format to implement the ls command:
  "%3d %6d %s\n"
• Use this format to implement the rd command:
  "%s\n"
  (once the bytes have be gathered and a null terminator added)

This work is licensed under a Creative Commons Attribution-ShareAlike 3.0 Unported License.

author: burton rosenberg
created: 5 nov 2023
update: 12 nov 2023