FAT32文件系统的那些事儿 第一讲《FAT32文件系统的精妙思想》

振南的FAT32文件系统专题详解 第一讲 《FAT32文件系统的精妙思想》

1、文件管理模型

文件系统的功能和目的，说白了就是要实现一种文件名与文件数据的映射，也就是给定一个文件名后就可以找到它所对应的数据，如图所示。

这看似简单，事实上并不简单，要考虑很多的问题，比如数据的不连续存储、存储空间的有效利用等等。如果要让你自己设计一套文件系统方案来实现存储设备上的数据管理的话，你会把它设计成什么样呢？好，废话少说，下面我们就来介绍几种振南设计的文件管理模型，看看是不是与您的构思相似呢？

1.1 原始模型

我们知道存储器是由很多的顺序分布的扇区所构成的，文件数据就存储在这些扇区上。而分布在若干个扇区上的具有某种关联性的数据，可以成为一个数据集合，我们可以给这个集合取一个名字，这就是一种原始意义上的“文件”了。因此，我们就有了这样一种最为原始的文件管理模型，如图所示。

从上图中我们可以看到，文件名与数据是直接放在一起存储的，而且数据的存储是顺序的。这种模型的优点显而易见：简单明了，绝不浪费一丝空间，数据存储十分紧凑。但是缺点多多，最主要的一点就是文件搜索效率太低。比如要找到name3，我们就要从0扇区开始，依次的读取扇区数据，并在其中检测文件名，如此一直循环下去，直到发现了“name3”为止。也许你会说：“这name3前面也没几个扇区，花不了多少时间就能找到。”其实不然，这只是一个例子，实际上它前面可能有成百上千，成千上万的扇区，这样效率就非常低了。最坏的情况就是搜索nameN，即位于磁盘最末尾的文件，基本上就要遍历整个磁盘的所有扇区了（不知道大家有没有对磁盘作过低格，这里所说的遍历整个磁盘的速度会比低格更慢）。

1.2 改进模型

聪明的你可能灵机一动会想到这样一个方案：如果能把文件名都提到扇区的开始处，那不是可以省去在扇区数据里找文件名的步骤了吗？或许能将搜索文件的效率提高一点。没错，我们来看下图。

    这样确实可以提高一些效率，但实际上仍然是换汤不换药，效率低下的问题并没有从根本上解决。我们还是要着眼于如何摆脱“逐个搜索扇区”的困境。同时，我们看到上面的改进模型中已经开始出现存储空间的“浪费”了。其实这也体现了“时空平衡”的原则：要提高效率，则必然要牺牲空间。俗话说：天要下雨，娘要嫁人，这都是没有办法的事情。我们能作的就是作好适当的取舍，也许这也算是中庸之道。在后面，我们会继续看到为了效率或其它更有价值的目的，而对存储空间的“牺牲”。

    其实，原始模型与改进模型都存在着另一个非常棘手的问题，不知道大家意识到了没有：它们的数据存储都是顺序的，是不能跨扇区的。如果我们要进行删除文件的操作，比如把“name2”删除，就要把数据清空，于是这些存储空间就会空闲出来（即2、3扇区）。我们自然会想到，在写入新的文件时，这部分存储空间能否被重新利用起来。如果新文件的数据量比它小（如下图中的nameS），那么它是可以放在这里的。但如果新文件数据量比较大（如下图中的nameL），这块存储空间就放不下了。我们只能放弃它，再到后面寻找更大的空闲连续扇区。造成这一问题的根本原因在于：这种文件管理模型无法将数据分为若干部分来分散存储。就算我们把它强行分散到各个扇区中，我们也无法知道它们是如何分布的，因为各部分数据之间根本毫无关联。

    要让数据可以不连续存储，又要能够知道各部分数据的具体存储位置，该如何实现呢？“链……链表？”对，别含糊，就是链表（如果你还不知道什么是链表，建议先学习一下数据结构的相关知识）。我们给每一个扇区的头部都设置一个专门的字段来记录扇区所属文件以及下一个扇区的地址。这样我们在读取某一扇区之后，就可以知道记录后续数据的下一扇区在哪里了。它就如一条锁链，环环相扣，直到最后一个扇区。下图是一个更为形象的示意。

同时，这种改进型也很好的解决了数据删除后新文件写入的问题。前面没空间，只管到后面去找，最后别忘了把前后两部分空间链起来就OK了，如下图所示。

2、FAT32文件系统

上面我们列举了几种文件系统的模型，并进行了多次的改进和演化。想必大家脑中已经形成了一个初步的文件管理的概念了。我们已离FAT32很近，很快就可以揭开FAT32文件系统的神秘面纱了。

2.1 逼近模型

    “逼近”？跟谁逼近？自然是与FAT32文件系统逼近。上面最后的文件管理模型，采用了“链式存储”的原理，其实这就是FAT32的核心思想。但这个模型顶多只能算是FAT32的雏形。经过进一步改进而得到的“逼近模型”，与真正的FAT32就更加神似了。

    我们的文件管理模型虽然经过了多次改进，但仍未摆脱“遍历扇区”的厄运，搜索目标文件的效率仍然非常低下。有什么办法可以快速得到文件的位置呢？答：索引！说白了，就如同书的目录一样，记录了章节的标题和具体位置。我们可以拿出一些扇区专门用来记录文件名及其对应数据的开始位置。这样一来，我们就不用遍历所有扇区了，只需要对这块“文件索引区”进行搜索，就可以找到目标文件了。可能这样说还是比较抽象，那请看下图。

    在上图中可以看到，我们用“文件索引扇区”记录了文件名与数据开始扇区的对应关系。但是用于描述扇区间的链式关系的字段，仍然位于各扇区的开始位置，这一点让人有些不爽：读写数据的时候，还要把它跟数据分离开。我们何不将这些字段也提出来，专门以映射表的形式存在一个地方，统一进行管理。如果你能理解我所说的这些，那么You Get It! 这个映射表就犹如FAT32文件系统核心中的核心—FAT（文件分配表）。如图3.8所示，这才算是FAT32文件系统的逼近模型。

    讲到这里，我记得曾经有人问过这样的问题：“记录数据链式关系的映射表固然是一种很好的解决方法，但是要知道磁盘扇区的数量是很大的，把它们之间的链式关系都放到映射表里，这表的体积未免也太大了吧？单单这个表就会占用较大的存储空间，另外数据的读取效率也是问题。”可见此人真的是动脑筋了。他所说的这个问题，可能不是每个人都能领会到的。我们来举一个例子：如果一个磁盘的容量为1GB，则它的扇区数为2097152，如果扇区地址使用32位整型来存储，那么一个扇区最多可以存储128个扇区地址，因此需要2097152/128=16384个扇区，即8M的存储空间，体积还是蛮大的。如果一个文件的数据占用了N个扇区，那么就要到映射表中查找N次，而每查找一次，却仅仅可以读到一个扇区的数据而已（512字节），这种“一查一读”的方式效率十分低下。这一过程被一些人喻称为“频转浅行”，意为一辆车频繁地转换行驶方向，但每次都仅前行几米而已，时间都浪费在转向上了，实际上并没有走出多少路程。如何解决这些问题呢？磁盘的扇区数是由硬件物理结构决定的，不可能减少。而要压缩映射表的体积，必然要减少地址数量。这可如何是好呢？扇区合并！将几个扇区合并为一个存储单元，以它作为最小单位，而不直接使用扇区。这样一来，地址数量减少了，映射表体积自然也就减小了。同时，每一次在映射表中查找之后，都可以读到n个扇区的数据，读取效率也上来了。这个新的存储单元，在后面我们就会知道它叫“簇”，同样是FAT32文件系统中非常重要而基础的概念。

    有人又问了：“要是文件数据量比较小，存不满一个存储单元（其中包含若干个扇区），那可能会浪费更多的存储空间啊？”没错，如果你在磁盘上存储一个只有一个字节的文件，那么浪费确实是太严重了。但对于大文件，那简直就是“效率的天堂”，仅仅查询几次映射表，数据就可以全部读出来了。所以，这正如我们上面所说的，这就是由于空间与效率的矛盾而进行权衡的典型例子。

3、FAT32的轮廓

有了前面的基础，振南就向大家来简要介绍一下实际FAT32文件系统的整体结构与主要功能部分。为大家勾勒出FAT32的大体轮廓，这是我们后面继续深入研究的基础。如下图所示。

MBR：别看错了，不是RMB哦。MBR，主引导记录（Master Boot Record）。严格来说，MBR并不属于FAT32文件系统。它的主要功能是用来记录各个分区的信息（分区信息由MBR中的DPT记录）。另外，MBR也是造成我们在上一章看到的物理0扇区与逻辑0扇区不相等的根本原因，在后面我们会对它进行详细讲解。

DBR：DOS引导记录（DOS Boot Record）。它对于FAT32来说，是极其重要的。DBR中的BPB（BIOS Parameter Block，即BIOS参数块）记录了很多非常关键的参数，如扇区和簇的大小、FAT表的大小、根目录的位置等等。如果DBR被意外破坏，将会直接导致FAT32文件系统的崩溃。当然，如果是有意而且合理地对它进行篡改，我们将可能创造意想不到的效果。比如可以让一支只有几十M的小容量U盘摇身一变成为容量高达几G，甚至上T的海量U盘。在后面振南会向大家揭露制造“假U盘”的具体方法。

FAT：我们可以把它读成 [fæt]，但它可不是肥胖的意思，而是文件分配表（File Allocation Table）。它就犹如上面逼近模型中的映射表一样，记录了所有数据的链式关系。

首目录（根目录）：想想我们在操作磁盘上的文件时，起初是从哪里一层层的进入的。对，根目录！不过在FAT32文件系统中，更准确的叫法是“首目录”，即第一个目录，它是我们进入磁盘的第一道入口。首目录的扇区里存的是什么？还记得上面逼近模型里的文件索引吗？首目录里存的就是文件索引，还有子目录索引。

文件/目录项：振南称之为FDI（File Directory Item，FAT32中实际上并没有这个词）。我们在电脑上所看到的一个个的文件和目录根本上是源自于此。它通常是一个32字节的数据段，用来记录文件和目录的相关信息，如名称、大小、时间、数据开始位置等等。文件/目录项其实就是上面所说的“索引”，我们可以通过它们找到数据的开始位置。

数据区：DA（Data Area）。这部分是FAT32文件系统的数据存储的主体部分。数据区中存储的自然是文件和目录的数据，它本身是由很多的存储单元（簇）所构成的。

上面我们所介绍的是FAT32的主要功能部分。当然，还有很多细微的内容，在后面的讲解过程中会有所涉及。这些功能部分我们虽然是分开来介绍的，但实际上它们是相互关联的。我们来超前性的绕一绕这种关联：从MBR的分区信息中可以获取到DBR的位置（DBR所在的扇区就是分区的第一个扇区）；而用DBR中的BPB中所得到的参数可以计算得到FAT、首目录等部分的具体位置和大小；FAT中又记录了数据区中的数据之间的链式存储关系；而数据区中数据存储单元（簇）的大小又记录在DBR的BPB中；文件/目录项作为文件或目录的索引，给出了数据的开始位置，此开始位置也是FAT中一个链式关系的开始节点，并可由此找到位于数据区中的后续数据……是不是开始觉得有点晕了？别急，其实我也有点晕。FAT32文件系统各功能部分环环紧扣，浑然一体，同时又是错综复杂的。但不要生畏，没你想得那么难，其实它的脉落是十分清晰的。

好，这里振南真正为大家引出了FAT32文件系统，后面我们就开始深入到各个部分进行详细的研究和具体的实现。伴随着我们在FAT32之路上越走越远，大家也会看到更多更加精彩的实验，取得更多的成果。好，继续前进……