Overview

FAT (File Allocation Table), introduced in DOS v1.0, is a minimalist file system with low overhead, remaining one of the most prevalent storage formats. It uses a flat cluster array model for media access, with variations tailored to different storage scales.

Evolution of FAT Variants

FAT variants evolved to address expanding storage needs:

• FAT12: Designed for floppy disks, using 12-bit addressing to manage up to 16MB via 4096 clusters.
• FAT16: Targeted early hard drives, supporting larger volumes but suffering from slack space due to growing cluster sizes (up to 64KB per cluster).
• FAT32: Introduced in Windows 95-B/98, resolving cluster size limits. It uses 28 effective bits (of 32) per FAT entry, enabling ~270 million clusters per partition—maintaining small clusters for large drives.
• ExFAT: Developed by Microsoft for SDXC cards, featuring full 32-bit FAT entries, contiguous file optimization, and advanced metadata handling.
• VFAT: A FAT extension for long filenames (up to 255 chars) in Windows 95, storing names across sequential directory entries marked with volume attributes.

Storage Layout

FAT organizes media into three core regions:

1. Boot Record: First logical sector, containing boot code, partition info, and filesystem parameters.
2. File Allocation Table (FAT): Tracks cluster status (free, reserved, bad, allocated) and chains for file fragments.
3. Directory & Data Area: Stores file/directory entries and actual file data.

On legacy media (e.g., old floppies), cluster numbers require conversion to physical sectors before disk access, handled by filesystem drivers.

Boot Record

The boot record (boot sector/MBR) resides at logical sector 0 (or partition start). It includes:

• Boot code to initialize hardware and load the OS kernel.
• Partition table describing disk layout.
• Boot flag indicating sector validity.

File Allocation Table (FAT)

FAT maps cluster states and links file fragments. For FAT32, each entry uses 28 bits (upper 4 reserved) to address clusters. ExFAT uses full 32 bits. A cluster chain terminates when the entry value ≥ 0x0FFFFFF8 (or 0xFFFFFFF8 for exFAT). Bad clusters are marked 0x0FFFFFF7 (0xFFFFFFF7 for exFAT). Entries 0 and 1 are reserved (entry 0 mirrors the BPB media descriptor; entry 1 is unused, set to 0xFFFFFFFF).

Reading a FAT Entry (C Example):

#define SECTOR_SIZE 512
#define FAT32_EOC 0x0FFFFFF8
#define FAT32_BAD_CLUSTER 0x0FFFFFF7

unsigned char fat_buffer[SECTOR_SIZE];
unsigned int current_cluster = 123; // Example cluster index
unsigned int first_fat_sec = 2;      // First FAT sector location

// Calculate byte offset in FAT table
unsigned int cluster_byte_offset = current_cluster * sizeof(unsigned int);
// Determine target FAT sector and entry position within sector
unsigned int target_fat_sec = first_fat_sec + (cluster_byte_offset / SECTOR_SIZE);
unsigned int entry_byte_pos = cluster_byte_offset % SECTOR_SIZE;

// Read sector 'target_fat_sec' into fat_buffer (pseudo-code)
// disk_read(target_fat_sec, fat_buffer, SECTOR_SIZE);

// Extract entry value (little-endian assumption)
unsigned int* entry_ptr = (unsigned int*)(fat_buffer + entry_byte_pos);
unsigned int raw_value = *entry_ptr;
// Mask upper 4 bits for FAT32
unsigned int cluster_link = raw_value & 0x0FFFFFFF;

// Interpret link
if (cluster_link >= FAT32_EOC) {
    // End of chain
} else if (cluster_link == FAT32_BAD_CLUSTER) {
    // Bad cluster
} else {
    // Next cluster in chain: cluster_link
}

Programming Guide: Reading the Boot Sector

The boot sector (logical sector 0) contains critical filesystem parameters. Define structures to parse its contents:

typedef struct {
    unsigned int fat32_table_size;    // FAT32 table size in sectors
    unsigned short ext_flags;         // Extended flags
    unsigned short fat_version;       // FAT version
    unsigned int root_cluster;        // Root directory cluster (FAT32)
    unsigned short fat_info_sec;      // FSInfo sector index
    unsigned short backup_bs_sec;     // Backup boot sector index
    unsigned char reserved[12];       // Reserved bytes
    unsigned char drive_num;          // Drive number
    unsigned char reserved1;          // Reserved
    unsigned char boot_sig;           // Boot signature (0x29)
    unsigned int volume_id;           // Volume serial number
    unsigned char volume_label[11];   // Volume label (ASCII)
    unsigned char fs_type_label[8];   // Filesystem type string
} __attribute__((packed)) Fat32ExtendedBootSec;

typedef struct {
    unsigned char bios_drive;          // BIOS drive number
    unsigned char reserved1;          // Reserved
    unsigned char boot_sig;           // Boot signature (0x29)
    unsigned int volume_id;           // Volume serial number
    unsigned char volume_label[11];   // Volume label (ASCII)
    unsigned char fs_type_label[8];   // Filesystem type string
} __attribute__((packed)) Fat16ExtendedBootSec;

typedef struct {
    unsigned char jump_instr[3];      // Boot jump instruction
    unsigned char oem_id[8];          // OEM identifier
    unsigned short bytes_per_sec;     // Bytes per sector
    unsigned char sec_per_cluster;     // Sectors per cluster
    unsigned short reserved_sec_cnt;  // Reserved sectors count
    unsigned char fat_copies;          // Number of FAT copies
    unsigned short root_dir_entries;  // Root directory entries (FAT12/16)
    unsigned short total_sec_16;      // Total sectors (16-bit)
    unsigned char media_desc;          // Media descriptor
    unsigned short fat_size_16;        // FAT size (16-bit, FAT12/16)
    unsigned short sec_per_track;      // Sectors per track
    unsigned short heads_count;        // Number of heads
    unsigned int hidden_sec_cnt;      // Hidden sectors count
    unsigned int total_sec_32;        // Total sectors (32-bit)
    unsigned char ext_data[54];        // Extended data (cast to variant-specific struct)
} __attribute__((packed)) FatBootSector;