|
File Allocation Table (FAT) is a partially patented file system developed by Microsoft for MS-DOS and is the primary file system for consumer versions of Microsoft Windows up to and including Windows Me. The FAT file system is relatively uncomplicated, and is supported by virtually all existing operating systems for personal computers. This ubiquity makes it an ideal format for floppy disks and solid-state memory cards, and a convenient way of sharing data between disparate operating systems installed on the same computer (a dual boot environment). The most common implementations have a serious drawback in that when files are deleted and new files written to the media, their fragments tend to become scattered over the entire media, making reading and writing a slow process. Defragmentation is one solution to this, but is often a lengthy process in itself and has to be repeated regularly to keep the FAT file system clean. History The FAT filesystem was created by Bill Gates and Marc McDonald in 1977 for managing disks in Microsoft Disk BASIC. In August 1980 Tim Paterson incorporated FAT into his 86-DOS operating system for the S-100 8086 CPU boards; the filesystem was the main difference between 86-DOS and CP/M, of which 86-DOS was otherwise mostly a clone. 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 how each file is scattered across the disk. To reduce the management complexity, disk space is allocated to files in contiguous groups of hardware sectors called clusters. The maximum possible number of clusters has dramatically increased over time. Its binary logarithm is used to name the successive major versions of the format, those requiring an operating system upgrade. One major upgrade was not related to increasing this count. The FAT standard has also evolved in several ways where backwards compatibility with existing software has been preserved. FAT12 This initial version of FAT is now referred to as FAT12. As a filesystem for disks, it had a number of limitations: no support for hierarchical directories, cluster addresses were "only" 12 bits long (which limited cluster count to 4096 and 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 32 MB. An entry-level floppy 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 160 KB. The above limits exceeded this capacity by one or more orders of magnitude and at the same time allowed all the control structures to fit inside the first track, thus avoiding head movement during read and write operations. The limits were successively lifted in the following years, which improved wait-loss dramatically. Since the sole root directory had to fit inside the first track as well, the maximum possible number of files was limited to a few dozen. A limitation which was not addressed until much later was that any bad sector in the control structures area, the track 0, could prevent the diskette from being usable. The DOS formatting tool rejected such diskettes completely. Bad sectors were only allowed in the file area, where they made the entire holding cluster unusable as well. Directories In order to properly support the newer IBM PC XT computer, which featured a 10 MB hard disk, MS-DOS 2.0 was released around the same time, at the beginning of 1983, and introduced hierarchical directories. Apart from allowing for better organization of files, directories allowed it to store many more files on the hard disk, as the maximum number of files was no longer constrained by the (still fixed) root directory size. This number could now be equal to the number of clusters (or even greater, given that zero-sized files do not use any clusters on FAT). The format of the FAT itself did not change. The 10 MB hard disk on the PC XT had 4 KB clusters. If a 20 MB hard disk was later installed, and formatted with MS-DOS 2.0, the resultant cluster size would be 8 KB, the boundary at 15.9 MB. Initial FAT16 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,517) and consequently much greater file-system sizes. 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 yet what today is commonly understood under this name. A 20 MB hard disk formatted under MS-DOS 3.0 was not accessible by the older MS-DOS 2.0. 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 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. Extended partition and logical drives Apart from improving the structure of the FAT filesystem itself, a parallel development allowing an increase in the maximum possible FAT storage space was the introduction of multiple FAT partitions. Originally partitions were supposed to be used only for sharing the disk between operating systems, typically DOS and Xenix at the time, so DOS was only prepared to handle one FAT partition. It was not possible to create multiple DOS partitions using DOS tools, and third party tools would warn that such a scheme would not be compatible with DOS. Simply allowing several identical-looking DOS partitions could lead to naming problems: should C: be the first FAT partition on disk, for simplicity, or rather the partition marked as active in the partition table, so that several DOS versions can co-exist? Which partition should be C: if the system was booted from a diskette? To allow the use of more FAT partitions in a compatible way a new partition type was introduced (in MS-DOS 3.2, January 1986), the extended partition, which was actually just a container for additional partitions called logical drives. Originally only 1 logical drive was possible, allowing the use of hard-disks up to 64 MB. In MS-DOS 3.3 (August 1987) this limit was increased to 24 drives; it probably came from the compulsory letter-based disk naming (A and B being reserved for the two floppy drives). The logical drives were described by on-disk structures which closely resemble the master boot record (MBR) of the disk (which describes the primary partitions), probably to simplify coding, and they were chained/nested in a way analogous to Russian matryoshka dolls. Only one extended partition was allowed. Logical drives were not bootable, and the extended partition could only be created after the primary FAT partition (except with third party formatting tools), which removed all ambiguity, but also the possibility of booting several DOS versions from the same hard disk. A useful side-effect of the extended partition scheme was to significantly increase the maximum number of partitions possible on a PC hard disk, beyond the 4 which could be described by the MBR alone. Prior to the introduction of extended partitions, some hard disk controllers (which at that time were separate option boards, since the IDE standard did not yet exist) could make large hard disks appear as two separate disks. Alternatively, special software drivers, like Ontrack's Disk Manager could be installed for the same purpose Final FAT16 Finally in November 1987, Compaq DOS 3.31 introduced what is today called the FAT16 format, with the expansion of the 16-bit disk sector index to 32 bits. The result was initially called the DOS 3.31 Large File System. Although the on-disk changes were apparently minor, the entire DOS disk code had to be converted to use 32-bit sector numbers, a task complicated by the fact that it was written in 16-bit assembly language. In 1988 the improvement became more generally available through MS-DOS 4.0. The limit on partition size was now dictated by the 8-bit signed count of sectors-per-cluster, which had a maximum power-of-two value of 64. With the usual hard disk sector size of 512 bytes, this gives 32 KB clusters, thereby fixing the "definitive" limit for the FAT16 partition size at 2 gigabytes. On magneto-optical media, which can have 1 or 2 KB sectors, the limit is proportionally greater. Much later, Windows NT increased the maximum cluster size to 64 KB by considering the sectors-per-cluster count as unsigned. However, the resulting format was not compatible with any other FAT implementation of the time, and it generated massive internal fragmentation. Windows 98 also supported reading and writing this variant, but its disk utilities didn't work with it. The FAT16 format limits the number of entries in the root directory to 512 (entries being file and/or folder names in the old 8.3 format).• Use of long file names reduces this further. Even today, this limitation still applies to certain MP3 players that require the use of the FAT16 file system format. Long File Names (VFAT, LFNs) One of the "user experience" goals for the designers of Windows 95 was the ability to use long filenames (LFNs), in addition to classic 8.3 names. LFNs were implemented using a work-around in the way directory entries are laid out (see below). The version of the file system with this extension is usually known as VFAT after the Windows 95 VxD device driver. Interestingly, the VFAT driver actually appeared before Windows 95, in Windows for Workgroups 3.11, but was only used for implementing 32-bit File Access, a higher performance protected mode file access method, bypassing DOS and directly using either the BIOS, or, better, the Windows-native protected mode disk drivers. It was a backport; Microsoft's ads for WfW 3.11 said 32-bit File Access was based on "the 32-bit file system from our Chicago project." In Windows NT, support for long filenames on FAT started from version 3.5. 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 decided to implement a newer generation of FAT, known as FAT32, with cluster counts held in a 32-bit field, of which 28 bits are currently used. In theory, this should support a total of approximately 268,435,438 (< 228) 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 (< 222) clusters, placing the volume limit at 124.55 gigabytes, unless “scandisk” is not needed.• indeed confirms the limitation and the by design statement, but gives no rationale or explanation. Peter Norton's opinion is that “Microsoft has intentionally crippled the FAT32 file system.” The maximum possible size for a file on a FAT32 volume is 4 GiB minus 2 B (232−2 bytes). For most users, this has become the most nagging limit of FAT32 as of 2005, since video capture and editing applications and some other software can easily exceed this limit. Most new windows machines now ship with NTFS and thus avoid these problems but those who run dual boot systems or who move external data drives between computers with different operating systems have little choice but to stick with FAT32 (although between Windows and Linux it is possible to use ext2 through the use of external drivers such as ext2 IFS; two good drivers can be found at * and *). Third party support The alternative IBM PC operating systems — such as Linux, FreeBSD, and BeOS — have all supported FAT, and most added support for VFAT and FAT32 shortly after the corresponding Windows versions were released. Early Linux distributions also supported a format known as UMSDOS, which was FAT with Unix file attributes (such as long file name and access permissions) stored in a separate file called --linux-.---. UMSDOS fell into disuse after VFAT was released and is not enabled by default in Linux kernels from version 2.5.7 onwards •. The Mac OS X operating system also supports the FAT filesystems on volumes other than the boot disk.
FAT and Alternate Data Streams The FAT filesystem itself is not designed for supporting ADS, but some operating systems that heavily depend on them have devised various methods for handling them in FAT drives. Such methods either store the additional information in extra files and directories (Mac OS), or give new semantics to previously unused fields of the FAT on-disk data structures (OS/2 and Windows NT). The second design, while presumably more efficient, prevents any copying or backing-up of those volumes using non-aware tools; manipulating such volumes using non-aware disk utilities (e.g. defragmenters or CHKDSK) will probably lose the information. Mac OS using PC Exchange stores its various dates, file attributes and long filenames in a hidden file called FINDER.DAT, and Resource Forks (a common Mac OS ADS) in a subdirectory called RESOURCE.FRK, in every directory where they are used. From PC Exchange 2.1 onwards, they store the Mac OS long filenames as standard FAT long filenames and convert FAT filenames longer than 31 characters to unique 31-character filenames, which can then be made visible to Macintosh applications. Mac OS X stores metadata (Resource Forks, file attributes, other ADS) in a hidden file with a name constructed from the owner filename prefixed with "._", and Finder stores some folder and file metadata in a hidden file called ".DS_Store". OS/2 heavily depends on extended attributes (EAs) and stores them in a hidden file called "EA DATA. SF" in the root directory of the FAT12 or FAT16 volume. This file is indexed by 2 previously reserved bytes in the file's (or directory's) directory entry. In the FAT32 format, these bytes hold the upper 16 bits of the starting cluster number of the file or directory, hence making it difficult to store EAs on FAT32. Extended attributes are accessible via the Workplace Shell desktop, through REXX scripts, and many system GUI and command-line utilities (such as 4OS2).• Windows NT supports the handling of extended attributes in HPFS, NTFS, and FAT. It stores EAs on FAT using exactly the same scheme as OS/2, but does not support any other kind of ADS as held on NTFS volumes. Trying to copy a file with any ADS other than EAs from an NTFS volume to a FAT volume gives a warning message with the names of the ADSs that will be lost. Windows 2000 onward acts exactly as Windows NT, except that it ignores EAs when copying to FAT32 without any warning (but shows the warning for other ADSs, like "Macintosh Finder Info" and "Macintosh Resource Fork"). Future Microsoft has recently secured patents for VFAT and FAT32 (but not the original FAT), which is causing concern that the company might later seek royalties from Linux distributions and from media vendors that pre-format their products (see FAT Licensing below). Despite two earlier rulings against them, Microsoft prevailed and was awarded the patents. 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 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, 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 is finally eroding this drawback. FAT is still the normal filesystem for removable media (with the exception of CDs and DVDs), with FAT12 used on floppies, and FAT16 on most other removable media (such as flash memory cards for digital cameras and USB flash drives). Most removable media are not yet large enough to benefit from FAT32, although some larger flash drives do make use of it. FAT16 is used on these drives for reasons of compatibility and size overhead. The FAT32 formatting support in Windows 2000 and XP is limited to volumes of 32 GB, which effectively forces users of modern hard drives either to use NTFS, to partition the drive into smaller volumes (below 32 GB), or to format the drive using third party tools such as a port of mkdosfs or fat32format. exFAT exFAT is an incompatible replacement for FAT filesystems that will be introduced with Windows CE 6.0. It is intended to be used on flash drives, where FAT is used today. Windows XP and Vista file system drivers will be offered by Microsoft shortly after the release of Windows CE 6.0. exFAT introduces a free space bitmap allowing faster space allocation and faster deletes, support for files up to 2^64 bytes, larger cluster sizes (up to 32 MB in the first implementation), an extensible directory structure and name hashes for filenames for faster comparizons. It does not have short 8.3 DOS names anymore. It does not appear to have security access control lists or file system journaling like NTFS. Main disk structures The following is an overview of the order of structures in a FAT partition or disk: A FAT file system is composed of four different sections. Boot Sector Common structure of the first 36 bytes used by all FAT versions: Further structure used by FAT12 and FAT16, also known as Extended BIOS Parameter Block: Further structure used by FAT32: The boot sector is portrayed here as found on e.g. an OS/2 1.3 boot diskette. Earlier versions used a shorter BIOS Parameter Block and their boot code would start earlier (for example at offset 0x2b in OS/2 1.1). Exceptions The implementation of FAT used in MS-DOS for the Apricot PC had a different boot sector layout, to accommodate that computer's non-IBM compatible BIOS. The jump instruction and OEM name were omitted, and the MS-DOS filesystem parameters (offsets 0x0B - 0x17 in the standard sector) were located at offset 0x50. Later versions of Apricot MS-DOS gained the ability to read and write disks with the standard boot sector in addition to those with the Apricot one. DOS Plus on the BBC Master 512 did not use conventional boot sectors at all. Data disks omitted the boot sector and began with a single copy of the FAT (the first byte of the FAT was used to determine disk capacity) while boot disks began with a miniature ADFS filesystem containing the boot loader, followed by a single FAT. It could also access standard PC disks formatted to 180 KB or 360 KB, again using the first byte of the FAT to determine capacity. 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 chains 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: 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 but are reserved and should be left untouched. In the table above these are denoted by a question mark. The first cluster of the data area is cluster Directory table A directory table is a special type of file that represents a directory (nowadays commonly 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. Entries with the subdirectory flag set should have a size of 0. The actual number of entires in a directory can grow by adding another cluster to the chain in the FAT. Legal characters for DOS file names include the following: This excludes the following ASCII characters: < > ? | Windows/MSDOS has no shell escape character stored as A–Z on FAT-12/16 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 are ignored by most old MS-DOS programs. Notably, a directory containing only volume labels is considered as empty and is allowed to be deleted; such a situation appears if files created with long names are deleted from plain DOS. A checksum also allows verification of whether a long file name matches the 8.3 name; such a mismatch could occur if a file was deleted and re-created using DOS in the same directory position. The checksum is calculated using the algorithm below. (Note that pFcbName is a pointer to the name as it appears in a regular directory entry, i.e. the first eight characters are the filename, and the last three are the extension. The dot is implicit. Any unused space in the filename is padded with a space (ASCII 0x20) char. For example, "Readme.txt" would be "README TXT".)
Older versions of PC-DOS mistake LFN names in the root directory for the volume label, and are likely to display an incorrect label. Each phoney entry can contain up to 13 UTF-16 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: If a filename contains only lowercase letters, or is a combination of a lowercase basename with an uppercase extension, or vice-versa, has no special characters, and fits within the 8.3 limits, a VFAT entry is not created on Windows NT. Instead, undocumented bits in byte 0x0c of the directory entry are used to indicate that the filename should be considered as entirely or partially lowercase. Specifically, bit 4 means lowercase extension and bit 3 lowercase basename, which allows for combinations such as "example.TXT" or "HELLO.txt" but not "Mixed.txt". Few other operating systems support this. Non-NT Windows versions see all-uppercase filenames if this extension has been used. By default, recent versions of Linux will recognize this extension but won't use it when writing. Third-party extensions Before Microsoft added support for long filenames and creation/access time stamps, bytes 0x0C–0x15 of the directory entry were used by alternative operating systems to store additional metadata. These included: FAT licensing Microsoft applied for, and was granted, a series of patents for key parts of the FAT file system in the mid-1990s. Being almost universally compatible and well-understood, FAT is frequently chosen as an interchange format for flash media used in digital cameras and PDAs. On 2003-12-03 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. To this end, Microsoft cited four patents on the FAT filesystem as the basis of its intellectual property claims. All four pertain to long-filename extensions to FAT first seen in Windows 95: 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, 2000-12-06), Microsoft specifically grants a number of rights, which many readers have interpreted as permitting operating system vendors to implement FAT. Microsoft is not the only company to have applied for patents for parts of the FAT file system. Other patents affecting FAT include: Appeal As there was 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 questions of patentability," and opened an investigation into the validity of Microsoft's FAT patents.• On 2004-09-30 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." According to the PUBPAT press release, "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." On 2005-10-05 the Patent Office announced that, following the re-examination process, it had again rejected all claims of patent 5,579,517, and it additionally found invalid on the grounds that the patent had incorrect assignees. Finally, on 2006-01-10 the Patent Office ruled that features of Microsoft's implementation of the FAT system were "novel and non-obvious" reversing both earlier non-final decisions•. See also | |||||||
|
| ||||||||
 |
|
| |