Understanding the FAT file system

The first 3 bytes of the sector are a short jmp instruction followed by a nop byte, used if the volume is bootable. The next 8 bytes are the OEM name, padded with spaces (0x20). This is usually the name of the tool that was used to build the filesystem image (e.g. mkfs.fat).

After the OEM name, it comes the BIOS Parameter Block (BPB), a data structure describing the layout of the volume. The following table describes the contents of the base BPB, common in all FAT filesystems.

FAT filesystems extend this structure with different fields, and the final structure is usually called Extended BIOS Parameter Block (EBPB). Please note that the term “BPB” will be used when refering to the base structure described in the first table, which is shared by all filesystem versions, while the term “EBPB” will be used when refering to one of the other two tables and its contents.

The following table describes the extra fields in FAT12 and FAT16 volumes.

And the next table describes the extra fields in FAT12 volumes.

Note that, in both the FAT12/FAT16 and FAT32 versions, the value of the Extended boot signature field should be 0x29 to indicate that there are 3 fields left at that point; a value of 0x28, on the other hand, would indicate that there is only one field left, the Volume serial number. Originally, byte 0x28 was used to indicate that the volume was using the DOS 3.4 EBPB, while byte 0x29 indicated the EBPB for DOS 4.0 version.

The remainder of the sector (up to offset 509, included) can be used to store executable instructions, which are normally the destination of the jmp instruction mentioned above; or to store any extra data that the system might need.

The bytes at offset 510 and 511 should be 0x55 and 0xAA, respectively, a magic value that indicates the BIOS that the sector is bootable. Note that this magic value might be written as 0x55AA or 0xAA55 depending on the machine’s endianness, but the BIOS will expect byte 0x55 first, followed by 0xAA, so it’s better to write them separately to avoid confusion.

These two bytes are usually the last ones of the first sector, since the Bytes per logical sector field of the BPB structure is usually 512, but they don’t necessarily have to be. The BIOS will check the bytes at offset 510 and 511, not at the end of the sector.

The FAT is an array of numbers that is used to define linked lists of the clusters that form the contents of a file. In order to fully understand this definition, some concepts need to be explained first.

Just like a sector is a fixed-size block of contiguous bytes, a cluster is simply a fixed-size group of contiguous sectors. The number of sectors that form a cluster can be obtained from the second field of the BPB. For example, if each cluster is 4 sectors (according to the second field), and each sector is 512 bytes (according to the first field), a cluster would use 2048 contiguous bytes.

The meaning of the term file can vary depending on the context and the level of abstraction, but it will be used in this context to refer to a data structure that contains information (i.e. metadata) about some arbitrary amount of data (i.e. the actual file contents). A file structure, which will take the name DirectoryEntry below, contains information such as the filename, the size of the data in bytes, and the creation and access dates.

While this file metadata is stored in some place that will be discussed below, the actual contents of the file are stored in one or more clusters (which are not necessarily adjacent to each other) in the data region. The data region is located after the root directory, as shown in Figure 1.

For example, if the cluster size was 2KiB and we wanted to store an 11KiB file, we would need to somehow build a 6-element list that kept track of the clusters that store that file’s data (the last one won’t be full, but still “owned” by this file).

Given a specific cluster index, there would need to be a way of retrieving the index of the next cluster on its list. To accomplish this, each cluster in the volume is assigned an entry in the FAT sequentially, so the first cluster would be assigned to entry 0 of the FAT, the second element to entry 1, and so on (this is not entirely accurate, as explained below). Each entry in the FAT will then contain the cluster index of its next element, or a special marker to indicate the end of the linked list².

For example, in order to build the cluster list represented in the previous figure, the following pseudo-code could be used. In this case, value of the end-of-chain marker assumes that this is a 16-bit FAT.

fat[0] = 2;      /* Cluster 1 is skipped */
fat[2] = 3;
fat[3] = 4;
fat[4] = 5;
fat[5] = 7;      /* Cluster 6 is skipped */
fat[7] = 0xFFFF; /* Mark end of chain */

As shown below, this is not entirely accurate, since the first data cluster is not mapped to the first element of the FAT. Either way, the important note is that the FAT is used to keep track of the clusters that store the contents of files, by building linked lists with their cluster indexes.

The size of each FAT entry changes depending on the filesystem version, and that is precisely what the 12/16/32 number indicates: the size of a FAT entry in bits. The 16-bit version will be used for explaining the layout of the FAT, since each entry is two bytes, and therefore easier to understand. The layout of a 32-bit FAT is pretty similar, the size of each element is just twice as big. The 12-bit version, however, is more tricky since it uses one bit and a half (i.e. 3 nibbles), so it will be explained in detail below.

The following figure shows the hexdump of the first 64 bytes of a 16-bit FAT. Each (non-empty) entry has been highlighted to show their linked list. Please note that the hexadecimal offsets in the following figure are expressed in bytes, but the FAT stores the linked lists with indexes to other 16-bit entries.

The first thing that should be noted about the FAT, and about the filesystem in general, is that it’s strictly little-endian, meaning that the least-significant bytes are stored at a smaller offset in the disk (i.e. the value 0xAABBCCDD would be stored as DD CC BB AA). The previous figure shows a hexdump, and although the bytes are grouped in pairs, they are dumped one by one, in the order in which they are stored in the disk. For example, the contents of the third 16-bit entry are displayed as 0300, but actually correspond to the value 0x0003. This will be specially important later when describing the layout of a 12-bit FAT, since each entry is one byte and a half.

The first two entries of the FAT are reserved, the first one usually being the FAT ID, and the second usually being the value used as the end-of-chain marker. Therefore, the first data cluster would correspond to the third entry of the FAT, not the first one. Since the linked lists themselves are built using “absolute” indexes in the FAT, the real cluster indexes can be calculated by subtracting 2 from the value stored in the FAT. For example, in the previous figure, entry 4 of the FAT contains the value 5, so the real index of the next cluster in the list would be 3, since it’s the fourth actual cluster in the volume.

As noted above, the 12-bit FAT is a bit more complicated, because each entry is one byte and a half. To The following figure shows how the previous 16-bit FAT would be represented with 12-bits per entry. Since each entry is 3 nibbles, and the structure is little-endian, nibbles in entries with an odd index have been highlighted in bold, to hopefully make it easier to visualize.

Also note how there are 15 bytes per row in this figure, instead of 16 like in the previous one. This has been done to avoid having one byte of the entry in one line (e.g. the 0x14 at offset 0x0F) and the third nibble in another line (e.g. the lower half of the byte at offset 0x10).

Just to emphasize again, since the byte ordering can be confusing in this version, the following example shows how the entries are distributed and nibbles ordered in the 12-bit FAT.

Entry distribution:

  AA BA BB CC DC DD EE FE FF ...
  `------´ `------´ `------´
   Two      Two      Two
   entries  entries  entries

Nibble order:

  23 61 45 89 C7 AB EF 3D 12 ...
  `------´ `------´ `------´
   0x123,   0x789,   0xDEF,
   0x456    0xABC    0x123

The following table shows the fields of the DirectoryEntry structure.

The name field follows the 8.3 filename scheme, where the first 8 bytes of the array are the file name padded with spaces, and the last 3 bytes are the file extension.

Each bit in the File attributes field indicates a different property, according to the following table.

The third field of a DirectoryEntry contains the creation time in tenths of a second, and its value range is [0..199]. The dates and times in the structure are stored as 16-bit integers with the following layouts:

Time: hhhhhhmmmmmsssss
      `----´`---´`---´
       Hour  Min  Sec

Date: yyyyyyymmmmddddd
      `-----´`--´`---´
       Year   Mon Day

Just like the EBPB changes between FAT12/FAT16 and FAT32, the method for determining the location and size of the root directory also change. These differences will be explained now.

Location and size in FAT12 and FAT16

In FAT12 and FAT16, this array is located right after the FAT(s), so the sector number can be calculated by multiplying the number of FATs by the size of a FAT, and adding that to the number of reserved sectors. All three of these values can be obtained from the base BPB.

The number of DirectoryEntry elements of the array is determined by the Root directory entries field of the BPB.

Location and size in FAT32

In FAT32 filesystems, the location of the root directory is determined by the Root directory cluster entry of the EBPB, which usually has a value of 2, but not necessarily.

In FAT32 filesystems, the Root directory entries field of the BPB must be set to zero, so the number of entries is calculated by following the chain of cluster indexes that is stored in the FAT, just like any other directory.

Once the location and size of the root directory is known, it can be accessed like a normal array, each element being 32 bytes.

The size of the root directory in sectors can be calculated by multiplying its number of entries by the size of a single entry in bytes, dividing that by the number of bytes per sector, and rounding up:

const uint32_t root_dir_bytes =
    bpb->root_dir_entry_count * sizeof(struct DirectoryEntry);

uint32_t root_dir_sectors = root_dir_bytes / bpb->bytes_per_sector;
if (root_dir_bytes % bpb->bytes_per_sector != 0)
    root_dir_sectors++;

Alternatively, as recommended in page 13 of the FAT specification, one can round up by adding the number of bytes per sector minus one before performing the integer division:

const uint32_t root_dir_bytes =
    bpb->root_dir_entry_count * sizeof(struct DirectoryEntry);

const uint32_t root_dir_sectors =
  (root_dir_bytes + (bpb->bytes_per_sector - 1)) /
    bpb->bytes_per_sector;

Note that, on FAT32, the Root directory entries field of the BPB is zero, so the result of these operations will also be zero. This is expected when calculating the first data sector below.

The first data sector can be calculated by adding the number of reserved sectors (such as the boot sector), the number of sectors used by the FAT(s), and the number of sectors used by the root directory.

The number of reserved sectors can be obtained from the third field of the BPB, as explained when calculating the location of the FAT. The number of sectors used by the FAT is determined by either the Logical sectors per FAT field of the base BPB, or, if it’s zero, by the Logical sectors per FAT field of the FAT32 EBPB. The number of sectors of the root directory is calculated using any of the methods from the previous section; again, note that this value is expected to be zero in FAT32.

const size_t sectors_per_fat = (bpb->sectors_per_fat_16 == 0)
                                 ? bpb->sectors_per_fat_16
                                 : ebpb->sectors_per_fat_32;

const uint16_t reserved_sectors  = bpb->reserved_sectors;
const uint32_t total_fat_sectors = bpb->fat_count * sectors_per_fat;
const uint32_t root_dir_sectors  = /* Shown above */;

const uint32_t first_data_sector =
  reserved_sectors + total_fat_sectors + root_dir_sectors;

With this information in mind, it should be possible to calculate the clusters numbers where the file contents are stored, and the sector when the data region starts, therefore allowing us to read all the necessary sectors that contain the file contents. This is the general algorithm for accomplishing this:

1. Obtain the sector where the FAT starts, the sector where the root directory starts, and the size in sectors of the root directory. All this has been explained above.
2. Search for the file by iterating the root directory until the name field of a DirectoryEntry structure matches the filename you are looking for.
3. Obtain the first FAT index in the chain of clusters that hold the contents of the file. This index can be obtained from the Low word of the first cluster index field of the DirectoryEntry. Note that this index is for the FAT, it’s not the real cluster number in the volume.
4. Calculate the real cluster number by subtracting 2 (i.e. the number of reserved FAT entries) from the FAT index that was just obtained.
5. Calculate the sector number by multiplying the real cluster number by the number of Logical sectors per cluster (second element of the BPB), and adding that to the number of sectors before the Data region, as explained above.
6. Somehow read from the disk a cluster worth of sectors, starting at the sector number from the previous step.
7. Obtain the next FAT index by reading the value stored at the FAT entry corresponding to the current FAT index (i.e. fat_idx = fat[fat_idx]).
8. If the new FAT index is smaller than the end-of-chain marker, go back to step 2. Otherwise, we are done with the file.

In FAT32, when reading the FAT index, you will need to also use the High word of the first cluster index field of the DirectoryEntry.

Also note that, as explained above, getting the next FAT index might be more complicated depending on the endianness of the machine, since all the structures in the FAT filesystem are little-endian.