File Allocation Table - FAT File System | OneNoughtOne

0/236

Operating SystemsFile System Structures

FAT File System

LevelIntermediate

Duration60 mins

TopicFile System Structures

1 / 5

File Allocation Table

The Foundation of Personal Computing Storage

In 1977, a young programmer named Marc McDonald sat down at Microsoft to solve a critical problem: how should floppy disks organize their data? The solution he created, refined by Bill Gates, would become the File Allocation Table (FAT) file system—a design so successful it remains in active use nearly fifty years later.

FAT isn't just a piece of computing history; it's a masterclass in elegant simplicity. From USB flash drives to SD cards, from digital cameras to car navigation systems, FAT continues to serve as the universal language of removable storage. Understanding FAT means understanding the fundamental principles that underpin all modern file systems.

What You Will Learn

By the end of this page, you will understand the core architecture of the File Allocation Table, how it maps files to disk locations, the ingenious design decisions that made FAT both simple and robust, and why this 1977 design continues to influence computing today.

The Problem FAT Solves

Before we dive into FAT's mechanics, we must understand the fundamental problem it addresses. Consider a disk drive—whether a floppy disk from 1977 or a modern USB drive.

The core challenge: A disk contains millions (or billions) of fixed-size storage units. Files, however, have variable sizes. A text document might be 2 KB, a photograph 5 MB, a video 2 GB. How do we:

Divide the disk into manageable units?
Track which units belong to which file?
Allow files to grow, shrink, or be deleted?
Find files efficiently?
Recover when things go wrong?

The Design Constraints of 1977

FAT was designed for systems with 64 KB of RAM, 4 MHz processors, and floppy disks holding 160 KB. Every byte of metadata was precious. Every CPU cycle mattered. These constraints forced a simplicity that, paradoxically, became FAT's greatest strength—making it portable, understandable, and remarkably robust.

The naive approaches and their problems:

Approach 1: Store files contiguously

Place each file in consecutive disk sectors
Problem: What happens when a file grows? You'd need to relocate the entire file.
Problem: External fragmentation—after deletions, you have gaps too small for new files.

Approach 2: Simple linked list in each sector

Each sector contains a pointer to the next sector
Problem: To read the last byte of a file, you must read every sector before it.
Problem: One corrupted pointer destroys access to the remainder of the file.

FAT combines the best of both worlds: linked allocation (flexibility) with separated metadata (reliability and random access).

Core Concepts: Clusters and Sectors

Understanding FAT requires grasping its fundamental units of storage: sectors and clusters.

Sectors: The Physical Unit

A sector is the smallest unit the disk hardware can read or write—typically 512 bytes on traditional drives, though modern drives often use 4,096 bytes (4K sectors). The operating system cannot read half a sector; it's all or nothing.

Clusters: The Logical Unit

A cluster (also called an "allocation unit") is FAT's fundamental unit for file storage—a group of consecutive sectors treated as a single unit. The file system tracks which clusters belong to which files.

Why clusters instead of individual sectors?

Cluster Size Trade-offs
Consideration	Small Clusters (e.g., 512B)	Large Clusters (e.g., 32KB)
Space efficiency	Minimal waste per file	Up to 31KB wasted per small file
FAT table size	Many entries → large FAT table	Fewer entries → compact FAT table
Fragmentation tracking	More entries to traverse	Fewer entries to traverse
Maximum volume size	Limited by FAT entry count	Larger volumes supported
Read/write overhead	More disk operations	Better throughput for large files

The slack space problem:

Consider a 4 KB cluster size. If you save a file containing a single character (1 byte):

The file occupies 1 byte of data
The file is allocated 1 cluster = 4,096 bytes of disk space
4,095 bytes are wasted (called "slack space" or "cluster slack")

This is the fundamental trade-off: larger clusters reduce metadata overhead but increase slack space. FAT implementations choose cluster sizes based on volume size, typically following these guidelines:

Typical FAT32 Cluster Sizes

Cluster Sizing

Volume Size           Cluster Size    Max Clusters
--------------------- --------------- ---------------
< 8 GB                512 bytes       ~16 million
8 GB - 16 GB          4 KB            ~4 million
16 GB - 32 GB         8 KB            ~4 million
32 GB - 2 TB          16 KB           ~134 million
> 2 TB                32 KB           ~268 million
 
Note: Maximum cluster count limited by FAT32's 
28-bit cluster addressing (~268 million clusters).
Cluster size automatically selected during formatting.

Cluster Numbering

Clusters are numbered starting from 2 (not 0 or 1). Cluster numbers 0 and 1 are reserved for special purposes in the FAT table. This seemingly arbitrary choice actually simplifies certain edge-case handling and maintains backward compatibility with the original FAT design.

The File Allocation Table Itself

The File Allocation Table is the heart of the FAT file system—a simple but powerful data structure that maps the entire disk's cluster usage.

Conceptual Design:

Imagine a simple array where:

The index is a cluster number (2, 3, 4, ...)
The value indicates either:
- The next cluster in the file's chain, or
- A special marker (end of file, bad cluster, free cluster)

This is the File Allocation Table: an array of cluster chain pointers.

FAT Table Conceptual Representation
Concept
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// The FAT is conceptually an array:
// FAT[cluster_number] = next_cluster_or_special_value
 
// Special values (example for FAT16):
FREE_CLUSTER    = 0x0000     // Cluster is available
RESERVED        = 0x0001     // Reserved by system
BAD_CLUSTER     = 0xFFF7     // Cluster has bad sectors
END_OF_CHAIN    = 0xFFF8-0xFFFF  // Last cluster of file
 
// Example FAT table contents:
// Cluster 2: 0x0003  → Next cluster is 3
// Cluster 3: 0x0004  → Next cluster is 4  
// Cluster 4: 0xFFFF  → End of chain (last cluster)
// Cluster 5: 0x0000  → Free cluster
// Cluster 6: 0xFFF7  → Bad cluster (avoid using)
// Cluster 7: 0x0008  → Next cluster is 8
 
// This represents:
// - A file using clusters 2 → 3 → 4 (3 clusters)
// - Free space at cluster 5
// - A defective area at cluster 6
// - Another file starting at cluster 7

Visual Representation:

Let's trace how a file named "document.txt" spanning clusters 10, 12, and 7 is represented:

Converting Mermaid diagram...

Why separate the FAT from the data?

This separation is FAT's key insight. By keeping all cluster chain information in one contiguous table:

Random access is possible: To find the 100th cluster of a file, traverse the FAT (in memory) without reading data clusters.
Reliability improves: FAT is typically stored in duplicate. If one copy corrupts, the other provides recovery.
Caching is efficient: The entire FAT can be loaded into memory for fast access, even on systems with limited RAM.
File operations are fast: Deleting a file means zeroing FAT entries—no need to touch actual data clusters.

FAT Fragmentation Impact

Because file clusters can be scattered anywhere on disk, a fragmented file requires traversing the FAT chain and seeking to each cluster's physical location. This is why FAT-formatted drives benefit significantly from defragmentation—contiguous clusters mean sequential disk reads.

Disk Layout and Boot Sector

A FAT-formatted volume has a precise layout. Understanding this structure is essential for file system implementation, data recovery, and forensic analysis.

Volume Structure (from beginning to end):

FAT Volume Layout
Region	Size	Purpose
Boot Sector	1 sector (512B)	BIOS Parameter Block + boot code
Reserved Area	Variable (FAT32: 32 sectors)	Additional boot code, FS info
FAT #1	Depends on volume size	Primary File Allocation Table
FAT #2	Same as FAT #1	Backup File Allocation Table
Root Directory	Fixed size (FAT12/16 only)	Root directory entries
Data Region	Remainder of volume	File and directory data clusters

The Boot Sector (BIOS Parameter Block):

The boot sector contains critical metadata that defines the file system. Without this information, reading the volume is impossible:

FAT Boot Sector Structure
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// BIOS Parameter Block (BPB) - Common to all FAT types
typedef struct __attribute__((packed)) {
    uint8_t  jmpBoot[3];        // Jump instruction to boot code
    uint8_t  oemName[8];        // OEM identifier (e.g., "MSDOS5.0")
    
    // BIOS Parameter Block
    uint16_t bytesPerSector;    // Usually 512
    uint8_t  sectorsPerCluster; // 1, 2, 4, 8, 16, 32, 64, or 128
    uint16_t reservedSectors;   // Sectors before first FAT
    uint8_t  numberOfFATs;      // Usually 2 (for redundancy)
    uint16_t rootEntryCount;    // FAT12/16: max root entries (0 for FAT32)
    uint16_t totalSectors16;    // Total sectors (if < 65536)
    uint8_t  mediaType;         // 0xF8 = fixed disk, 0xF0 = removable
    uint16_t sectorsPerFAT16;   // FAT12/16: sectors per FAT table
    uint16_t sectorsPerTrack;   // Disk geometry (legacy)
    uint16_t numberOfHeads;     // Disk geometry (legacy)
    uint32_t hiddenSectors;     // Sectors before partition
    uint32_t totalSectors32;    // Total sectors (if >= 65536)
    
    // Extended Boot Record (FAT12/16) or FAT32 extension follows
} BPB_Common;
 
// Example values for a typical USB drive:
// bytesPerSector    = 512
// sectorsPerCluster = 8      (4 KB clusters)
// reservedSectors   = 32     (FAT32 standard)
// numberOfFATs      = 2      (primary + backup)
// totalSectors32    = 15728640  (8 GB volume)

Critical Calculations from Boot Sector:

Given the boot sector parameters, we can compute everything needed to navigate the file system:

FAT Layout Calculations
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
// Calculate key file system locations
 
// Size of the FAT region
uint32_t fatSize = (bpb->sectorsPerFAT16 != 0) 
    ? bpb->sectorsPerFAT16 
    : bpb32->sectorsPerFAT32;
 
// First sector of the FAT
uint32_t fatStartSector = bpb->reservedSectors;
 
// First sector of root directory (FAT12/16 only)
uint32_t rootDirStart = fatStartSector + 
    (bpb->numberOfFATs * fatSize);
 
// Size of root directory in sectors (FAT12/16 only)
uint32_t rootDirSectors = ((bpb->rootEntryCount * 32) + 
    (bpb->bytesPerSector - 1)) / bpb->bytesPerSector;
 
// First sector of data region
uint32_t dataStart = rootDirStart + rootDirSectors;
 
// Convert cluster number to sector number
uint32_t clusterToSector(uint32_t cluster) {
    return dataStart + 
        ((cluster - 2) * bpb->sectorsPerCluster);
}
 
// Total data clusters (determines FAT type!)
uint32_t totalDataSectors = totalSectors - dataStart;
uint32_t totalClusters = totalDataSectors / 
    bpb->sectorsPerCluster;
 
// FAT type is determined SOLELY by cluster count:
// totalClusters < 4085      → FAT12
// totalClusters < 65525     → FAT16
// totalClusters >= 65525    → FAT32

FAT Type Detection

Contrary to popular belief, the FAT type (12, 16, or 32) is NOT stored in the boot sector. It is determined by counting the total data clusters. This means a volume with fewer than 4,085 clusters is always FAT12, regardless of any labels or file system indicators.

FAT Table Operations

Understanding how to read and manipulate the FAT table is fundamental to implementing or recovering FAT file systems. Let's examine the core operations.

Reading a Cluster Chain:

To read an entire file, we follow its cluster chain:

Reading a File via FAT Chain
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
// Read all clusters of a file given its first cluster
int readFile(uint32_t firstCluster, uint8_t *buffer, 
             size_t maxSize) {
    uint32_t cluster = firstCluster;
    size_t bytesRead = 0;
    size_t clusterBytes = bytesPerSector * sectorsPerCluster;
    
    while (!isEndOfChain(cluster) && bytesRead < maxSize) {
        // Validate cluster number
        if (cluster < 2 || cluster >= totalClusters + 2) {
            return -1;  // Invalid cluster reference
        }
        
        // Calculate physical sector
        uint32_t sector = clusterToSector(cluster);
        
        // Read cluster data
        if (readSectors(sector, sectorsPerCluster, 
                       buffer + bytesRead) < 0) {
            return -1;  // Disk read error
        }
        
        bytesRead += clusterBytes;
        
        // Get next cluster from FAT
        cluster = getFATEntry(cluster);
    }
    
    return bytesRead;
}
 
// Check if cluster value indicates end of chain
bool isEndOfChain(uint32_t cluster) {
    // End-of-chain markers vary by FAT type:
    // FAT12: >= 0x0FF8
    // FAT16: >= 0xFFF8
    // FAT32: >= 0x0FFFFFF8
    return cluster >= endOfChainMarker;
}

Allocating Clusters for a New File:

When creating or extending a file, we must find and link free clusters:

Cluster Allocation Algorithm
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
// Allocate N clusters for a file, return first cluster
// Returns 0 on failure (no space)
uint32_t allocateClusters(int count) {
    uint32_t firstCluster = 0;
    uint32_t prevCluster = 0;
    int allocated = 0;
    
    // Search for free clusters
    // (In practice, start from lastAllocatedCluster for efficiency)
    for (uint32_t c = 2; c < totalClusters + 2 && allocated < count; c++) {
        if (getFATEntry(c) == FREE_CLUSTER) {
            // Mark cluster as end-of-chain (for now)
            setFATEntry(c, END_OF_CHAIN);
            
            if (firstCluster == 0) {
                firstCluster = c;  // Remember first cluster
            } else {
                // Link previous cluster to this one
                setFATEntry(prevCluster, c);
            }
            
            prevCluster = c;
            allocated++;
        }
    }
    
    if (allocated < count) {
        // Failed to allocate enough - rollback
        freeClusterChain(firstCluster);
        return 0;  // Disk full
    }
    
    // Update the free cluster count (FAT32)
    if (fsInfo != NULL) {
        fsInfo->freeClusterCount -= allocated;
        fsInfo->lastAllocated = prevCluster;
    }
    
    return firstCluster;
}

Deleting a File:

File deletion in FAT is remarkably simple—and this simplicity has important implications for data recovery:

File Deletion Process
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
// Delete a file - FREE its clusters
int deleteFile(DirectoryEntry *entry) {
    // Step 1: Mark directory entry as deleted
    // (First byte of filename set to 0xE5)
    entry->name[0] = DELETED_MARKER;  // 0xE5
    
    // Step 2: Free the cluster chain
    uint32_t cluster = getFirstCluster(entry);
    freeClusterChain(cluster);
    
    // Step 3: Write updated directory entry
    writeDirectoryEntry(entry);
    
    return 0;
}
 
// Free all clusters in a chain
void freeClusterChain(uint32_t firstCluster) {
    uint32_t cluster = firstCluster;
    uint32_t freedCount = 0;
    
    while (cluster >= 2 && cluster < totalClusters + 2 && 
           !isEndOfChain(cluster)) {
        uint32_t nextCluster = getFATEntry(cluster);
        setFATEntry(cluster, FREE_CLUSTER);  // Mark as free
        cluster = nextCluster;
        freedCount++;
    }
    
    // Handle last cluster in chain
    if (cluster >= 2 && cluster < totalClusters + 2) {
        setFATEntry(cluster, FREE_CLUSTER);
        freedCount++;
    }
    
    // Update free cluster count
    if (fsInfo != NULL) {
        fsInfo->freeClusterCount += freedCount;
    }
}

Data Recovery Implication

Notice that deletion does NOT erase the actual data—it only marks clusters as free and flags the directory entry. Until those clusters are reused, the data remains on disk. This is why file recovery tools can often restore deleted files from FAT volumes, and why secure deletion requires overwriting the actual cluster data.

FAT Table Redundancy and Recovery

The FAT file system maintains two identical copies of the File Allocation Table. This redundancy is a critical reliability feature, especially important given FAT's original use on floppy disks—notoriously unreliable media.

Why Two FATs?

Benefits of FAT Redundancy

•Corruption Recovery — If a sector in the primary FAT becomes unreadable, the backup FAT provides an alternative data source.
•Media Defect Tolerance — Floppy disks were prone to developing bad sectors. Having the FAT in two locations doubles the chance of survival.
•Verification — Disk utilities can compare both FATs to detect inconsistencies indicating corruption.
•Simple Implementation — The backup is a byte-for-byte copy, requiring no complex mirroring logic.

Synchronization Behavior:

The two FATs must remain synchronized. When the operating system modifies the FAT:

FAT Synchronization
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
// Write a FAT entry - updates BOTH copies
void setFATEntry(uint32_t cluster, uint32_t value) {
    // Calculate offset within FAT
    uint32_t offset;
    switch (fatType) {
        case FAT12:
            offset = cluster + (cluster / 2);  // 1.5 bytes per entry
            break;
        case FAT16:
            offset = cluster * 2;  // 2 bytes per entry
            break;
        case FAT32:
            offset = cluster * 4;  // 4 bytes per entry
            break;
    }
    
    // Calculate which sector(s) of FAT to modify
    uint32_t fatSector = offset / bytesPerSector;
    uint32_t sectorOffset = offset % bytesPerSector;
    
    // Read the FAT sector, modify entry, write back
    // Do this for BOTH FAT copies
    for (int fatNum = 0; fatNum < numberOfFATs; fatNum++) {
        uint32_t sector = fatStartSector + 
            (fatNum * sectorsPerFAT) + fatSector;
        
        uint8_t sectorBuffer[SECTOR_SIZE];
        readSector(sector, sectorBuffer);
        
        // Write value at appropriate position
        writeValueToBuffer(sectorBuffer, sectorOffset, 
                          value, fatType);
        
        writeSector(sector, sectorBuffer);
    }
}
 
// Recovery: Use backup FAT if primary is corrupted
int repairFromBackupFAT() {
    // Read both FATs and compare
    for (uint32_t sector = 0; sector < sectorsPerFAT; sector++) {
        uint8_t primary[SECTOR_SIZE], backup[SECTOR_SIZE];
        
        readSector(fatStartSector + sector, primary);
        readSector(fatStartSector + sectorsPerFAT + sector, backup);
        
        if (memcmp(primary, backup, SECTOR_SIZE) != 0) {
            // FATs differ - check which is correct
            if (!verifySectorIntegrity(primary)) {
                // Primary is corrupt, use backup
                writeSector(fatStartSector + sector, backup);
                printf("Restored FAT sector %d from backup
", sector);
            }
        }
    }
    return 0;
}

Modern Considerations

On modern solid-state storage, the reliability concern that justified dual FATs is less pressing—flash memory has its own error correction. However, the dual-FAT design remains in the specification for compatibility. Some systems (particularly embedded) may only use a single FAT to save space, setting numberOfFATs to 1.

Summary: The Elegance of FAT

The File Allocation Table represents a masterclass in simple, effective design. Let's consolidate what we've learned:

Key Takeaways

•The FAT is a cluster chain map — A simple array where each entry points to the next cluster of a file, enabling linked allocation without embedding pointers in data blocks.
•Clusters balance efficiency vs. metadata size — Larger clusters reduce FAT table size but increase slack space; cluster size is chosen based on volume size.
•Separating metadata from data enables recovery — The FAT can be cached, duplicated, and verified independently of file contents.
•Volume layout is deterministic — Boot sector → Reserved → FAT × 2 → Root Directory → Data Region. Every calculation derives from boot sector parameters.
•Operations are straightforward — Allocate by finding free entries, delete by marking entries free, read by following the chain.
•Redundancy provides resilience — Dual FAT copies protect against media failures and enable corruption recovery.

What's next:

Now that we understand the FAT's core architecture, we'll explore the variants of FAT—FAT12, FAT16, and FAT32. Each evolved to address the storage limitations of its era, and understanding their differences reveals both the history of personal computing and the engineering trade-offs that shaped each design.

Page Complete

You now understand the fundamental architecture of the File Allocation Table—the simple yet powerful data structure that has organized billions of storage devices since 1977. Next, we'll examine how FAT12, FAT16, and FAT32 each adapted this core design for different eras of computing.