File System

This is a specification for the file system. It is yet to be implemented in System 42. Please check the backlog for implementation progress.

For now, we will call it CATFS… Until we find a better name. CAT is for cluster allocation table. FS is self explanatory.

I need a good name for this fictional file system. Suggestions are welcome.

CATFS is reminiscent of FAT16 family of file systems, but simplified. There is no partition table. No allocation table redundancy.

The sector size is determined by the disk configuration, and as mentioned in the disk documentation, is often 256 bytes.

File system has to keep track of allocated space. This can be done per sector. However, that would make the overhead quite large. To reduce the overhead, CATFS tracks space allocation per group of sectors, called cluster.

Cluster is a group of continuous sectors, usually 4 or 8. While the data is read or written one sector at a time, it is allocated one cluster at a time. So the application writes one sector at a time until the whole cluster is filled, and then another cluster is allocated.

Boot sector is a single sector. It is the first sector on a CATFS disk. It contains necessary information about the file system. It also contains boot code, the first code executed that loads and starts the operating system.

Note that the total number of sectors occupied by a CATFS is 1 + number of CAT sectors + (cluster count * sectors per cluster).

See boot loader page for more on how boot sector is used.

CAT occupies a number of sectors immediately after the boot sector. CAT is a list of cluster offsets, each offset of word size. In the standard 256 byte sector, we have 128 cluster offsets.

It is important to remember that each cluster refers to multiple sectors. So, cluster pointer actually points to a number of sectors.

CAT is a linked list of cluster offsets. The directory entry, explained below, contains the offset to the first allocated cluster. And each cluster offset in CAT points to the next one. The last cluster in the list, one that does not point to any other cluster, has offset value of 0xFFFF.

Empty, unallocated clusters have offset value 0x0000.

When deleting files and directories, after the directory entry is marked deleted, the cluster offsets occupied by this entry should be set to zero as well.

NOTE: deleting files requires at least two sectors to be written, directory and CAT. While unlikely, it is possible that the system can fail between these two writes, and leave the CATFS in inconsistent state, where CAT indicates the clusters are in use while no directory entry points to this space.

TBD: diagram example

Immediately after the allocation table is the root directory.

Every directory is a list of file structures which describe directories and files.

Each directory sector contains a number of these structures, always starting from the beginning of the sector. Number of structures is determined by the sector size. It is possible to have some unused bytes at the end of the sector if the sector size is not divisible by structure size.

Filename consists of 8 characters for the name and 3 for the extension.

Allowed filename characters are [a-zA-Z0-9_-+].

If a filename or extension has less characters than the field, it should be padded with zeroes.

If the filename starts with zero, this indicates that the specific field is empty. Zero is also used to mark a file deleted.

Deleting existing files and directories means setting their first character to zero and then setting all cluster offsets used by the file 0x0000 indicating they are free. Note that the actual data in the files is not deleted, but simply marked as free.