FAT文件系统

FAT文件系统是微软在上个世纪七八十年代为DOS系统开发的一种文件系统。最初是FAT12系统，用在软盘上。后来计算机硬件不断发展，逐渐推出了FAT16和FAT32。 它们大体上是一致的，本质的不同之处在于描述文件存储的FAT表中各元素的长度分别为12位, 16位和32位。

物理上有各种各样的存储设备，比如说机械硬盘、固态硬盘、CD/DVD等等。在操作系统中将之抽象为一个个的分区，根据我们使用Windows系统的习惯， 会把一块硬盘分为C、D、E……盘，在C盘中安装操作系统，在D盘中安装应用程序，在E盘中存储文件。如果插入了一块移动硬盘或者U盘，Windows会将之称为F、G……盘。 每一个分区都会有一个文件系统进行管理，关于磁盘分区可以参考《鸟哥的私房菜》， 在后续的文章中也将进行详细的介绍。

各种物理设备都会有一个最小的存储单元，比如：机械硬盘是扇区(Sector)，SD卡块(Block)。通常一个扇区或者块有512个字节，具体由存储设备的实现决定。 一般对于存储设备的访问都是以最小存储单元为单位进行访问的，这样可以节省空间提高访问效率。 在FAT文件系统中，文件是以簇(Cluster)为单位进行存储的。它把若干个扇区作为一个整体对待，具体一个簇对应多少个扇区由FAT系统的实现决定。 因为FAT表位宽的限制，FAT12和FAT16支持的簇的数量要远比FAT32小，簇的数量也是用于区分这三种FAT系统最有效的方法。

需要注意的是，FAT文件系统的数据是小端(little-endian)存储的。一个FAT格式的磁盘分区由如下所示共四个部分组成，它们在磁盘上是先后依次排布的。 左图是从于渊的Orange一书中抠出的图，它描述的是一个FAT12的文件系统， 它与FAT16和FAT32的组织形式是一样的，从第0扇区开始依次是：

1. 保留区
2. FAT表区
3. 根目录区(在FAT32系统中不需要该区)
4. 文件和目录存储区

在这四个部分中一共有3个重要的结构：保留区中的BPB，FAT表和目录结构。BPB描述了磁盘分区和文件系统的基本信息，FAT表则记录了文件内容的具体存放地址， 目录结构描述了文件的各种属性及其占用的第一个簇编号。 下面我们将结合文件系统原理分别对它们进行介绍。

1. 保留区和BPB

从磁盘分区的第一个扇区开始就是保留区了。该区记录了磁盘和文件系统的很多信息，称为零扇区(\(0^{th}\) Sector)；有时也用于操作系统的引导，此时我们称之为引导扇区(boot sector)。 对于FAT而言，零扇区中的BPB(BIOS Parameter Block)结构是至关重要的，它记录了包括扇区大小、每个簇包涵多少个扇区等各种参数，其中还有一个字段描述了保留区所占扇区个数。

最早FAT系统是运行在一张5.25英寸的软盘上的，只有单面和双面两种软盘，只用第一个字节就可加以区分。后来在2.X版的DOS系统中引入了BPB结构，之后所有的FAT分区就必须在引导扇区中添加一个BPB结构。 但是此时的FAT系统只支持32M的磁盘，因为用于描述扇区数量的字段只有16位，最多可以由65536个扇区。所以在3.X版的DOS系统中添加了一个32位的字段用来描述扇区数量。

在于渊的Orange一书中，开篇就用不到20行的代码写了一个"操作系统"， 在虚拟机中显示了一个红色的"Hello, OS world!"。事实上，这个例子只是在引导扇区上做了文章。不知道什么历史原因，如果第一个扇区中第511和512个中的内容是0xAA55， 那么BIOS就会将其判定为引导扇区。在FAT中一个扇区的字节数可以通过字段BPB_BytsPerSec修改，不过一般都是512个字节的。官方文档中强调引导扇区的标识符0xAA55一定是在零扇区的第511和512位， 不能认为是第一个扇区的最后两个字节，因为扇区的字节数是可以改变的。

比较容易产生疑惑的一点是，零扇区的第一个字段是一条3字节的无条件跳转指令BS_jmpBoot。它实际上应当是X86架构的一条指令，在Orange一书中的例程中的第一行就是"org 07c00"， 用于跳转到内存地址0000:7c00的位置上。

现在看来，前两段中描述的内容对于我们的XTOS是没有意义的。首先，在我们的开发板上没有BIOS这么个东西。BIOS也是上个实际七八十年代的古老产物， 它是固化在计算机主板上的一个ROM芯片上的一段程序，是PC机启动时执行的第一段程序。而我们的实验板启动时执行的第一段程序都是我们自己写的，所以一定程度上，我们写的XTOS是一个BIOS系统。 其次，BS_jmpBoot的跳转指令是X86架构的指令，对于ARM处理器是没有任何约束的。

在一开始我们就已经介绍过，在FAT中文件的资源分配是以簇为单位进行的。字段BPB_SecPerClus描述了一个簇所拥有的扇区数量，它必须非零且是2的指数幂。 另外，官方文档要求一个簇的大小，即BPB_BytsPerSec * BPB_SecPerClus，不能超过32K。需要注意的是，簇是针对文件和目录存储区而言的。 因为保留区、FAT表区中记录的是一些描述信息，不存在文件存储资源分配的问题，所以它们仍然是以扇区为单位进行操作的。

这里依次介绍BPB中各个字段，详细解释参见微软的官方文档。 FAT32在前36个字节的字段与FAT12/FAT16是一致的，其定义和描述如下表所示，其中前缀"BPB_"是BPB结构的字段，"BS_"是引导扇区的字段。

因为接下来的字段对于FAT12/FAT16和FAT32系统都不一样，所以需要根据这些公共字段判定文件系统类型。下面分别介绍FAT12/FAT16和FAT32在36字节以后的字段定义。

我们可以根据上述的BPB的字段计算FAT系统的各个部分的偏移地址和大小。因为FAT表区就在保留区之后， 所以它的偏移地址和大小可以计算如下，对于FAT32系统BPB_FATSz由BPB_FATSz32代替。

        FatStartSector = BPB_ResvSecCnt;
        FatSectors = BPB_FATSz * BPB_NumFATs;

根目录区的偏移地址和大小可以计算如下，计算根目录扇区数量时乘以的32是指目录中的一条记录长度为32个字节。 加上BPB_BytsPerSec再减去1是为了做除法运算时向上取整的。再FAT32系统中不存在根目录区，BPB_RootEntCnt取值总是0。

        RootDirStartSector = FatStartSector + FatSectors;
        RootDirSectors = (32 * BPB_RootEntCnt + BPB_BytsPerSec - 1) / BPB_BytsPerSec;

根目录区之后就是数据区，用于记录实际的文件和目录内容的区域。我们可以通过如下的语句计算数据区的偏移地址和大小。

        DataStartSector = RootDirStartSector + RootDirSectors;
        DataSectors = BPB_TotSec - DataStartSector;

2. FAT表

在文件的存储方式中，我们介绍说为了防止存储空间的碎片化，人们设计了一种链式存储方法。 但是这种方法对于文件内容的随机访问而言，其查找效率是很低的，因而又增加了一个FAT(File Allocation Table)查找表的概念，专门用一块空间记录各个文件对于簇的使用情况。

在保留区之后就是FAT表区，FAT表的数量由保留区中字段BPB_NumFATs来决定，一般都会有两个FAT表。其中一个表用作备份，当一个表所在扇区损坏时，还可以从备份中获取数据。

FAT表的前两项保留，不对文件和目录区进行映射。第一个表项的低8位应当与保留区中字段BPB_Media一致，描述介质类型，其余各位用'1'填充。 第二个表项用于标记磁盘是否发生读写错误，或者上次挂载时是否正常连接。

FAT表以链的形式记录了每一个簇被文件占用的信息。表中的每个单元对应一个簇，单元中记录的是其后继，即同一个文件的下一个簇的编号。 如右图所示，描述了两个文件的查找表，文件A使用了编号为7、2、10、12的共四个数据块，文件B使用了编号为6、3、11、14四个数据块。格子中的-1标识着文件的结束。

FAT表项中的值除了记录簇的占用信息外，还用两个特殊的值，分别标记文件的最后一个簇和坏簇。有时把标记文件结束的值称为EOC标记，对于FAT12为0x0FFF，对于FAT16为0xFFFF， 对于FAT32则是0x0FFFFFFF。被标记为坏簇的簇将不再被分配，对于FAT12为0x0FF7，FAT16为0xFFF7，FAT32为0x0FFFFFF7。所有为0的表项所对应的簇都是空闲的，可以被分配的簇。

FAT表的大小与具体实现的类型和磁盘大小有关，FAT12中表的每个记录都是12位宽的，FAT16则是16位，FAT32是32位。因此磁盘的簇数和表的位宽决定了FAT表大小的下限。 FAT系统得以应用的关键就是准确的定位FAT表项，下图分别是三种FAT表项的排布示意图。我们用FAT[n]表示第n个FAT表项，从0开始索引。 从图中我们可以看出FAT16和FAT32的表项相比于FAT12要容易计算很多，因为它们的每个表项都完整的占用了两个或者4个字节，而FAT12则占用了1.5个字节。

图1 FAT表项示意图

一个FAT表可能占有多个扇区，对于FAT12/FAT16和FAT32在保留区中分别用字段BPB_FATSz16和BPB_FATSz32来描述。对于FAT32系统BPB_FATSz16一定为0， 在BPB_FATSz32中指定FAT表的大小。若要定位第n个FAT表项，我们需要先计算出该表项所在的扇区，将之加载到内存中； 再计算FAT[n]在该扇区中的偏移量。FAT16的表项的定位最简单，没有过多的额外操作，如下：

        nFATSecNum = BPB_ResvdSecCnt + (N * 2 / BPB_BytsPerSec);
        nFATEntOffset = (N * 2) % BPB_BytsPerSec;
        // 读一个FAT16表项的值
        ReadSector(SecBuf, nFATSecNum);
        nFATEntValue = *(uint16*)&SecBuf[nFATEntOffset];
        // 写一个FAT16表项的值
        ReadSector(SecBuf, nFATSecNum);
        *(uint16*)&SecBuf[nFATEntOffset] = newEntValue;
        WriteSector(SecBuf, nFATSecNum);

FAT32的表项虽然有32位，但其高四位是保留的。在格式化磁盘的时候，保留位一般被初始化为0；在文件系统正常工作时，不应当修改保留位的内容。 所以我们在读和写FAT32表项的时候应当用掩码0x0FFFFFFF保护保留位的内容，其计算方法如下：

        nFATSecNum = BPB_ResvdSecCnt + (N * 4 / BPB_BytsPerSec);
        nFATEntOffset = (N * 4) % BPB_BytsPerSec;
        // 读一个FAT32表项的值
        ReadSector(SecBuf, nFATSecNum);
        nFATEntValue = *(uint16*)&SecBuf[nFATEntOffset] & 0x0FFFFFFF;
        // 写一个FAT32表项的值
        ReadSector(SecBuf, nFATSecNum);
        tmp = *(uint16*)&SecBuf[nFATEntOffset];
        tmp = (tmp & 0xF0000000) | (newEntValue & 0x0FFFFFFF);
        *(uint16*)&SecBuf[nFATEntOffset] = tmp;
        WriteSector(SecBuf, nFATSecNum);

由于FAT12的表项只占用了1.5个字节，所以其计算方式相对复杂一些。根据表项索引n为奇数或者偶数，需要两个读写方案，其计算方法如下，至于公式是如何推导的这里就不再详细描述了：

        nFATSecNum = BPB_ResvdSecCnt + ((N + (N / 2)) / BPB_BytsPerSec);
        nFATEntOffset = (N + (N / 2)) % BPB_BytsPerSec;
        // 读一个FAT12表项的值
        ReadSector(SecBuf, nFATSecNum);
        if (N & 1) { // 奇数情况
            nFATEntValue = (SecBuff[nFATEntOffset] >> 4) | ((uint16)SecBuff[nFATEntOffset + 1] << 4);
        } else { // 偶数情况
            nFATEntValue = SecBuff[nFATEntOffset] | ((uint16)(SecBuff[nFATEntOffset + 1] & 0x0F) << 8);
        }
        // 写一个FAT12表项的值
        ReadSector(SecBuf, nFATSecNum);
        if (N & 1) { // 奇数情况
            SecBuf[nFATEntOffset] = (SecBuff[nFATEntOffset] & 0x0F) | (newEntValue << 4);
            SecBuf[nFATEntOffset + 1] = newEntValue >> 4;
        } else { // 偶数情况
            SecBuf[nFATEntOffset] = newEntValue;
            SecBuf[nFATEntOffset + 1] = (SecBuff[nFATEntOffset + 1] & 0xF0) | ((newEntValue >> 8) & 0x0F);
        }
        WriteSector(SecBuf, nFATSecNum);

3. 目录结构和根目录区

在FAT系统中，目录实际上就是一种特殊的文件，只是用一个属性将其标记为目录。目录中保存的是一个32字节为单位的线性表，这个表中记录了文件名、创建时间、起始簇编号等信息，如表1所示。

在这个表中的第一个字段中记录了文件名称，它只有11位，前8个字符记录主文件名，后3个字符记录扩展文件名，两个部分如果不足8字节或3字节，就左对齐，不足的部分用空格(0x20)填充。 我们在使用操作系统的时候文件名和扩展名之间是用'.'进行分隔的，但它是不会在DIR_Name体现的。当DIR_Name[0] = 0xE5时，表示目录项是空的，不对应任何文件或目录。 DIR_Name[0] = 0x00除了和0xE5一样也表示目录项是空的外，还表示其后所有的目录项也都是空的，它们的DIR_Name[0]都是0。 表中的的第二个字段描述了文件的属性。DIR_FstClusHI和DIR_FstClusL0则记录了目录项的簇编号，对于FAT12和FAT16系统而言DIR_FstClusHI为0。 其它字段则描述了文件的创建、访问、修改的日期和时间。

每个FAT系统都会有一个特殊的目录——根目录(root directory)，而且只有一个。根目录不同于其它目录的是，它没有名称，也不需要日期和时间戳，在格式化分区时就已经存在了。 对于FAT12和FAT16系统，专门有一个根目录区紧跟在最后一个FAT表后，而且其中的目录入口项数是由BPB_RootEntCnt确定了的。而在FAT32系统中，没有一个专门的根目录区。 它将其当做一个普通目录记录在文件和目录存储区中，在保留区中用BPB_RootClus记录其第一个簇编号。

4. 总结

FAT文件系统最早是针对IBM-PC和MS-DOS系统开发的，一共有FAT12, FAT16和FAT32共三个版本，它们之间的差别主要在FAT表的位宽和支持的簇数量上。

FAT文件系统把一个分区分为了四个部分，在保留区中记录了分区和文件系统的基本信息；在FAT表区中以簇为单位记录了存储区的占用情况； 根目录区则是文件系统树形结构的起点，在FAT32中取消了根目录区，将根目录当做一个普通的目录来实现，在保留区中用一个字段记录了根目录的起始簇编号。

本文中还简单介绍了FAT文件系统中的三个主要结构：BPB，FAT表，目录表。关于FAT更详细的内容可以参考微软的官方文档。