FATFS: Add Support for FAT16/FAT12 File Systems

This PR extends the FATFS driver to support FAT 12 and FAT 16 versions of the FAT file system.

Why?

Why not! But also, this enables use of the QEMU VVFAT virtual drive, which makes it really easy to share files between the host and guest:

SERENITY_BOOT_DRIVE="$SERENITY_BOOT_DRIVE -drive file=fat:16:rw:$SCRIPT_DIR/../Documentation/"

Note that this is still pretty slow driver. The driver doesn't do any caching, and frequently reads all blocks associated with a file. There's a lot of room for optimization with some light caching of the FAT table and being more selective about which sectors/blocks are read.

PR Overview

e834897b822d412b08bf0d2ca5f24480bed01074: Add support for different versions of the DOS BIOS Parameter Block. This is a majority of the change.
f795ebc4e111cbd3be8cdebc209e0e3391957f7, 6f1f506f3d6abd540dc1fff333dc2727438164ff: Support for FAT16/FAT12 clusters. Once the above was in-place, this is was fairly minor.
70d156d5f7172b63585ee130a1be814b20f6f53b: Resolve existing bug where files would not be truncated to their size, and instead would return all of the sectors within the cluster associated with the file.

DOS BIOS Parameter Block (BPB)

The DOS BIOS Parameter Block (BPB) is the header of a FAT file system, and stored in the first sector. It contains the parameters required to locate and read the data in the file system. There are multiple versions of the BPB, with the DOS 4 and DOS 7 being the versions used by (modern) FAT File Systems. These are called "Extended BPBs" (EBPBs) because they extend the original BPB. The DOS 4 BPB is typically used by FAT12/16 file systems, and DOS 7 used by FAT32, but other combinations are possible.

The DOS 4 and DOS 7 EBPBs have a common set of initial fields, the DOS 3.31 BPB. Following the fields defined in the DOS 3.31 BPB (the first 25 bytes), they diverge in field location/definition. I found the Wikipedia DOS Parameter Block and Design of the FAT File System pages very helpful references.

Commit e834897b822d412b08bf0d2ca5f24480bed01074 introduces support for these different BPB versions through the creation of a DOSBIOSParameterBlock class that abstracts the common fields into accessors, and provides structs that interpret the BPB sector as either EBPB.

Another major difference between FAT12/16 and FAT32 is that in FAT12/16, the root directory entries are not stored in the FAT, but instead in sectors following the FAT. This necessitated special handling of the root entry inode, because it is not associated with a cluster number, but instead the root directory regtion. FATFS::first_block_of_cluster() was extended to support with, with a sentinel value of cluster == 0 to signify the root directory entry.

FAT12/FAT16 FAT Cluster Support

Beyond the above differences, the FAT table itself differs between each FAT version. These (fairly trivial) changes to support parsing cluster numbers from 12-bit and 16-bit values were implemented in f795ebc4e111cbd3be8cdebc209e0e3391957f7, 6f1f506f3d6abd540dc1fff333dc2727438164ff.

Testing

I created FAT 12, FAT 16, and FAT 32 file system images using mkfs.vfat (as in #16754).

For devs on macOS, these can be populated with hdiutil:

$ hdiutil attach fat16.img
# Add files to "/Volumes/NO\ NAME/"
$ hdiutil detach /Volumes/NO\ NAME/

These were added to qemu with the following change to run.sh:

+SERENITY_BOOT_DRIVE="$SERENITY_BOOT_DRIVE -drive file=$SCRIPT_DIR/../fat32.img,format=raw,index=1,media=disk"
+SERENITY_BOOT_DRIVE="$SERENITY_BOOT_DRIVE -drive file=$SCRIPT_DIR/../fat16.img,format=raw,index=2,media=disk"
+SERENITY_BOOT_DRIVE="$SERENITY_BOOT_DRIVE -drive file=$SCRIPT_DIR/../fat12.img,format=raw,index=3,media=disk"

Mounting a file system will detect the FAT file system version, EBPB version, and print the decoded BPB data:

2330.586 [#0 mount(69:69)]: FATFSs: oem_identifier: mkfs.fat
2330.586 [#0 mount(69:69)]: FATFS: bytes_per_sector: 512
2330.586 [#0 mount(69:69)]: FATFS: sectors_per_cluster: 4
2330.586 [#0 mount(69:69)]: FATFS: reserved_sector_count: 4
2330.586 [#0 mount(69:69)]: FATFS: fat_count: 2
2330.586 [#0 mount(69:69)]: FATFS: root_directory_entry_count: 512
2330.586 [#0 mount(69:69)]: FATFS: media_descriptor_type: 248
2330.586 [#0 mount(69:69)]: FATFS: sectors_per_track: 32
2330.586 [#0 mount(69:69)]: FATFS: head_count: 2
2330.586 [#0 mount(69:69)]: FATFS: hidden_sector_count: 0
2330.586 [#0 mount(69:69)]: FATFS: sector_count: 20480
2330.586 [#0 mount(69:69)]: FATFS: sectors_per_fat: 20
2330.586 [#0 mount(69:69)]: FATFS: EBPB: DOS 4
2330.586 [#0 mount(69:69)]: FATFS: drive_number: 128
2330.586 [#0 mount(69:69)]: FATFS: flags: 0
2330.586 [#0 mount(69:69)]: FATFS: volume_id: 1231697288
2330.586 [#0 mount(69:69)]: FATFS: Detected FAT16 with 5101 data area clusters
2330.598 [#0 mount(69:69)]: FATFS: Creating inode 48059 with filename "."

QEMU vvfat disk

A much more stressing and useful test environment was the QEMU vvfat driver, which creates a FAT "disk" out of a host directory.

The vvfat driver has many options/modes, but the most useful are:

floppy: Present drive as a floppy disk, meaning there is no MBR partitioning scheme, and instead just the FAT file system. When the vvfat drive is added with the :floppy: option, the drive block device (ie /dev/hda) can be mounted directly.
:floppy: not specified: Present drive as a hard disk. This disk contains an MBR and a single partition. Creation of block devices for MBR partitions isn't happening automatically, but can be created with mknod.
:12:, :16:, :32: to specify FAT version: Control the FAT version that QEMU uses when creating the drive. There is a QEMU bug mixing :12:floppy: (the resulting sector count for the drive is considered FAT12), and QEMU very loudly reports that FAT32 is untested, but otherwise it is effective.

I created a md5sum verification file on my host:

$ cd Documentation/
$ md5sum *.md */*.md > Documentation.md5

and then compared the checksum of each file within SerenityOS:

$ mkdir fat
$ mknod /dev/hdap0 b 100 0  # When using a hard-disk vvfat drive, not "floppy"
$ mount -t fat /dev/hdap0 fat
$ cd fat
$ md5sum --check Documentation.md5

Dec 12 '23 08:12 tajmorton

Hello!

One or more of the commit messages in this PR do not match the SerenityOS code submission policy, please check the lint_commits CI job for more details on which commits were flagged and why. Please do not close this PR and open another, instead modify your commit message(s) with git commit --amend and force push those changes to update this PR.

Dec 14 '23 22:12 BuggieBot

Thank you for the re-review @ADKaster! Comments addressed, rebased on latest master, and re-tested.

Jan 07 '24 22:01 tajmorton