fat16 filesystem layout

First there was FAT, then FAT12, FAT16 and finally FAT32. Inferior filesystems nowadays, but nevertheless both ubiquitous and mandatory for some uses. And sometimes you need to be aware of the differences.

A short breakdown of FAT16 follows — we'll skip the older FAT as well as various uncommon settings, because those are not in active use.

Sector size

The storage device defines (logical) sector sizes. This used to be 512 bytes per sector for a long time (we're skipping pre-hard disk tech), but this is now rapidly moving to 4096 bytes per sector on newer SSD and NVMe drives. Both the partition table and the filesystems record this size somewhere.

Boot sector

The first sector of FAT16 (or any other FAT version for that matter) holds the boot sector. How long the sector is, depends on the sector size (commonly 512 or 4096 bytes). At offset 0x00B two bytes hold the bytes per sector. Commonly 00 02 (512 little endian) or 00 10 (4096 little endian).

At 0x00D one byte holds the sectors per cluster. This must be a power of two (1, 2, 4, ...). In the data area of the filesystem, files are accessed by cluster number. A cluster can hold at most one chunk of a single file. If the amount of bytes per cluster is large, you'll waste space if you have many small files. Conversely, if you have only large files, you can choose larger and fewer clusters, making the allocation tables more efficient.

Let's look at the hex dump of a cleanly initialized FAT filesystem. We'll compare FAT16 created with 512 byte sector sizes, with FAT16 with 4096 byte sector sizes. You can reproduce by running dd if=/dev/zero of=fat16.img bs=1M count=510 to create an empty filesystem image and running mkfs.fat -F 16 -S 512 -s 16 fat16.img or mkfs.fat -F 16 -S 4096 -s 2 fat16.img to make a filesystem on it. (-s defines sectors per cluster.)

--- fat16-512
+++ fat16-4096
@@ -1,3 +1,3 @@
-00000000  eb 3c 90 6d 6b 66 73 2e  66 61 74 00 02 10 10 00  |.<.mkfs.fat.....|
+00000000  eb 3c 90 6d 6b 66 73 2e  66 61 74 00 10 02 02 00  |.<.mkfs.fat.....|
-00000010  02 00 02 00 00 f8 00 01  20 00 40 00 00 00 00 00  |........ .@.....|
+00000010  02 00 02 00 00 f8 20 00  20 00 40 00 00 00 00 00  |...... . .@.....|
-00000020  00 f0 0f 00 80 00 29 ff  fc 1e d8 4e 4f 20 4e 41  |......)....NO NA|
+00000020  00 fe 01 00 80 00 29 77  4c de d8 4e 4f 20 4e 41  |......)wL..NO NA|
...
 *
 00002000  f8 ff ff ff 00 00 00 00  00 00 00 00 00 00 00 00  |................|
 00002010  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
 *
 00022000  f8 ff ff ff 00 00 00 00  00 00 00 00 00 00 00 00  |................|
 00022010  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|
...

Indeed, we see 00 02 versus 00 10 for the bytes per sector, and 10 (16) versus 02 (2) for sectors per cluster. The cluster size is 8192 for both: 512 * 0x10 or 4096 * 0x2.

Next, at 0x00E, is the count of reserved sectors. mkfs.fat(8) defaults this to the same number as clusters per sector. (Also 8192 bytes.)

Then, at 0x010, there's the count of FATs — that is, the File Allocation Tables, the tables that hold linked lists of cluster positions, specifying in which clusters a file resides. This is always 2, i.e. two copies, for redundancy.

At 0x013, two bytes hold the total logical sectors (not valid for FAT32) or 0, in which case a four byte value is at 0x020. Here we see 00 f0 0f 00 (1044480 sectors) and 00 fe 01 00 (130560 sectors) respectively. For a 510 MiB filesystem this is indeed correct.

And at 0x016 we see 00 01 (256) or 20 00 (32) sectors per FAT. In both cases 128 KiB.

After the boot sector

After the reserved sectors (only the boot sector for FAT16), 8 KiB in this case, there are the two FATs (2 * 128 KiB) and finally the data.

Directory entries (containing filenames and pointers into the FAT) are special types of files. For FAT16, the root directory entry is actually at a fixed position (after the last FAT), with at most 512 32-byte entries (00 02 seen at 0x11). Subdirectory entries are located in the data area, just like regular files.

Taking the values from above, the filesystem layout looks like this (for 512-bytes per sector and 4096-bytes per sector respectively):

Total number of clusters

Computing the number of clusters in the data area is done by taking the total number of sectors (from 0x013 or 0x020), subtracting the reserved sectors (see 0x00E), FAT sectors (from 0x016) and root directory (32 and 4 sectors respectively), and dividing, rounding down, by the number of sectors in a cluster (at 0x00D).

For the 512 byte sector filesystem above, that means:
floor((1044480 - 16 - 2*256 - 32) / 16) = 65245 clusters (509.7 MiB)

For the 4096 byte sector filesystem above, that means:
floor((130560 - 2 - 2*32 - 4) / 2) = 65245 clusters (509.7 MiB)

Which FAT version are we dealing with?

While you would think that somewhere in the FAT headers, there would be a version field. There isn't one.

According to Microsoft's EFI FAT32 specification, any FAT file system with less than 4085 clusters is FAT12. If it has less than 65,525 clusters, it's FAT16. Otherwise it is FAT32.

Why am I telling you all this? That's for tomorrow's post.