原始 Paper

http://www.computerscijournal.org/dnload/Wasim-Ahmad-Bhat-and-S-M-K-Quadri/OJCSV03I01P161-164.pdf

标题

回顾FAT数据结构，FAT32文件系统

概述

FAT 文件系统是一种最原始，可兼容并且简单的文件系统，它如今仍然在支撑着各种数码设备的运行，比如mini MP3播放器，智能手机和数字相机。由于它的简单性和经典性，这种文件系统几乎被所有的操作系统都支持。这篇论文回顾了FAT数据结构中最基本，最重要的一些设计技巧，约束，规则去构建FAT32文件系统中的块数据结构。

介绍

FAT (文件分配表) 文件系统于20世纪70年代开始发展并且早在20世纪80年代就被微软的MS-DOS操作系统所支持。
它也是包括DR-DOS, FreeDOS, MS-DOS, OS/2(v1.1)和Microsoft Windows (一直到Windows Me)在内的各种操作系统的原生文件系统。
FAT 最初是为了500KB以内的软盘设备而开发的。
随着存储容量的提升，FAT也被增强来支持大容量存储设备。
例如我们有三种完整的，具有规范文档的FAT文件系统类型：FAT12, FAT16, FAT32。
exFAT是微软最近编写的, 同时还有KFAT, TFAT, FATTY, 他们都是可靠的，增强了的，他们实际上都是被相同的研究人员所设计的。

某些标准，ECMA-107和ISO/IEC 9293对FAT的设计仅包含了缺乏长文件名支持的FAT12和FAT16。

当和其他的文件系统做对比，FAT的性能很缺乏，因为它使用了简单的数据结构，这使得文件操作的非常耗时并且在遇到许多小文件时磁盘空间的利用率是低效的。
但是由于这种简单而经典的设计，使得其被几乎所有现存的个人计算机操作系统所支持。这使他成为了一个对于固态存储卡和在不同操作系统之间共享数据的便捷方式有用的格式。
在当今世界，有一些可携带的数字设备，像是mini MP3播放器，智能手机和数码相机开始逐步成为我们生活的一部分。这些设备会频繁地和PC机交换数据。PC机识别这些设备作为标准的USB大容量设备，并且自动地挂载文件系统卷。这仅当该设备使用的文件系统受该PC的操作系统支持时才能实现。
这就是为什么FAT32文件系统是方便的，它可以寻址大容量存储介质并且被所有主流桌面操作系统所支持, 它仍然在便携式数码设备中广泛地被使用。

FAT32卷的数据结构顺序

下面的表展示了FAT32磁盘卷中数据结构的组成顺序。

Boot Sector
Reserved Sectors
FAT (Copy 1)
FAT (Copy 2)
File & Directory Sectors

一个FAT32文件系统由以下四个不同的区域所构成：

引导扇区被放置在了卷的最开头, 换句话说就是0号扇区。它包含了一个叫做BPB(BIOS Parameter Block)的区域。这个区域起始于偏移量11，包含了一些文件系统的基本信息。该扇区剩余的部分通常包含了boot loader的代码。
保留扇区紧跟在引导扇区之后。这个卷的保留扇区数被BPB表示在主引导扇区的偏移量14的位置处。通常来说，保留扇区在1扇区包含了文件系统信息，还有在6扇区包含了引导扇区副本。
文件分配表是一个32位宽条目所构成的数组，它被BPB指示在引导扇区的偏移量36处占据了大量的扇区。FAT32通常有两个FAT数据结构的拷贝为了确保冗余来检查修复磁盘。BPB中引导扇区的偏移量40处的第7个比特位标识了这个FAT是否被镜像了。正是因为这个区域的存在，所以这种文件系统被命名为FAT，后缀为32。
文件扇区和目录扇区构成了这个文件系统，它一直延伸到卷尾，它是文件和目录数据实际存放的位置。FAT32通常在文件目录扇区中的第一个簇放置根目录，并且该簇号还可由BPB在引导扇区的44号偏移量所表示。（簇是固定数量的连续扇区，该数字由BPB在卷的引导扇区的13号偏移量所表示）

FAT32文件系统卷中FAT的数据结构

所有的FAT文件系统最初都是为了IBM PC机架构所开发的，因此FAT文件系统在BPB，FAT和文件目录区中的条目中使用了小端格式。
FAT数据结构是一个表，它存储了簇的相关信息，如表示了某个簇是否被使用，空闲或不稳定。
此外，它还存储了某个文件的所属的簇的链接信息。
根据被使用的FAT文件系统类型和卷的大小，簇大小可能有所不同每簇连续的扇区数可依次按大小为1, 2, 4, 8, 16, 32或64。
随着每年单位容量的存储器成本剧烈降低，簇数也在剧烈的增加，所以用于标识每个簇的比特数也在增长。
因此，FAT格式的连续的主要版本号使用用于寻址簇的一张表元素所使用的比特位数来命名：12, 16, 32, 64。
在FAT32文件系统中，FAT中每条目是32位，但是只有它的低28位被用于寻址2^{28个簇。因此，FAT32卷容量能够高达((2}28) * 64)/2KB，即8TB

基本设计技巧

每个文件和文件夹（除了Root文件夹）在FAT32卷中都有一个入口条目在它的父文件夹中，包含了名称，属性，大小等等，以及一个32位宽的簇号被分配给它。
对于给定编号的任意一个簇，FAT条目可以给定以下值：

FAT32簇入口值	描述
0x00000000	是空闲簇
0x00000001	保留
0x00000002 - 0x0FFFFFEF	被使用的簇，且值指向它在文件/目录被分配到簇链表中的下一个簇号
0x0FFFFFF0 - 0x0FFFFFF6	保留
0x0FFFFFF7	簇中有一些坏扇区，不稳定
0x0FFFFFF8 - 0xFFFFFFFF	文件或目录的最后一个簇，即链表尾标记

每个文件/文件夹可能会占用一个或多个簇，这取决于它的大小和每簇中的扇区数。
因此，一个文件被表述为由这些簇所组成的链表。
然而，这些簇物理上并不是必须相邻地存储在磁盘表面，更常见的是碎片化地分段存储。
让我们假设有两个文件叫做：MYFILE1.TXT和MYFILE2.TXT，如图1所示：它们当前都驻留在于FAT32卷中，前者是碎片化的占用3个簇，后者不是碎片化的，占用两个簇长。

MYFILE1.TXT的第一个簇被分配于0x00000029，根据其内容可得到另一个簇0x0000002A，然后0x0000002D其内容显示了该簇是链表的最后一个簇。
同理，对于MYFILE2.TXT分配的第一个簇是0x0000002B，根据其内容可得到另一个簇号0x0000002C，由其内容可得出这是其链表中最后一个簇。

约束

实际上，一个FAT32的FAT条目真正只使用了低28位来寻址簇。它的高四位被保留下来，并且只能当卷被格式化时才能改变，那时整个32位的FAT条目都应该被清零，包括它的高四位。这意味着所有的32位簇条目值：0xA0000000, 0xB0000000, 0x00000000都表示一个空闲簇，因为他们的低28位都被置为0。

假设一个32位空闲簇的值当前是0xA0000000，我们可以通过存储值0x0FFFFFF7来标记这个簇是损坏的。然而，因为当我们写入0x0FFFFFF7坏扇区标记时，我们必须保留高4位不变，所以这个32位的条目项需要包含的值最终为0xAFFFFFF7。

因为每个扇区的字节数被BPB所指示，它在引导扇区的11偏移量，它总是需要能够被4整除的，一个FAT32文件系统的FAT表条目永远不会跨越一个扇区的边界。

FAT表开头的两个条目存储了特殊值

第一个条目包含了在引导扇区的21号偏移量处的BPB副本，其长度为8位，指示了存储媒介类型。在该条目的高4位和低8位中的20位均被设置为1。
第二个条目存储了EOC标志。它的高两位有时候用于脏卷管理：若高位设置为1则表示上次关机是干净的，否则就是异常的。下一个最高位如果设置为1则表示先前的挂载未检测到磁盘I/O错误，否则就是检测到了。

由于头部的两个FAT条目存储了特殊值，所以并没有0号或1号簇。第一个可寻址的簇在FAT32的FAT数据结构中是2号簇，这就是为什么BPB在引导扇区的44号偏移量指示了根目录簇号不能低于2，且通常就是2。即，根目录就是在文件/目录区的起始处。

公式

此处计算的所有的扇区号都是相对于FAT32卷的第一个扇区，即引导扇区，并且不一定是直接映射到驱动器上，这是因为引导扇区不一定是驱动器的0号扇区，以下是C语言中的代码片段。

文件/目录区的起始位置，也就是2号簇的首个扇区，通过以下公式进行计算：

FirstDataSector = BPB_ResvdSecCnt + (BPB_NumFATs * FATSz)

BPB_ResvdSecCnt在引导扇区的14号偏移量，是保留区的扇区数

BPB_NumFATs在引导扇区的16号偏移量，是FAT数据结构的数目

FATSz在引导扇区的36号偏移量，表示一个FAT的副本所占据的扇区数

给定任意有效的数据簇号N，这个簇的第一个扇区号的计算如下：

FirstSectorOfCluster = ((N – 2) * BPB_SecPerClus) + FirstDataSector

BPB_SecPerClus在引导扇区的13号偏移量，是每个簇的扇区数

给定任意有效的数据簇号N，其FAT中的该条目的扇区号偏移计算如下

FATOffset = N * 4

ThisFATSecNum = BPB_ResvdSecCnt + (FATOffset / BPB_BytsPerSec)

ThisFATEntOffset = FATOffset % BPB_BytsPerSec

BPB_BytsPerSec 是每个扇区的字节数

上述计算的FAT扇区是属于FAT的第一个副本，如果想要使用第二个副本，则需要使用如下公式计算：

ThisFATSecNum = BPB_ResvdSecCnt + (FATOffset / BPB_BytsPerSec)+ FATSz

结束语与未来工作

在这篇论文中，我们讨论了FAT数据结构在FAT32中基本的，简单的设计技巧，并且回顾了操作FAT32中FAT数据结构所必须的约束和公式。由于其设计的简单性，它被广泛地支持小到小型数码设备，大到桌面操作系统。当然，还遗漏了一些事情，像是FAT数据结构的可靠性问题，兼容性问题，优化算法等等。

参考文献

Microsoft Corporation, “FAT32 File System Specification”, http://microsoft.com/whdc/system/platform/firmware/fatgen.mspx, 2000

微软公司，FAT32文件系统规范
Microsoft Corporation, “Extended FAT File System”, http://msdn2.microsoft.com/en-us/library/aa914353.aspx, 2007

微软公司，扩展FAT文件系统
M. S. Kwon, S. H. Bae, S. S. Jung, D. Y. Seo, and C. K. Kim, “KFAT: Log-based Transactional FAT File system for Embedded Mobile Systems”, In Proceedings of 2005 US-Korea Conference, ZCTS-142, 2005

KFAT: 为嵌入式移动系统设计的基于日志的事务性FAT文件系统
Microsoft Corporation, “Transaction-Safe FAT File System”, http://msdn2.microsoft.c0m/en-us/library/aa911939.aspx, 2007

微软公司，事务安全的FAT文件系统
Liang Alei, Liu Kejia, Li Xiaoyong , “FATTY :A reliable FAT File System”, Proceedings of the 10th Euromicro Conference on Digital System Design Architectures, Methods and Tools, Pages: 390-395, 2007.

FATTY: 一个可靠的FAT文件系统
Standards - Ecma-107
Standards - ISO 9293:1987
Standards - ISO/IEC 9293:1994
Michael D. Dahlin, “The Impact of Trends in Technology on File System Design“ University of California, Berkeley, January 23,

技术的发展趋势对文件系统的设计所带来的影响
Andries E. Brouwer, The FAT file system”, 2002-09-20 http://www.win.tue.nl/~aeb/linux/fs/fat/fat-1.html
“Microsoft MS-DOS Programmer’s Reference: version 5.0.”, Microsoft press. 1991.