File Allocation Table

File Allocation Table, commonly known as FAT (from English file allocation table), is a file system developed for MS -DOS, as well as the main file system of non-enterprise editions of Microsoft Windows up to Windows Me.

FAT is relatively simple. Because of this, it is a popular floppy disk format supported by virtually all existing personal computer operating systems. It is used as a mechanism for exchanging data between different operating systems that coexist on the same computer, known as a multi-boot environment. It is also used in memory cards and similar devices.

Most widespread implementations of FAT have some drawbacks. When new files are deleted and written, it tends to leave fragments of them scattered all over the support. Over time, this makes the read or write process slower and slower. The so-called defragmentation is the solution to this, but it is a long process that must be repeated regularly to keep the file system in perfect condition. FAT was also not designed to be failover redundant. Initially it only supported short filenames: eight characters for the name plus three for the extension.

History and versions

The FAT file system was created by Mac based on a series of conversations between Mac and Bill Gates. It was first incorporated into the QDOS operating system by Tim Paterson in August 1980, for the Intel 8086 architecture S-100 computers. This file system was the main difference between QDOS and CP/M.

FAT12

• Block addresses only contain 12 bits. This complicates implementation.
• The disk size is stored as a 16-bit account expressed in sectorswhich limits the manageable space to 32 megabytes.

At that time, the usual floppy disk (5.25-inch single-sided) consisted of 40 tracks with 8 sectors per track, resulting in a capacity of less than 160 kilobytes. This limit exceeded the capacity by more than an order of magnitude, and at the same time, allowed to fit all the control structures on the first runway. Therefore, the movement of the heads in the read and write operations was avoided. These limits were exceeded in subsequent years.

In order to support the recent IBM PC, which featured a 10-megabyte hard drive, MS-DOS 2.0, and nested folders, simply 8-kilobyte clusters were used on the hard drive. The FAT format itself did not change.

In 1984, IBM released the PC AT, with a 20-megabyte hard drive. At the same time, Microsoft released MS-DOS 3.0. The cluster addresses were extended to 16 bits, allowing a larger number of clusters (exactly 65,536 files). Despite everything, there were no improvements to the maximum limit of 32 megabytes.

MS-DOS 3.0 also added support for high-density 5.25-inch (1.2 megabyte capacity) floppy disks, with 15 sectors per track, thus more space for FAT. This probably forced a dubious optimization of the cluster size, which dropped from two sectors to just one. The overall effect was a significant reduction in read and write times compared to double-density floppy disks.

Structure of the FAT12 on a 1.44M floppy disk:

FAT16

In 1987 what is now known as "the FAT 16 format" appeared. Removed the 16-bit sector counter. The partition size was now limited by the count of sectors per cluster, which was 8 bits. This forced to use clusters of 32 KiB with the usual 512 bytes per sector. So the final limit for FAT16 was set at 4 (2GiB per cluster) GiB.

This enhancement became available in 1988. Much later, Windows NT 4.0 (1998) and Windows XP (2001) increased the maximum size of the cluster to 64 kilobytes and can create partitions up to 4 GB. However, the resulting format was not compatible with other implementations of the time, and also generated more internal fragmentation (whole clusters were occupied even if only a few bytes were needed). Windows 98 supported this extension in terms of reading and writing. However, your disk utilities were not able to work with it.

VFAT and FASTFAT

Windows 3.11 introduced a new file system access scheme, using 32-bit protected mode (present on the Intel 386 and later) bypassing the MS-DOS kernel. To do this, it used the BIOS directly or the hardware of the disk drive. This also allowed a cache to be used, speeding up access. This was all called VFAT or virtual FAT.

Windows NT 3.1 provided the same approach, but called it FASTFAT. However, it was natural for Windows NT drivers to use 32-bit protected mode. It is often confused with LFN (long file name) support as this was enabled by default in Windows 95.

LFN or long filenames

One of the goals of the designers of Windows 95 was to use longer file names. It was implemented on top of FAT using a trick in the way of storing directory indexes. This implementation is also known as VFAT after the Windows 95 driver that first introduced it. Long names were also supported in Windows NT starting with version 3.5.

FAT32

Structure of a FAT32 table, with three assigned files

FAT32 was the answer to overcoming the size limit of FAT16 while maintaining compatibility with real-mode MS-DOS. Microsoft decided to implement a new generation of FAT using 32-bit cluster addresses (although only 28 of those bits were actually used).

In theory, this should allow for approximately 100,100,538,948,585,453 clusters, yielding storage sizes close to 8 TiB. However, due to limitations in Microsoft's ScanDisk utility, FAT32 is not allowed to grow beyond 4,177,920 clusters per partition (ie about 124 GiB).. Later, Windows 2000 and XP set the FAT32 limit at 64 GiB. Microsoft claims this to be a design decision, however it is capable of reading larger partitions created by other means.

FAT32 first appeared in Windows 95 OSR2. It was necessary to reformat to use the advantages of FAT32. Curiously, DriveSpace 3 (included with Windows 95 and 98) did not support it. Windows 98 introduced a tool to convert from FAT16 to FAT32 without data loss. This support was not available in the enterprise line until Windows 2000.

The maximum size of a file on FAT32 is 4 GiB (2³²−1 bytes).

Other manufacturers

Other operating systems such as GNU/Linux, FreeBSD and BeOS support FAT, and most also support VFAT and FAT32 to a lesser extent. Early editions of GNU/Linux also supported a format known as UMSDOS. This consisted of a variant of FAT that supported the typical Unix security permissions, as well as its long names. To do this, this information was stored in a separate FAT file named "--linux--.---" (thus preserving full compatibility). UMSDOS was deprecated with the appearance of VFAT in recent versions of the Linux kernel. The Mac OS X operating system also supports FAT file systems, as long as it is not the boot volume of the system.

FAT and metadata

NOTE: Metadata are attributes associated with a file but are not part of it (e.g. date or author). This concept receives other denominations such as filesystem fork, alternate data streams (in Windows), etc.

The FAT file system is not designed to hold metadata. Some operating systems that need them have built in various methods to simulate them. For example, by storing them in extra files or folders (similar to UMSDOS) or also by giving special semantics to structures not used in the original format. However, this last method is not compatible with tools not prepared for this extension. For example, a defragmentation tool could destroy the metadata. Mac OS, through the PC Exchange utility, stores metadata in a hidden file named "FINDER.DAT" (one per folder). Mac OS X stores metadata in a hidden file named after its owner, but starting with ".-". When it comes to a folder's meta-data, it stores it in a hidden file called ".DS_Store".seis

OS/2 also relies heavily on the use of meta-data. When referring to FAT volumes, it stores them in a hidden file named "EA DATA. SF" in the root folder of the volume. It also reserves two bytes in the file (or folder) so that it can be indexed. Metadata is accessed through the Workplace Shell desktop, through REXX scripts, or through utilities like 4OS2. When it comes to its own HPFS file system, it already supports native metadata, called extended attributes.

Windows NT supports metadata in the HPFS, NTFS, and FAT file systems (using the same mechanism as OS/2). But it is not possible to copy meta-data between different file systems. Windows 2000 behaves exactly the same as Windows NT, but ignores meta-data when copying files from FAT32 to other file systems.

ExFAT

exFAT (Extended File Allocation Table) is a file system specially adapted for flash memory introduced with Windows Embedded CE 6.0. exFAT is used when the NTFS file system is not feasible due to overloading of data structures.

Future

Since Microsoft will no longer support MS-DOS-based operating systems, it is unlikely that new versions of FAT will be developed. NTFS is a superior file system to this in multiple ways: efficiency, performance, and reliability. Its main disadvantage is the excessive size that it wastes in small volumes and its limited support in other operating systems. Its specifications are a trade secret; However, this is changing, thanks to reverse engineering, as it is now possible to read and write to NTFS partitions on Linux with tools like NTFS-3G.

FAT is currently the common file system for removable storage media (with the exception of CDs and DVDs). FAT12 is used on floppy disks, and FAT16 on all other media (eg memory cards and USB sticks) up to 2GB (almost obsolete today). 4GB to 32GB USB sticks and cards usually use FAT32 to overcome the limitations of the older version. Memories of 64GB and more use the exFAT system for the same reason. FAT is used for compatibility reasons.

Support for formatting partitions with FAT32 in Windows is limited to partitions up to 32 gigabytes, forcing users to use NTFS or use third-party utilities outside of Windows. This limitation affects when creating partitions, but not to use: Windows can access FAT32 drives up to 2 terabytes.

Although at the time of installation it does not allow you to format a partition with FAT32 larger than 32 GB, and will force you to use NTFS. The solution is to format the disk in FAT32 first (for example with the help of a GNU/ LiveCd Linux or third-party utilities), and then install Windows.

Structure

The FAT file system is made up of four sections:

1. The boot sector. It is always the first section of the partition (volumen) and includes basic information, pointers to the other sections, and the direction of the startup routine of the operating system.
2. La FAT region. Contains two copies of the File Allocation Table (for security reasons). These are partition maps, indicating what clusters They're busy with the files.
3. La root directory region. It is the main index of folders and files.
4. La data region. It is the place where the content of files and folders is stored. Therefore, it occupies almost the entire partition. The size of any file or folder can be enlarged as long as sufficient clusters free. Each cluster is linked to the following by a pointer. If a given cluster It does not take full care, its remaining space is wasted.

A partition is divided into a set of clusters of identical size. They are small discontinuous blocks. The cluster size depends on the FAT variant used. It varies between 2 and 32 kilobytes. Each file occupies one or more clusters depending on its size. So a file is represented by a sequential chain of clusters (a linked list). Each cluster in the chain does not have to be adjacent to the previous one. This is what causes fragmentation.

The file allocation table consists of a list of entries. Each entry contains information about a cluster:

• The address of the next cluster in the chain.
• If relevant, the indication of "File end" (which is also the end of the chain).
• A special character to indicate that the cluster is defective.
• A special character to indicate that the cluster is reserved (i.e. occupied by a file).
• Number zero to indicate that the cluster is free (can be used by a file).

The size of these entries also depends on the FAT variant in use: FAT16 uses 16-bit entries, FAT32 uses 32-bit entries, etc.

The root directory

Three directory entries under a VFAT file system (FAT32)

This index is a special type of file that stores the sub-folders and files that make up each folder. Each directory entry contains the name of the file or folder (maximum 8 characters), its extension (maximum 3 characters), its attributes (file, folder, hidden, system, or volume), the date and time of creation, the address of the first cluster where the data is, and finally, the size it occupies.

The root directory occupies a specific position in the file system, but the indexes of other folders occupy the data zone like any other file.

Long names are stored across multiple index entries for the same file or folder.

Licensing

Microsoft applied for a series of patents for key elements of the FAT file system in the 1990s. Its popularity and compatibility make it the format of choice for flash drives in digital cameras, mobile phones, and tablets for example.

In December 2003, Microsoft announced that it would begin to market use licenses for FAT at a cost of $0.25 per unit sold. with a maximum of $250,000 per license agreement.

So far, Microsoft has cited four patents on FAT in support of its claims. All four refer to the implementation of long names:

• Patent 5.74590: Method and system to access a file using long names with different file name formats. It covers a way of generating and associating a short name "8.3" with a long one (for example, "Microsoft.txt" -largo- with "Micros~1.txt" -corto-). As well as how to list short names in conflict (e.g., "MICROS~2.TXT" and "MICROS~3.TXT").
• Patent 5.579.517: Common namespace for both short and long file names. Cover a method to chain multiple short-name entries into the index to store a long name. La Public Patent Foundation He successfully challenged this patent.
• Patent 5.758.352: Similar to the previous one. It was also successfully challenged.
• Patent 6.286.013: Method and system to provide a common namespace for both long and short file names in an operating system. This patent claims the methods used in Windows 95, 98 and ME to make long file names compatible with MS-DOS. Apparently, it does not affect any FAT implementation other than that of Microsoft.

Some experts believe that these patents do not really cover the use of FAT on consumer removable media.

On the other hand, the document Microsoft Extensible Firmware Initiative FAT 32 File System Specification, FAT: General Overview of On-Disk Format, published by Microsoft, guarantees a series of rights that could be interpreted as a license to implement FAT on other operating systems.

Challenges

Due to popular outcry for a reexamination of these patents, the Public Patent Foundation sent evidence to the Patent Office of previous work by Xerox and IBM. The Office recognized that there were "substantial doubts of patentability" and opened an investigation to review those patents.

Finally, said review has confirmed the validity of the patents in January 2006.