FAT 文件系统¶

导读¶

文件、目录和文件系统¶

文件系统是对文件的一种组织形式，所以文件固然也就是文件系统中至关重要的部分，了解文件系统首先就要了解文件的构成。

不论是哪种类型的文件，不论是 .doc、.ppt 还是 .txt 抑或是 .bin，在硬盘的视角来看，它们中的数据实际上都是一系列二进制的数据块，而类别的区别只在于这些数据内部的组织形式，并不会让它们看起来是除了二进制数据块以外的其他样子。

但是如果一个文件只有数据块又不太够，文件名称是用户用以区分不同文件的关键信息，文件名称有时候对于文件系统来说太复杂了，所以文件系统会用一些特殊的方式记录用户提供的文件名称并通过其来识别不同的文件，这种记录有时候会呈现以标识符的形式，在 FAT 文件系统中则是一系列字符串。

除此之外，文件还需要一些其他的信息，例如其类型、数据在硬盘上的位置、尺寸、访问权限、创建或修改日期等等。

可见，文件由两个关键的部分组成，一个是文件的数据，也就是一系列二进制数据块，另一个则是文件的信息，它用来区分不同的文件并在硬盘上定位到文件数据的位置。

在文件系统组织文件的时候，其实际上就是在建立索引文件的数据结构，由于文件是由两部分构成的，文件系统中也就存在着两种主要的数据结构，分别用来索引文件的这两个组成部分。

其中一个数据结构用来索引文件的信息，这部分数据结构一般呈现树形的结构，文件系统中的文件目录就是由这个数据结构所维护的，树中每个节点都存储着一个文件或是目录的信息。

1
2
3
4
5
6
7
8
9

root/
  ├── system/
  │   └── kernel.elf
  └── home/
      ├── main.cpp
      └── folder/
          ├── boo/
          ├── baz
          └── bar/

另一个数据结构则用于通过文件的信息来索引文件的数据，由于一个文件可能跨越数个甚至数十、数百个扇区，由于文件时时刻刻都可能会被更改，所以没有办法预先给文件分配一段固定的、连续的、大小适当的空间，因此文件的数据往往分散在磁盘的各个位置，这时就需要一个数据结构来将这些游离的数据块串接起来。

说到这里，可能大家就已经能猜到，这部分数据结构一般以链表的形式出现。每一个文件块都对应着一个下一文件块的位置信息，而第一个文件块的位置信息则存储于文件的信息中。

下图表示了一个文件系统磁盘中可能的样子：

• #0 标号的内存空间对应着系统的根目录 / 节点，其内部有两个有效的文件信息，分别是 system 和 home，均为目录类别。
• system 首文件块指向 #8，并且 #8 为其最后一个文件块，因此 #8 实际上就对应着 /system/ 节点，其中存储了 kernel.elf 一个文件的信息。
• 对于 home，首文件块指向 #14，其下一个文件块为 #16，并且是最后一个文件块，因此 #14, #16 共同构成 /home/ 节点，在这个节点中存储了两个有效文件信息，分别是 boo.baz 和 bar，分别是文件和目录。
• kernel.elf 首文件块为 #4，#4 下一个文件块为 #6，#6 为最后一个文件块，因此 kernel.elf 对应的文件数据为 #4, #6 上的数据。
• boo.baz 首文件块为 #10，后续文件块依次为 #12、#5。因此 #10, #12, #5 共同构成 boo.baz 文件的数据
• bar 首文件块指向 #18，后续文件块为 #11，因此 #18, #11 共同构成了目录树中的 /home/bar/ 节点的子树信息

由上图可以看出，目录树的遍历方式是要与数据结构中树的遍历方式有很大不同的。每一个节点实际上都对应着一个存储着其子节点的文件的信息的数组，通过这个数组，可以获得子节点对应文件的首块信息，再依据链表就能够获得全部的文件数据。只有当取得了全部的文件数据，才可以进入下一层的节点。

简单来说，就是在 / 目录下，我们只能得到 system/ 和 home/ 的信息，但是我们不能从这些信息中直接得到 system/ 下或是 home/ 下有什么文件，除非我们把它们的数据完整地读取出来。

而在一般的数据结构中，对于根节点 root，我们只需要访问 child = root->children[0] 就可以获得整个子节点，得到的 child 就包含了其所有的子节点数据，而不需要额外的加载操作。

现在，假设我们需要访问 /system/kernel.elf 文件，那么就需要：

• 首先从树的根部开始，找到类型为目录，名称为 system 的信息。
• 从信息中读取出目录数据的第一个块 #8，并根据链表中的信息读入整个目录，由于这里只有一个块，所以就读入 #8。
• 在目录的数据中找到类型为文件，名称为 kernel.elf 的信息。
• 从信息中读出文件数据的第一个块 #4，并根据链表读入 #6，得到整个文件。

为了提高文件读写的速度，系统一般会维护一个打开的文件表 (Open-file table) 用于维护所有打开的文件的信息，所以一般来说，当打开一个文件的时候，除了会将它的全部数据就被读取到内存中，还会将其信息添加到打开文件表中，后续所有的增删改都只会对内存中的数据起作用，直到文件关闭时才再次写回磁盘。这样就避免了每次读写过程中对文件数据的定位以及读取。

FAT 文件系统¶

导读中的内容只是对文件系统的一种简单的概述，不同的文件系统会有不同的组织文件的方式，但核心总还是离不开怎样组织文件的数据以及如何通过文件的信息索引到文件的数据，区别大抵是数据结构的差异以及具体实现上的差异。

在上世纪出现的 FAT 中，由于软盘随机读取的性能奇差，所以如果像上文中图片绘制的那样，在文件数据块的末尾添加上下一个文件块的信息，糟糕的问题就会出现：如果尝试在文件尾部添加些什么，那需要遍历之前所有的文件块才能知道最后一个文件块在哪个位置！

为此，工程师们将所有文件块中关于下一个块的信息独立出来，存放在磁盘中的一个连续的空间内，这个空间也被称作文件分配表 (File Allocation Table)，也就是 FAT 实际的意义。这样，只需要提前把这一部分空间读取到内存中，就可以很快地定位到文件任意个块的信息了。

同时，这样做还有一个好处，一个 512 字节或是其整数倍的块需要分配几个字节给下一个块的块号，导致每个文件块实际数据大小不是 2 的幂，现在由于将这部分信息独立出来，所以每一个文件块都是完整的 512 字节或是 512 字节的倍数。

但是，如果每个数据块只占据 1 个扇区的话，对于大磁盘来说，需要的块号还是太多了，于是工程师就提出了簇 (cluster) 的概念，一簇由许多个扇区组成，而这个簇就相当于前文中的数据块。

在 FAT 中存储簇号而不是块号就大大减少了 FAT 的大小。这样虽然增加了碎片，但提升了文件读写的效率。

文件系统的实现¶

在了解了文件系统是怎样组织和存储文件之后，对于如何从文件系统中读取文件应该有了思路。

但是细细一想又会发现很多问题，例如：根目录存储在磁盘的哪个位置、如何知道一个簇有多大、文件名是如何存储的、怎样才代表当前的簇是文件的最后一个簇等等

这便是因为文件系统很多具体的细节还没有落实，程序还无法从现有的文件系统中获得需要的数据。而这就是本节的目的，通过阅读 微软关于 FAT 文件系统的规范文档，对 FAT 文件系统进行抽象，并且提供接口来解决上面提到的种种问题。

定义与注解¶

第一章大体可以略过，其中较为重要的概念如下：

• 簇 (cluster)： 一组逻辑连续的扇区。卷内的每个簇都可以通过一个簇号 N 指代 (referred to)。簇是文件分配的最小单元 (A unit of allocation)，给任何一个文件所分配的全部空间的大小 (All allocation for a file) 必须是簇的整数倍。
• 分区 (partition)： 在一个卷内的一系列扇区
• 卷 (volume)： 一个逻辑上的连续的扇区地址空间

FAT 卷结构¶

第二章主要介绍了 FAT 格式卷的结构，除了上文中提到的用来存储下一个簇信息的 FAT 区域 (FAT Region) 以及存储文件数据的区域 (File and Directory Data Region) ，还包括了一个保留区 (Reserved Region) 和一个根目录区 (Root Directory Region) 。

一个 FAT 格式的卷结构大概长得就像下面这样

BPB¶

在 FAT 格式的卷的首扇区，有一个叫做 BPB (Bios Parameter Block) 的数据结构，其主要存储了关于当前卷上 FAT 文件系统的关键信息，包括了文件系统各个区域的首扇区号，以及簇大小等等。

对于 FAT12/16 和 FAT32，它们的 BPB 结构在首 36 字节上完全一致：

从第 37 字节开始，FAT12 和 FAT16 卷上的 BPB 结构如下：

文档在接下来的部分介绍了如何初始化一个 FAT 卷，由于目前只需要读取 FAT 卷，所以可以忽略章节 3.4。

在 3.5 章节中文档就介绍了如何在装载卷时判断 FAT 的类型，其中关键的判断算法为

1
2
3
4
5
6
7

if(CountofClusters < 4085) {
  /* Volume is FAT12 */
} else if(CountofClusters < 65525) {
  /* Volume is FAT16 */
} else {
  /* Volume is FAT32 */
}

也就是说，FAT 的类型只与簇的数量有关，而与磁盘的大小、扇区数量以及 BPB 中的 BS_FilSysType 域都无关，其中

• FAT12 不能有超过 4084 个簇
• FAT16 不能有超过 65524 个簇，也不能少于 4085 个簇

FAT¶

对于不同的 FAT 格式，FAT 表中每个条目 (entry) 的大小不同：

• 对于 FAT12 而言，每个条目长 12 位
• 对于 FAT16 而言，每个条目长 16 位
• 对于 FAT32 而言，每个条目长 32 位

这时候就发现了，原来 FAT 后面的数字就是指代的 FAT 表中每个条目的长度，因此对于我们需要实现的 FAT16，每个条目长 16 位

FAT 条目中可能的存储值及其含义如下，其中 MAX 指代磁盘中合法的最大的簇号：

FAT 表中第一个保留的条目 FAT [0] 包含了 BPB_Media 域中的内容，其他的位被设置为 1，对于 FAT32 高四位同样不进行更改。

例如，如果 BPB_Media 的值为 0xF8，那么

• 对于 FAT12，值为 0xFF8
• 对于 FAT16，值为 0xFFF8
• 对于 FAT32，值为 0xFFFFFF8

第二个保留的条目 FAT [1] 在格式化时会被格式化工具赋一个 EOC 值，具体用处不明。

对于 FAT12 而言，由于空间有限，所以并没有额外的标记位；对于 FAT16 和 FAT32 而言，Windows 系统可能会使用高两位作为脏卷的标记位，其中最高位为 ClnShutBit，如果该位置位，则意味着上一次该设备没有被正常卸载，可能需要检查文件系统的完整性；次高位为 HrdErrBit，如果该位置位，则标明读写功能正常，如果置 0 则代表遇到了 IO 错误，提示一些磁盘扇区可能发生了错误。

目录¶

到目前为止，BPB 以及 FAT 表我们都已经清楚了，这样我们可以顺利地找到根目录所在的区域并且读取根目录所包含的所有数据了：

对于 FAT16，根据保留区的大小以及 FAT 的大小可以计算出根目录区的首扇区位置，根据根目录区首扇区位置和根目录区大小就可以读取全部根目录区数据

实际上，目录同样是一个由目录条目构成的数组，其中每一个目录条目都是一个 32 字节长度的数据结构，而正是这个数据结构中存储的数据描述了一个目录中存储的文件或是一个子目录的详细信息，例如它的创建日期和时间、名称或是最重要的首簇簇号等等。它的完整结构如下：

其中提到了一些概念，如短名称、文件属性以及一些仍然不明确的结构，如日期和时间的表示格式，如果继续阅读，则会发现文档也一一对它们作出了解释。

短名称为一种表示文件名称的格式，其 11 字节长度的域被分为 8 字节和 3 字节的空间，其中 11 字节用来存储文件不含扩展名的部分，而后 3 字节用来存储文件的扩展名，在存储名字的时候，所有的字母都会以大写字母的形式存储。

同时，短名称的存储方式会在文件名长度小于最大长度时在其后面填补空格，例如 FOO.BAR 在存储时由于文件名为三字节，所以会在其后填补 5 个空格，存储为 FOO BAR

除此之外，短名称域还遵循以下规则：

• 若首字节为 0xE5 则代表当前条目为空
• 若首字节为 0x00 则同样代表当前条目为空，并且还代表当前条目之后的所有条目都为空
• 首字节不能为空格，也就是说文件名不能以空格开头
• 目录中不能出现名称相同的两个条目
• 不能出现小写字母
• 不能出现ASCII 值小于 0x20 的字符（控制字符）以及 0x22、0x2A、0x2B、0x2C、0x2E、0x2F、0x3A、0x3B、0x3C、0x3D、0x3E、0x3F、0x5B、0x5C、0x5D、0x7C（部分特殊符号）

然而，如果文件名称很长的话，短名称就显得不太够用了，所以 FAT 还额外提出了长名称解决方案，并且称存储短名称的条目为 SFNEntry，存储长名称的条目为 LFNEntry。

在长名称解决方案中，一个文件会对应一个短名称的条目和一系列长名称的条目。短名称条目存储文件名称的前数个字符和扩展名，而长名称则存储文件的全部名称。

在目录中，一个文件对应的长名称条目和短名称条目连续存储，其中地址从低到高依次存储：

• 第 N 个长名称条目
• 第 N-1 个长名称条目
• …
• 第 1 个长名称条目
• 短名称条目

但是目前短名称足够使用了，所以不妨暂时跳过长名称的进一步介绍和实现。

文件的属性使用按位枚举的方式表示，其中的六个二进制位分别如下：

文件的日期和时间有特殊的存储格式

其中文件的日期包括三个部分：

• [4:0]：日（从 1 至 31）
• [8:5]：月（从 1 至 12）
• [15:9]：从 1980 年起的年份偏移（从 0 至 127）

文件的时间同样也包括三个部分：

• [4:0]：从零起经过的 2s 间隔数（从 0 至 29）
• [10:5]：分（从 0 至 59）
• [15:11]：时（从 0 至 23）

可以看到，秒的精度为 2s，这也就引出了 CrtTimeTenth 这个域，其精度为 10ms，范围从 0 至 199，正好填补了 2s 之间的空缺，使得精度提高到 10ms。

参考资料¶

• FAT - OSDev
• File Allocation Table - Wikipedia
• 南京大学操作系统课程中关于 FAT 和 UNIX 文件系统知识的讲解 - Bilibili