8.3 filenames and cluster chains: how the DOS FAT file system worked

FAT is the file system everyone has used and almost nobody has read about. It formatted every DOS floppy and every pre-NT hard disk, and it never really went away: the USB stick in your drawer is almost certainly FAT32 or exFAT, so is your camera's SD card, and the EFI system partition your Mac or PC boots from is FAT by specification. Understanding FAT is also the fastest way to understand file systems in general, because it is the simplest design that actually works: a boot sector, one table, one directory format, and nothing else. This post walks the on-disk structures of FAT12 - the original - and then follows the family through FAT16, FAT32, long filenames, and exFAT.

Born on eight-inch floppies

The File Allocation Table predates DOS. Marc McDonald, Microsoft's first salaried employee, worked out the scheme with Bill Gates in 1977 and implemented it for Microsoft's Standalone Disk BASIC-80, which needed some way to keep named files on 8-inch floppies. In 1980 Tim Paterson adopted and reworked the idea - with 12-bit table entries - for 86-DOS at Seattle Computer Products, and when Microsoft bought 86-DOS and shipped it as PC DOS 1.0 in 1981, FAT12 became the file system of the IBM PC.

The design constraints explain everything that follows. A 1981 floppy held 160 KB; the machine reading it might have 64 KB of RAM. The file system had to be tiny, had to be traversable with almost no memory, and had to tolerate media you could bend. So FAT spends a single table on all of its bookkeeping, keeps a second copy of that table as its only concession to redundancy, and describes each file with one fixed 32-byte record. There are no permissions, no owners, and no journal - concepts that would have been meaningless on a single-user machine with a beeper for a security system.

The layout: four regions, in order

A FAT12 or FAT16 volume is laid out as four consecutive regions. On a standard 1.44 MB floppy (2,880 sectors of 512 bytes) they look like this:

1. Boot sector (sector 0). The first bytes are a jump instruction and then the BIOS Parameter Block- a little table declaring the volume's geometry: bytes per sector, sectors per cluster, number of FATs, root-directory entry count, total sectors. Everything else on the disk is found by arithmetic from these fields. The sector ends with the boot code and the famous 0x55 0xAA signature.
2. FAT #1 (9 sectors on our floppy) - the allocation table itself, described below.
3. FAT #2 - a byte-for-byte copy of FAT #1, written on every update. If a sector of the first table went bad, the data was not lost with it. This is the entire crash-resilience story of FAT: two copies of one structure, and good luck.
4. Root directory- a fixed-size array of 32-byte entries; 224 of them (14 sectors) on a 1.44 MB floppy. Fixed means fixed: a full root directory refused new files even with free space remaining. Subdirectories, added in DOS 2.0, are ordinary files containing the same 32-byte entries, so only the root had this limit.
5. Data area - everything remaining, divided into clusters of one or more sectors. Clusters are numbered starting at 2 (entries 0 and 1 of the table are reserved), which is why the first file on a fresh floppy starts at cluster 2, not 0.

The 32-byte directory entry

Every file and subdirectory is described by exactly 32 bytes. The layout, unchanged since 1981 (later versions filled in reserved bytes), is:

The 8+3 name field is where AUTOEXEC.BAT and README.TXT come from, and why a generation of software shipped with names like WP51.EXE. The packed timestamp is a small marvel of stinginess: 16 bits for the date (seven bits of year counted from 1980, four of month, five of day) and 16 for the time - five bits of hours, six of minutes, and five for seconds divided by two. FAT timestamps have two-second resolution because there was no room for the odd seconds. And the 32-bit size field is the reason a FAT32 stick still refuses any file of 4 GB or larger, in 2026.

The table itself: a linked list on disk

Notice what the directory entry does notcontain: any list of where the file's data lives, beyond the first cluster. That job belongs to the FAT, and its trick is worth savoring. The table has one entry per cluster in the data area - entry 7 corresponds to cluster 7 - and each entry holds simply the number of the next cluster in the file. The allocation table is a linked list, with the pointers stored apart from the data:

• 0x000 - cluster is free;
• any ordinary value - cluster is in use, and here is the next link;
• 0xFF8-0xFFF - end of chain (the file stops here);
• 0xFF7 - bad cluster, discovered by FORMAT or CHKDSK, never to be allocated.

Reading a file is therefore a walk: take the first cluster from the directory entry, read it, look up its FAT entry, go where it points, repeat until you hit an end-of-chain marker, and trim the final cluster with the size field. Free-space accounting needs no separate bitmap - count the zeros. Allocation is finding a zero and splicing it in. One structure does everything, and on a floppy the whole table (4.5 KB per copy) fit comfortably in RAM.

Here is the walk, on a miniature volume you can click:

The demo's fragmented GAME.EXEis the design's weakness made visible. Because each link is only found by reading the previous one, a badly fragmented file on a real disk meant a seek per hop - and the table gives you no way to ask "where are all my file's clusters?" without walking. Modern file systems store extents (start + length runs) precisely to avoid this.

Deleting a file barely did anything

When you ran DEL LETTER.TXT, DOS did two cheap things: it overwrote the first byte of the directory entry's name with the marker 0xE5("this slot is reusable"), and it walked the FAT chain setting each entry back to zero. That is all. The data clusters were not touched, and the rest of the directory entry - including the extension, the size, and crucially the first cluster number - remained in place.

This is why undelete tools were a whole product category, and why Norton Utilities made its name. UNERASE, and later DOS 5's own UNDELETE, found entries starting with 0xE5, asked you to supply the lost first letter, and then had to reconstruct the chain - which the zeroed FAT no longer recorded. The heuristic: assume the file was contiguous, start at the surviving first-cluster number, and claim free clusters forward until the size field was satisfied. On a lightly used disk, where files mostly were contiguous and nothing had overwritten the freed clusters, this worked shockingly often. Try it in the demo above: delete a file, note that its clusters merely change state, then recover it.

Fragmentation, and the defrag ritual

DOS allocated new clusters by scanning for the first free entry. On a fresh disk that yields tidy contiguous files; after months of creating, growing, and deleting, free clusters are scattered and every new file is shredded across the platter. The linked-list design means fragmentation costs you twice - once in head seeks between data clusters, and once because sequential reads become pointer chasing. Hence the great shared memory of the era: running DEFRAG (or Norton's SPEEDISK) and watching the little blocks reshuffle for an hour. A defragmenter is conceptually simple on FAT - move clusters so each chain is consecutive, rewrite the table - which is partly why so many existed.

FAT12 to FAT16 to FAT32: outgrowing the table, twice

Every jump in the family was forced by the same arithmetic: cluster addresses are fixed-width, so a volume can have only so many clusters, so bigger disks force either wider entries or bigger clusters.

• FAT12 (1980) - 12-bit entries, at most 4,084 clusters. Fine for floppies; hopeless for hard disks beyond a few dozen megabytes.
• FAT16(PC DOS 3.0, 1984) - 16-bit entries, up to 65,524 clusters, arriving with the PC/AT's hard disk. Other 16-bit fields still capped volumes at 32 MB until Compaq's DOS 3.31 (1987) widened the sector count, taking FAT16 to 2 GB - at the cost of 32 KB clusters, in which a 200-byte batch file consumed 32 KB of disk. That waste ("slack space") was the practical scandal of FAT16.
• FAT32(Windows 95 OSR2, 1996) - 32-bit entries of which 28 bits are used, lifting volumes to 2 TB and letting clusters shrink back to sane sizes. The root directory also finally became an ordinary cluster chain instead of a fixed array. The 4 GB file-size ceiling, however, is baked into the 32-byte directory entry and stayed.

The long-filename hack, and exFAT

Windows 95 needed Letter to Grandma.docon a file system whose directory entry physically holds eleven characters. Microsoft's solution, VFAT long filenames, is a beloved dirty trick: store the long name in extra 32-byte directory entries placed before the real one, each carrying 13 UTF-16 characters, a sequence number, and a checksum of the short name. The genius is the attribute byte: LFN entries are marked 0x0F - read-only + hidden + system + volume-label simultaneously - a combination so nonsensical that DOS and every existing tool silently ignored the entries instead of choking. Old systems saw LETTER~1.DOC; new ones reassembled the long name. Full backward and forward compatibility, achieved with a bit pattern.

exFAT(2006, built for flash media and made the mandatory format for SDXC cards) is the family's modernization: 64-bit file sizes, a real free-space bitmap so allocation no longer scans the table, and optional contiguous-file flags that skip chain walking entirely. It kept the name and the licensing but is structurally a different, simpler-than-NTFS animal. Microsoft published the full specification in 2019, and Linux gained a native driver soon after.

What FAT never had

FAT's omissions define modern file systems by contrast. No ownership or permissions - any process could touch any byte. No journaling or copy-on-write: interrupt a write at the wrong moment and the two FAT copies could disagree, orphaning chains (CHKDSK's famous FILE0001.CHKfiles were exactly these recovered orphans). No checksums, no snapshots, no hard links, no atomic anything. Those are the problems that HFS+, NTFS, ext4, and eventually APFS were built to solve - we walk through how your Mac's current file system handles them in APFS explained. And yet: a file manager listing a directory today performs the same conceptual acts as DOS did in 1981 - read entries, resolve names, walk allocation metadata - just against structures a thousand times more elaborate, which is a large part of why doing it fast still takes engineering care (that story is in What makes a file manager fast?, and it is the problem Shuffle exists to solve). For the fuller arc from CP/M to today, see our history of the file manager.

Forty-five years on, FAT survives for the same reason it was invented: it is small enough to implement anywhere, simple enough to get right, and every device on earth can read it. Not bad for a scheme sketched for a BASIC interpreter in 1977.