File Allocation Table (FAT)

innovation

File Allocation Table or FAT is a computer file system architecture now widely used on most computer systems and most memory cards, such as those used with digital cameras.

It was developed by Bill Gates and Marc McDonald during 1976–1977.[1][2] It is the primary file system for various operating systems including DR-DOS, FreeDOS, MS-DOS, OS/2 (v1.1) and Microsoft Windows (up until Windows Me). For floppy disks, it has been standardized as ECMA-107[3] and ISO/IEC 9293.[4][5] Those standards include only FAT12 and FAT16 without long filename support; long filenames with FAT is partially patented.

The FAT file system is relatively straightforward technically and is supported by virtually all existing operating systems for personal computers. This makes it a useful format for solid-state memory cards and a convenient way to share data between operating systems.

innovation

History
The FAT file system was created for managing disks in Microsoft Standalone Disk BASIC. In August 1980 Tim Paterson incorporated FAT into his 86-DOS operating system for the S-100 8086 CPU boards;[6] the file system was the main difference between 86-DOS and its predecessor, CP/M.

The name originates from the usage of a table which centralizes the information about which areas belong to files, are free or possibly unusable, and where each file is stored on the disk. To limit the size of the table, disk space is allocated to files in contiguous groups of hardware sectors called clusters. As disk drives have evolved, the maximum number of clusters has dramatically increased, and so the number of bits used to identify each cluster has grown. The successive major versions of the FAT format are named after the number of table element bits: 12, 16, and 32. The FAT standard has also been expanded in other ways while preserving backward compatibility with existing software.

innovation

FAT12


The initial version of FAT is now referred to as FAT12. Designed as a file system for floppy disks, it limited cluster addresses to 12-bit values, which not only limited the cluster count to 4078,[7] but made FAT manipulation tricky with the PC's 8-bit and 16-bit registers. (Under Linux, FAT12 is limited to 4084 clusters.[8]) The disk's size is stored as a 16-bit count of sectors, which limited the size to 32 MB[9]. FAT12 was used by several manufacturers with different physical formats, but a typical floppy disk at the time was 5.25-inch, single-sided, 40 tracks, with 8 sectors per track, resulting in a capacity of 160 KB for both the system areas and files. The FAT12 limitations exceeded this capacity by a factor of ten or more.

By convention, all the control structures were organized to fit inside the first track, thus avoiding head movement during read and write operations, although this varied depending on the manufacturer and physical format of the disk. At the time FAT12 was introduced, DOS did not support hierarchical directories, and the maximum number of files was typically limited to a few dozen. Hierarchical directories were introduced in MS-DOS version 2.0.[10]

A limitation which was not addressed until much later was that any bad sector in the control structures area, track 0, could prevent the disk from being usable. The DOS formatting tool rejected such disks completely. Bad sectors were allowed only in the file area, where they made the entire holding cluster unusable as well. FAT12 remains in use on all common floppy disks, including 1.44MB ones.

innovation

Initial FAT16
In 1984, IBM released the PC AT, which featured a 20 MB hard disk. Microsoft introduced MS-DOS 3.0 in parallel. (The earlier PC XT was the first PC with a hard drive from IBM, and MS-DOS 2.0 supported that hard drive with FAT12.) Cluster addresses were increased to 16-bit, allowing for up to 65,517 clusters per volume, and consequently much greater file system sizes, at least in theory. However, the maximum possible number of sectors and the maximum (partition, rather than disk) size of 32 MB did not change. Therefore, although technically already "FAT16", this format was not what today is commonly understood as FAT16. With the initial implementation of FAT16 not actually providing for larger partition sizes than FAT12, the early benefit of FAT16 was to enable the use of smaller clusters, making disk usage more efficient, particularly for files several hundred bytes in size, which were far more common at the time. Also, the introduction of FAT16 actually did bring an increase in the maximum partition size under MS-DOS, since the implementation of FAT12 for hard disks in MS-DOS 2.0 was limited to 15 MB. (That is, the initial FAT16 did not support larger drives than FAT12, but MS-DOS 3.0 using FAT16 did support larger drives than MS-DOS 2.0 using FAT12, by a factor of two.)[11]

A 20 MB hard disk formatted under MS-DOS 3.0 was not accessible by the older MS-DOS 2.0. (This was because MS-DOS 2.0 did not support version 3.0's FAT-16 and because it did not support hard disk partitions over 15 MB in size.) Of course, MS-DOS 3.0 could still access MS-DOS 2.0 style 8 KB-cluster partitions.

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 the FATs. 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.

innovation

FAT32
In order to overcome the volume size limit of FAT16, while still allowing DOS real mode code to handle the format without unnecessarily reducing the available conventional memory, Microsoft implemented a newer generation of FAT, known as FAT32, with cluster values held in a 32-bit field, of which 28 bits are used to hold the cluster number, for a maximum of approximately 268 million (228) clusters. This allows for drive sizes of up to 8 terabytes with 32KB clusters, but the boot sector uses a 32-bit field for the sector count, limiting volume size to 2 TB on a hard disk with 512 byte sectors.

On Windows 95/98, due to the version of Microsoft's SCANDISK utility included with these operating systems being a 16-bit application, the FAT structure is not allowed to grow beyond around 4.2 million (< 222) clusters, placing the volume limit at 127.53 GB.[14] A limitation in original versions of Windows 98/98SE's Fdisk utility causes it to incorrectly report disk sizes over 64 GB.[15] A corrected version is available from Microsoft, but it cannot partition drives larger than 512GB [16]. The Windows 2000/XP installation program and filesystem creation tool imposes a limitation of 32 GB [17]. However, both systems can read and write to FAT32 file systems of any size. This limitation is by design and according to Microsoft was imposed because many tasks on a very large FAT32 file system become slow and inefficient.[14][18] This limitation can be bypassed by using third-party formatting utilities.[19] Windows Me supports the FAT32 file system without any limits.[20] However, similarly to Windows 95/98/98SE there is no native support for 48-bit LBA in Windows ME, meaning that the maximum disk size for ATA disks is 127.6 GB, the maximum size of an ATA disk using the previous long-standard 28-bit LBA.

FAT32 was introduced with Windows 95 OSR2, although reformatting was needed to use it, and DriveSpace 3 (the version that came with Windows 95 OSR2 and Windows 98) never supported it. Windows 98 introduced a utility to convert existing hard disks from FAT16 to FAT32 without loss of data. In the NT line, native support for FAT32 arrived in Windows 2000. A free FAT32 driver for Windows NT 4.0 was available from Winternals, a company later acquired by Microsoft. Since the acquisition the driver is no longer officially available.

The maximum possible size for a file on a FAT32 volume is 4 GB minus 1 byte (232&#8722;1 bytes). Video applications, large databases, and some other software easily exceed this limit. Larger files require another formatting type such as NTFS.

innovation

Future
Microsoft has recently secured patents for VFAT and FAT32 (but not the original FAT). Despite two earlier rulings against them, Microsoft prevailed and was awarded the patents.

For most purposes, the NTFS file system is superior to FAT in terms of features and reliability; its main drawbacks are the size overhead for small volumes and the very limited support by anything other than the NT-based versions of Windows, since the exact specification is a trade secret of Microsoft. The availability of NTFS-3G since mid 2006 has led to much improved NTFS support in Unix-like operating systems, considerably alleviating this concern. It is still not possible to use NTFS in DOS-like operating systems without third-party drivers, which in turn makes it difficult to use a DOS floppy for recovery purposes. Microsoft provided a recovery console to work around this issue, but for security reasons it severely limited what could be done through the Recovery Console by default. The movement of recovery utilities to boot CDs based on BartPE or Linux (with NTFS-3G) is finally eroding this drawback.

FAT is still the normal file system for removable media (with the exception of CDs and DVDs), with FAT12 used on floppies, and FAT16 or FAT32 on most other removable media (such as flash memory cards for digital cameras and USB flash drives). Some removable media are not yet large enough to benefit from FAT32 and FAT16 is used on these drives for reasons of compatibility and size overhead, although some larger flash drives, like SDHC, do make use of it.

innovation

exFAT (aka FAT64) is an incompatible replacement for FAT file systems that was introduced with Windows Embedded CE 6.0. It is intended to be used on flash drives, where FAT is used today. Microsoft has offered a hotfix to add support for exFAT to Windows XP[23], while Windows Vista Service Pack 1 added exFAT support to Windows Vista.[24] exFAT introduces a free space bitmap allowing faster space allocation and faster deletes, support for files up to 264 bytes (16777216 Terabytes), larger cluster sizes (up to 32 MB in the first implementation), an extensible directory structure and name hashes for filenames for faster comparisons. It does not have short 8.3 filenames anymore. It does not appear to have security access control lists or file system journaling like NTFS, though device manufacturers can choose to implement simplified support for transactions (backup file allocation table used for the write operations, primary FAT for storing last known good allocation table).

innovation

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 2 KB and 32 KB. Each file may occupy one or more of these clusters depending on its size; thus, a file is represented by a chain of these clusters (referred to as a singly linked list). However these clusters are not necessarily stored adjacent to one another 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 cluster number of the next cluster in a chain
a special end of clusterchain (EOC) entry that indicates the end of a chain
a special entry to mark a bad cluster
a special entry to mark a reserved cluster[citation needed]
a zero to note that the cluster is unused
Each version of the FAT file system uses a different size for FAT entries. Smaller numbers result in a smaller FAT table, but waste space in large partitions by needing to allocate in large clusters. The FAT12 file system uses 12 bits per FAT entry, thus two entries span 3 bytes. It is consistently little-endian: if you consider the 3 bytes as one little-endian 24-bit number, the 12 least significant bits are the first entry and the 12 most significant bits are the second.

In the FAT32 file system, FAT entries are 32 bits, but only 28 of these are actually used; the 4 most significant bits are reserved.

FAT entry values:

innovation

Directory table
A directory table is a special type of file that represents a directory (also known as a folder). 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. The actual number of entries in a directory stored in the Data Region can grow by adding another cluster to the chain in the FAT.

Legal characters for DOS file names include the following:

Upper case letters A–Z
Numbers 0–9
Space (though trailing spaces in either the base name or the extension are considered to be padding and not a part of the file name, also filenames with space in them could not be used on the DOS command line prior to Windows 95 because of the lack of a suitable escaping system)
! # $ % & ' ( ) - @ ^ _ ` { } ~
Values 128–255
This excludes the following ASCII characters:

" * / : < > ? \ |
Windows/MSDOS has no shell escape character
+ , . ; = [ ]
They are allowed in long file names only.
Lower case letters a–z
Stored as A–Z. Allowed in long file names.
Control characters 0–31
Value 127 (DEL)
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