File Allocation Table

File Allocation Table (FAT) is the main file system developed for MS-DOS and Windows. The FAT file system is considered relatively uncomplicated, and because of that it is popular format for floppy disks; moreover, it is supported by virtually all existing operating systems for the IBM PC, and because of that it's often used to share data between several operating systems booting on the same computer (a multiboot environment). It is also used on solid-state memory sticks and other similar devices.

FAT is a relatively early file system design, and its designers did not exploit what was known about file system design, and because of that it suffered from several problems. First, its simple file layout allows for fragmentation, which leads to significant slowdowns during file system operations. Secondly, FAT was not designed for redundancy in the case of system failure. Thirdly, the first versions of FAT allowed file name sizes of only up to 11 characters (file name of 8 and a file extension of 3), although a work-around was developed when Microsoft implemented VFAT, that would allow file names of up to 255 characters. Finally, the large cluster size in many versions of FAT meant that a lot of space was being wasted on padding small files to the cluster size.

However, because IBM designated MS-DOS as its primary operating system for its PC, and MS-DOS used FAT, FAT became widely used and is still used in a number of circumstances. Because of its primitive design, it is easy to implement a basic FAT implementation, and because of the ubiquity of MS-DOS and Windows, FAT has become useful in providing a base level of interoperability in some circumstances.

Table of contents

1 FAT file system structure
2 FAT history
3 FAT licensing
4 External link

FAT file system structure

A FAT file system on a partition consists of the following parts:

The partition boot record, consisting of one or several sectors in the beginning of the disk, which include some basic file system information (in particular, its type), and the operating system's boot loader code
The File Allocation Table is a linked list that stores the logical order of the disk's clusters. Clusters are small blocks of contiguous and related space in the data area. Clusters are tied into chains that represent files. These chains are not necessarily stored adjacently on the disk's surface but are instead fragmented throughout the data area. Each file record, or inode, (discussed below) contains the location of the file's first cluster. Each entry in the FAT contains the location of the next logical cluster. The number of bits used to address the clusters determine the FAT size. Common FAT sizes are 12, 16 and 32 bits. The FAT actually exists as one or more (usually 2) identical copies, kept as redundancies to prevent accidental data loss.
The root directory for the partition (which has a maximal size, written inside the boot record) contains records for files and subdirectories inside it. The records, or inodes, for each file include names, first disk cluster, creation dates, file attributes and so on.
The data area is where file data and inodes are stored and takes up most of the partition. It is divided into small units of space called clusters. The size of files and subdirectories can be increased arbitrarily (as long as there are free clusters) by simply adding more links to the file's chain in the FAT. Note, however, that each cluster can be taken only by one file, and so if a 20-byte file resides in a 32,768-byte cluster, 32,748 bytes are wasted.

In order to store long file names (LFN) on a FAT file system, Windows 95 and above use a trick - adding phoney file records into the directory tables. The records are marked with attributes that are impossible for a regular file and because of that they're ignored by most old MS-DOS programs that access FAT directly. Each phoney record can contain up to 13 UCS-2 characters (26 bytes), gaining about 15 bytes in addition to the old 8 + 3 by using fields in the record where normal records contain file size and cluster number.

FAT history

FAT as it is known today made its debut in 1980 with the first version of QDOS, the ancestor of Microsoft's PC-DOS and MS-DOS. Initially it did not even support subdirectories. MS-DOS version 2 added support for subdirectories. Since FAT was intended for use mainly on floppy disks, in order to save on space, 12-bit cluster numbers were used, resulting in a maximum of 2¹² = 4,096 clusters. Clusters at that time were usually 512 bytes big, meaning the floppy could hold up to 2 megabytes - which was enough at the time. File names were built according to the 8 + 3 pattern. This initial version of FAT became known as FAT12.

In 1983 (since version 2) DOS also supported FAT with 16-bit cluster numbers, for the naturally larger hard disk drives. That way, there could be up to 2¹⁶ = 65,536 clusters. Even with 512-byte clusters, this could give up to 32 megabytes - enough for XT hard drives, either 10 or 20 megabytes in size. This version of FAT is known simply as FAT, or FAT16 (in the newer documents).

As hard drives grew in size, however, 512-byte clusters were not enough, and bigger sizes were used. 65,536 8,192-byte clusters (512 megabytes) were sufficient for the 400 megabyte disks which were standard issue when Windows 95 was released. However, one of the user experience goals that the designers of Windows 95 wanted to achieve was the use of long file names in the new operating system. The long file names were implemented using a work-around in the way FAT tables are laid out (see above). The new version of the file system became known as VFAT (Virtual FAT), after the Windows 95 VxD (device driver) that's used by the operating system to work with it. VFAT is supported by Windows 95 and above and Windows NT 4.0 and above.

By 1997, the cluster growth possibility was exhausted. The maximum cluster size in Windows FAT was 32,768 bytes (Windows NT could create partitions with clusters of 65,536 bytes, which could be used by Windows 95, but this was wasteful when keeping small files in mind, and did not solve the broader issue). For the next release of Windows, Microsoft decided to implement a newer generation of FAT, which 32-bit cluster numbers (only 28 bits are currently used, giving a total of 2²⁸ = 268,435,456 clusters. In these conditions, cluster sizes could be lowered again to 4,096 bytes, giving the (so far) adequate figure of 1 terabyte for the whole file system. As a further bonus, lower cluster size meant space was utilized more efficiently. In addition, several changes were made to other filesystem structures. The new FAT version became known as FAT32. This version is supported in Windows 95 OSR 2 and above, and Windows 2000 and above.

The alternative IBM PC operating systems, for example OS/2, Linux, FreeBSD, and BeOS, have all supported FAT, and most have gained support for VFAT and FAT32 shortly after the appropriate Windows versions were released. Early Linux distributions also supported a format known as UMSDOS, which was nothing more than FAT with the UNIX file properties (e.g. long file name and access permissions) stored in a separate file called --linux-.---. UMSDOS was mostly dropped after VFAT was released, although it still remains in the Linux kernel sources.

Since Microsoft has announced the discontinuation of the DOS line of succession with Windows ME, it remains unlikely that any new versions of FAT appear. For most purposes, the NTFS file system that was developed for the Windows NT line is superior to FAT from the points of view of efficiency, performance and reliability. However, FAT is likely to stay for a long time, both as the file system for the lower-end versions of Windows (currently, XP Personal), as well as the ideal file system for small drives, like the floppies.

FAT licensing

Although technical details of the FAT file system derive from CP/M and have been widely known and widely disseminated in the PC community for many years, and although the file system itself is widely considered to be obsolete, it should be noted that in 2003 Microsoft made a point of asserting intellectual property claims to the system. Citing patents, Microsoft claimed that licensing fees are required for its use in such applications as removable solid state media, and consumer devices using such media.

This claim by Microsoft is controversial, for a number of reasons. Microsoft itself has admitted that it developed its first FAT file system in 1976, so no patents could apply to an implementation of the original version. Copyright law could not prevent a re-implementation of FAT either.

Microsoft has cited 4 patents, dating from 1995 on, for FAT. All of these patents relate to storing both long and short filenames in a single file system. A Slashdot discussion on December 4, 2003, analyzed these patents and participants (particularly Svartalf) reported the following:

Patent 5,579,517 - Common name space for long and short filenames. Filed for on April 24, 1995. This appears to only impact someone using a Common Name Space for long and short filenames. This is the scheme Microsoft deployed for "Chicago" (the codename of Windows 95 while in development). This patent is likely to be invalidated (if challenged) by Microsoft's prior art release of Chicago to the world in December 1993.
Patent 5,745,902 - Method and system for accessing a file using file names having different file name formats. Filed for on July 6, 1992. This patents allowing renaming of just the name and preserving the extension for the purposes of keeping track of the filetype. It is unclear that other implementors would need to implement this patent to implement a FAT system.
Patent 5,758,352 - Common name space for long and short filenames. Filed on September 5, 1996. This is extremely similar to the 5,579,517 Patent; see those comments.
Patent 6,286,013 - Method and system for providing a common name space for long and short file names in an operating system. Filed on January 28, 1997. This is a detailed description of how Windows 95/98/Me handles long filenames on an x86-32 platform. It is unclear this patent would apply to anything other than an exact clone of Windows 95/98/Me. This patent is likely to be invalidated (if challenged) by Microsoft's prior art release of Windows 95, two years before the filing date,

In addition, there also seems to be prior art for at least the first, third, and forth patents in the Rock Ridge Interchange Protocol standard for UNIX, which was an IEEE draft specification on at least July 13th, 1993. This protocol defined a method to support long and short names on the same media (as well as additional information) to support Unix systems.

And of course, there is the simple question if this is really an innovative idea at all. Patents are supposed to be granted for new ideas; the notion of not removing short names, but adding long name information as well, is an option that is immediately obvious to any practitioner in the field.

In short, many have concluded that these patents only cover implementations that include support for long filenames, so it likely that removable solid state media and consumer devices only using short names would be unaffected. Also, there is good reason to believe the patents would be found invalid or unnecessary if challenged. In particular, many or all such patents are believed by many to be invalid because of previous public release, prior art, or because the technique would be obvious to a practioner.

None of this may impact operating system or firmware implementations. In the document "Microsoft Extensible Firmware Initiative FAT 32 File System Specification, FAT: General Overview of On-Disk Format" by Microsoft (version 1.03, December 6, 2000), Microsoft specifically grants a number of rights, and many readers of that document have interpreted it as permitting operating system vendors to implement FAT.

See also: File system, Drive letter assignment, Software patent, as well as entries for competing file systems such as NTFS, EXT2, EXT3, and ReiserFS.