Fat File System

In this post, we discuss the internals of a FAT based file system. FAT stands for File Allocation Table, which is also the name of the central data structure of this design. It is one of the oldest file system designs still in use – your pen drive is probably formatted with some variant of it (FAT32 or exFAT).

The layout

A FAT file system has a fairly simple on-disk layout:

• Reserved region: Contains the boot sector and basic parameters of the file system – block size, total number of blocks, location of the fat table etc.
• FAT table: An array with one entry per data block. This is the heart of the design.
• Root directory: The starting point for all path lookups. In FAT12/16 this is a fixed-size region; in FAT32 it is stored like a normal file.
• Data region: The actual data blocks of the files and directories.

The disk is divided into fixed sized blocks (the FAT terminology is cluster, but we will stick with block). The size typically varies from 512B to 4KB.

The fat table

The fat table is an array-based linked list. Each entry in the table corresponds to one data block, and stores the index of the next block of the same file. A special value (EOF marker) indicates the last block of a file, and another special value (typically 0) indicates a free block.

So, a file is simply a chain in this table. Say a file starts at block 4, and occupies blocks 4, 7 and 9:

index:  0    1    2    3    4    5    6    7    8    9
value: ...  ...  ...  ...   7   ...  ...   9   ...  EOF

The directory entry of the file stores the starting block (4 here), along with the file name, size, and attributes. To read the file, you start at block 4, and keep following the chain in the fat table till you hit the EOF marker.

The same table, drawn as a picture. a.txt occupies blocks 4, 7 and 9; blocks 2, 5 and 8 are free:

flowchart LR
    D["dir entry: a.txt<br/>start = 4"] --> F4

    subgraph FAT["fat table"]
        direction LR
        F2["[2] FREE"]
        F4["[4] next = 7"]
        F5["[5] FREE"]
        F7["[7] next = 9"]
        F8["[8] FREE"]
        F9["[9] EOF"]
    end

    F4 --> F7 --> F9

The three basic operations

All three operations are just manipulations of this chain.

Lookup. Say we want byte offset 10000 of a.txt, with 4KB blocks. That is inside the 3rd block of the file, so we start at block 4 (from the directory entry) and follow the chain two hops: 4 → 7 → 9. Block 9 is the one we read. Note that we had to touch every entry on the way – there is no way to jump directly to the n-th block.

flowchart LR
    S["dir entry<br/>start = 4"] --> A["fat[4] = 7<br/>hop 1"] --> B["fat[7] = 9<br/>hop 2"] --> C["fat[9] = EOF<br/>read block 9"]

Insert. To append a new block to a.txt, we scan the table for a free entry (say block 5), then splice it in: fat[9] changes from EOF to 5, and fat[5] becomes the new EOF. Two writes to the table, done.

flowchart LR
    subgraph BEFORE["before"]
        direction LR
        A4["[4] next = 7"] --> A7["[7] next = 9"] --> A9["[9] EOF"]
        A5["[5] FREE"]
    end

    subgraph AFTER["after"]
        direction LR
        B4["[4] next = 7"] --> B7["[7] next = 9"] --> B9["[9] next = 5"] --> B5["[5] EOF"]
    end

    BEFORE -- "fat[9] = 5, fat[5] = EOF" --> AFTER

Delete. To delete a.txt, we walk the chain and mark every entry as FREE, then remove the directory entry. Notice that the data blocks themselves are never touched – only the table entries. This is why deleted files on a FAT disk are often recoverable: the chain is gone, but the data is still sitting there until the blocks get reused.

flowchart LR
    subgraph BEFORE2["before"]
        direction LR
        C4["[4] next = 7"] --> C7["[7] next = 9"] --> C9["[9] EOF"]
    end

    subgraph AFTER2["after"]
        direction LR
        D4["[4] FREE"]
        D7["[7] FREE"]
        D9["[9] FREE"]
    end

    BEFORE2 -- "walk the chain, free each entry" --> AFTER2

Directories

A directory in FAT is just a file whose data blocks contain directory entries. Each entry is a fixed sized record (32 bytes in the classic design) containing the name, attributes, size, and the starting block of the file. A path lookup is a linear scan of these entries, level by level.

What is good about it

• The design is simple. The whole file system can be implemented in a few thousand lines of code, which is why it is the default choice for embedded devices, boot loaders, and removable media.
• All the metadata is in one place (the fat table), which can be cached in memory for small file systems. Once cached, finding the next block of a file is a single array lookup.

What is wrong with it

• Locating a random offset inside a file requires traversing the chain from the beginning. For a large file, this linked-list traversal becomes expensive.
• The fat table grows linearly with the disk size, and the entry width limits the maximum file system size. This is the main reason it does not scale to file systems that span in TBs.
• No permissions, no ownership, no journaling.

These limitations are what motivated the inode based design, which we cover in the next post of this series.

Where we use it: SecureFS

The simplicity of FAT is not just of historical interest. In our SecureFS project, we built a secure FAT based file system for Intel SGX applications. Inside an SGX enclave, memory is a scarce resource, and every extra data structure you keep around has a cost. The compact metadata of a FAT design – a single table that can be kept entirely inside the enclave – makes it a good fit there, and integrity protecting one contiguous table is much simpler than protecting scattered inodes. The details of that design are on the SecureFS page.