File Allocation Table

File Allocation Table (FAT) is a file system that was developed for MS-DOS and used in consumer versions of Microsoft Windows up to and including Windows Me. The FAT file system is considered relatively uncomplicated, and because of that, it is a popular format for floppy disks; moreover, it is supported by virtually all existing operating systems for personal computers, and because of that it is 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 cards and other similar devices.

History

The FAT filesystem made its debut in August 1980 with the first version of QDOS, the ancestor of Microsoft's PC-DOS and MS-DOS; it was the main difference between QDOS and CP/M, of which QDOS was otherwise mostly a clone.

Interestingly, the filesystem idea was taken from how the stand-alone version of Microsoft BASIC has been managing diskettes since 1976. In May 1979, a year before deciding to write QDOS, Tim Paterson helped Microsoft's Bob O'Rear to port their language onto the new 8086 hardware his company was about to put on the market.

This initial version of FAT is now referred to as FAT12. As a filesystem for floppy disks, it had a number of limitations: no support for directories, cluster addresses were "only" 12-bits long (which made the code manipulating the FAT a bit tricky) and the disk size was stored as a 16-bit count of sectors, which limited the size to 32MB.

An entry-level diskette at the time would be 5.25", single-sided, 40 tracks, with 8 sectors per track, resulting in a capacity of slightly less than 160KB. The above limits exceeded this capacity by one or more orders of magnitude and at the same time allowed to fit all the control structures inside the first track, thus avoiding head movement during read and write operations. They were successively lifted in the following years.

In order to properly support the IBM PC XT computer, which featured a 10 MB hard disk, MS-DOS 2.0 has been released around the same time, at the beginning of 1983, and introduced directories. The format of the FAT itself did not change. The hard disk on PC XT had 8 KB clusters.

In 1984 IBM released the PC AT, which featured a 20 MB hard disk. Microsoft introduced MS-DOS 3.0 in parallel. Cluster addresses were increased to 16-bit, allowing for a greater number of clusters (up to 65,536) and consequently much greater filesystem sizes. However, the maximum possible number of sectors and the maximum (partition, rather than disk) size of 32 MB did not change.

MS-DOS 3.0 also introduced support for high-density 1.2 MB 5.25" diskettes, which notably had 15 sectors per track, hence more space for FAT. This probably prompted a dubious optimization of the cluster size, which went down from 2 sectors to just 1. The net effect was that high density diskettes were significantly slower than older double density ones.

In 1988 finally came what today is called the FAT16 format, with the removal of the 16-bit counter of disk sectors, in MS-DOS 4.0. The partition size was now limited by the 8-bit signed count of sectors per cluster, which could reach a maximum power-of-two value of 64, giving 32 KB clusters with the usual 512 bytes per sector hardware, hence fixing the "definitive" limit for FAT16 partition size at 2 gigabytes. Much later, Windows NT increased the maximum cluster size to 64K by considering the sector per cluster count as unsigned, but the resulting format was not compatible with any other FAT implementation and generated really huge internal fragmentation anyway.

One of the user experience goals for the designers of Windows 95 was the use of long file names in the new operating system. These were implemented using a work-around in the way directory entries are laid out (see below). The new version of the file system became known as VFAT (Virtual FAT), after its Windows 95 VxD device driver. VFAT is supported by Windows 95 and above and Windows NT 3.5 and above.

In order to overcome the volume size limit of FAT16 while still allowing memory-constrained DOS real-mode code to handle the format, Microsoft decided to implement a newer generation of FAT, known as FAT32, with 32-bit cluster numbers, of which 28 bits are currently used. In theory, this should support a total of approximately 268,435,438 clusters, allowing for drive sizes in the range of 2 terabytes. However, due to limitations in Microsoft's scandisk utility, the FAT is not allowed to grow beyond 4,177,920 clusters, placing the volume limit at 124.55 gigabytes [1]. FAT32 was introduced with Windows 95 OSR 2. The many changes it incorporated made it a major improvement. Unfortunately, it is no longer sufficient for the much larger volumes in use today.

The alternative IBM PC operating systems--such as 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. The Mac OS X operating system also supports the FAT filesystems on volumes other than the boot disk.

Since Microsoft has announced the discontinuation of its MS-DOS-based consumer operating systems with Windows ME, it remains unlikely that any new versions of FAT will 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; its main drawback is its very limited support by non-Microsoft OSs, since the exact specification is a trade secret of Microsoft. Because of this, and also as FAT is an ideal file system for small drives like floppy disks, FAT is likely to stay for a long time. It is also used on other removable storage of sizes smaller than the practical limits of FAT, such as flash memory cards for digital cameras and USB flash drives.

Design and implementation

A FAT file system is composed of four different sections.

The Boot Sector (aka Partition Boot Record, BIOS Parameter Block or Reserved Sector). This is always the first sector of the partition and includes some basic file system information (in particular, its type), pointers to the location of the other sections and the operating system's boot loader code.
The FAT Region. This contains two copies of the File Allocation Table for the sake of redundancy. These are maps of the partition, indicating how the clusters are allocated.
The Root Directory Region. This is a Directory Table that stores information about the files and directories in the root directory. With FAT32 it can be stored anywhere in the partition, however with earlier versions it is always located immediately after the FAT Region.
The Data Region. This is where the actual file and directory data is stored and takes up most of the partition. 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 1KB file resides in a 32KB cluster, 31KB are wasted.

The Boot Sector is of the following format:

File Allocation Table

A partition is divided up into identically sized clusters, small blocks of contiguous space. Cluster sizes vary depending on the type of FAT file system being used and the size of the partition, typically cluster sizes lie somewhere between 2KB and 32KB. Each file may occupy one or more of these clusters depending on its size, a file is represented by a chain of these clusters (referred to as a singly linked list). However these chains are not necessarily stored adjacently on the disk's surface but are often instead fragmented throughout the Data Region.

The File Allocation Table (FAT) is a list of entries that map to each cluster on the partition. Each entry records one of five things:

the address of the next cluster in a chain

a special end of file (EOF) character that indicates the end of a chain

a special character to mark a bad cluster

a special character to mark a reserved cluster

a zero to note that that cluster is unused

Each version of the FAT file system uses a different size for FAT entries. The size is indicated by the name, for example the FAT16 file system uses 16 bits for each entry while the FAT32 file system uses 32 bits. This difference means that the File Allocation Table of a FAT32 system can map a greater number of clusters than FAT16, allowing for larger partition sizes with FAT32. This also allows for more efficient use of space than FAT16, because on the same hard drive a FAT32 table can address smaller clusters which means less wasted space.

FAT entry values:

Note that FAT32 uses only 28 bits of the 32 possible bits. The upper 4 bits are usually zero and should be left untouched. In the table above these are denoted by a question mark.

Directory Table

A Directory Table is a special type of file that represents a directory. Each file or directory stored within it is represented by a 32 byte entry in the table. Each entry records the name, extension, attributes (archive, directory, hidden, read-only, system and volume), the date and time of creation, the address of the first cluster of the file/directory's data and finally the size of the file/directory.

Aside from the Root Directory Table in FAT12 and FAT16 file systems which occupies the special Root Directory Region location, all Directory Tables are stored in the Data Region.

Legal characters for DOS file names include the following:

Upper case letters A-Z

Numbers 0-9

Space (though trailing spaces are considered to be padding and not a part of the file name)

! # $ % & ( ) - @ ^ _ ` { } ~ '

Values 128-255

The DOS file names are in the OEM character set.

Directory entries, both in the Root Directory Region and in subdirectories, are of the following format:

Long File Names (LFN) are stored on a FAT file system using a trick - adding phoney entries into the Directory Tables. The entries are marked with a Volume Label attribute which is impossible for a regular file and because of that they're ignored by most old MS-DOS programs. (Older versions of PC-DOS mistake LFN names for the volume label, and are likely to display an incorrect label). Each phoney entry 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 which contained file size or time stamps (but for security versus disk checking tools the starting cluster field is left unused with a 0 value). See 8.3 for additional explanations.

LFN entries use the following format:

FAT licensing

In the mid-1990s Microsoft patented the FAT file format. Many producers of devices such as digital cameras and PDAs use this file system as the format for their flash media because it is used by Microsoft Windows and other operating systems to access those media.

On December 3 2003, Microsoft announced it would be offering licenses for use of its FAT specification and "associated intellectual property", at the cost of a US $0.25 royalty per unit sold, with a $250,000 maximum royalty per license agreement. [1]

To this end, Microsoft cited four patents on the FAT filesystem as the basis of its intellectual property claims. Analysis of the four patents show that all pertain to the "long filenames" feature found in Windows 95.

- Method and system for accessing a file using file names having different file name formats. Filed July 6, 1992. This covers the ability to access the same file with both a long and short filename, e.g. "Microsoft.txt" and "MICROS~1.TXT". This covers the basic fact of pointing several file entries with different filenames at the same actual file data, the method of translating from a long name to an MS-DOS compliant 8.3 filename, and the method of resolving filename clashes (e.g. creating short names MICROS~2.TXT, MICROS~3.TXT and so on), and cross-referencing the long and short filenames for a file. It is unclear whether this patent would be infringed in the implementation of a FAT filesystem without explicit long filename capabilities. Let's note that although the idea of accessing the same file under two different names has prior art in the form of hard links in older (eg. UNIX) file systems, the semantics of FAT (and NTFS) dual names are quite different: deleting a file using one name will delete the other name (and the file) as well, renaming a file to a "short" name will update the long file name for coherency, and renaming a file to a "long" name will allocate a new "short" name, again for coherency. On NTFS, which features both hard links and dual names, these are separate concepts and each hard link has two names. Finally, at the API level, both names are available together when a directory listing is requested; they do not appear as two separate files and do not have to be "matched".
- Common name space for long and short filenames. Filed for on April 24, 1995. This covers the method of using the file meta-data table normally used only for short filenames to store a number of "fake" entries which hold the long filename data.
* This patent was challenged by the Public Patent Foundation and its claims were rejected on September 14 2004, due to prior disclosure of the claimed techniques in patents and . [1] [1]
- Common name space for long and short filenames. Filed on September 5, 1996. This is very similar to 5,579,517.
* Has not yet been challenged.
- 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 claims on the methods used when Windows 95, Windows 98 and Windows Me expose long filenames to their MS-DOS compatibility layer. It does not appear to affect any third party implementations outwith the Windows and MS-DOS operating systems.

Many technical commentators have concluded that these patents only cover FAT implementations that include support for long filenames, and that removable solid state media and consumer devices only using short names would be unaffected.

Additionally, in the document "Microsoft Extensible Firmware Initiative FAT 32 File System Specification, FAT: General Overview of On-Disk Format" published by Microsoft (version 1.03, December 6, 2000), Microsoft specifically grants a number of rights, which many readers have interpreted as permitting operating system vendors to implement FAT.

Re-opened investigation

As there has been widespread call for these patents to be re-examined, the Public Patent Foundation submitted evidence to the US Patent and Trade Office (USPTO) disputing the validity of these patents, including prior art references from Xerox and IBM. The USPTO acknowledged that the evidence raised "substantial new question[s] of patentability," and opened an investigation into the validity of Microsoft's FAT patents.

On September 30 2004, the USPTO rejected all claims of , based primarily on evidence provided by the Public Patent Foundation. Dan Ravicher, the foundation's executive director, said "The Patent Office has simply confirmed what we already knew for some time now, Microsoft's FAT patent is bogus."

Microsoft still has the opportunity to respond to the Patent Office's rejection. Typically, third party requests for reexamination, like the one filed by PUBPAT, are successful in having the subject patent either narrowed or completely revoked roughly 70% of the time.