髌骨带正确佩戴图:FAT文件系统原理-规范(2)

FAT数据结构（Data Structure）
接下来一个重要的数据结构就是FAT表（File Alloacation Table），它是一一对应于数据簇号的列表
文件系统分配磁盘空间按簇来分配。因此，文件占有磁盘空间时，基本单位不是字节而是簇，即使某个文件只有一个字节，操作系统也会给它分配一个最小单元：即一个簇。为了可以将磁盘空间有序地分配给相应的文件，而读取文件的时候又可以从相应的地址读出文件，我们可以把数据区空间分成BPB_BytsPerSec*BPB_SecPerClus字节长的簇来管理，FAT表项的大小与FAT表的类型有关，FAT12的表项为12bit ，FAT16为16bit， 而FAT32则为32bit。对于大文件，需要分配多个簇。同一个文件的数据并不一定完整地存放在磁盘中一个连续地区域内，而往往会分若干段，像链子一样存放。这种存储方式称为文件的链式存储。为了实现文件的链式存储，文件系统必须准确地记录哪些簇已经被文件占用，还必须为每个已经占用的簇指明存储后继内空的下一个簇的簇号，对于文件的最后一簇，则要指明本簇无后继簇。这些都是由FAT表来保存的，FAT表的对应表项中记录着它所代表的簇的有关信息：诸如是空，是不是坏簇，是否是已经是某个文件的尾簇等。
以FAT16为例说明FAT的结构如下：
表项
示例代码
描述
0
FFF8
磁盘标识字，必须为FFF8
1
FFFF
第一簇已经被占用
2
0003
0000h            ：可用簇
3
0004
0002h  -   FFFEF ：已用簇，表项中存放文件下个簇的簇号
……
……
N
FFFF
FFFF0h  -   FFFF6 ： 保留簇
N+1
0000
FFFF7h           ：坏簇
……
……
FFFF8h  -    FFFFFh ：文件的最后一簇
FAT的项数与硬盘上的总簇数相关（因为每一个项要代表一个簇，簇越多当然需要的FAT表项越多），每一项占有的字节数也与总簇数有关（因为基中需要存放簇号，簇号越大当然每项占用的字节数就越大）
这里说一下FAT目录，其实它和普通的文件汉有什么不一样的地方，只是多了一个表示它是目录的属性，另外就是目录所链接的内容是一个32字节的目录项。除此之外，目录和文件没什么区别。FAT表是根据簇数和文件对应的。第一个存入数的簇是簇2
簇2的第一个扇区（硬盘的数据区）根据BPB来计算，首先我们计算目录所在记扇区数：
RootDirSectors = ((BPB_RootEntCnt*32)  + (BPB_BytsPerSec – 1))/BPB_BytsPerSec;
因为FAT32的BPB_RootEntCnt为0，所以对于FAT32卷RootDirSectors的值也一定是0。上式中的32是每个目录项所占的字节数，计算结果四舍五入
数据区的起始地址，簇2的第一个扇区由下面的公式计算：
If ( BPB_FATz16 != 0 )
FATSz = BPB_FATSz16;
Else
FATz = BPB_FATSz32;
FirstDataSector = BPB_EsvdSecCnt + (BPB_NumFATs * FATSz) + RootDirSectors;
NOTE：扇区号指的是针对卷中包BPB的第一个扇区的偏移量（包含BPB的第一个扇区是扇区0），并不是必须直接和磁舯的扇区相对应。因为卷中的扇区0并不一定就是磁盘的扇区0。
给一个合法的簇号N，该簇的第一个扇区号（针对FAT卷扇区0的偏移量）由下式计算：
FirstSectorofCluster =((N -2) * BPB_SecPerClust) + FirstDataSecot;
NOTE ： 因为BPB_SecPerClus总是2的整数次方，这意味着BPB_SecPerSlus的乘法运算可以通过移动来进行。在当前的Intel x86架构的2进制机器上的乘法和除法的机指令非常的繁杂和庞大，而使用移位来运算会相对快许多。
FAT类型辨别
这是一个经常产生错误的地方，并且常常会出现者如”off by1 ”,”off by 2 ”,”off by10”和”massively off”的错误，事实上，FAT的类型检测非常简单，FAT的类型———FAT12或是FAT16或是FAT32只能能地FAT卷中的簇数来判定，没有其他的办法
首先我们讨论“簇数”是如何计算的，它完全根BPB的内容来确定，我们先计算根目录所占的扇区数
RootDirSectors =((BPB_RootEntCnt * 32)  + (BPB_BytsPerSec -1)) / BPB_BytsPerSec;
FAT32的RootDirSectors为0
接下来我们检测数据区中的扇区数
If ( BPB_FATz16 != 0 )
FATSz = BPB_FATSz16;
Else
FATz = BPB_FATSz32;
If(BPB_TorSec16 != 0)
TotSec =BPB_TotSect16;
Else
TotSec = BPB_TotSec32;
DataSect=TotSec – (BPB_RsvdSecCnt +(BPB_NumFATs * FATSz) +RootDirSectors);
计算簇数：
CountofClusters = DataSec / BPB_SecPerClus;
计记住计算结果四舍五入就可以了
现在我们就可判定FAT的类型了：
If(CountofClusters < 4085) {
/*卷类型是 FAT12 */
} else if(CountofClusters < 65525) {
/* 卷类型是FAT16 */
} else {
/* 卷类型是 FAT32 */
}
这是检测FAT类型的唯一方法。世上不存在簇数大于4084的FAT12卷，也不存在簇数小于4085或是大于65524的FAT16卷，同样也没有哪个FAT32卷簇数小于65525。如果你坚持要违背这个规则来创建一个FAT卷那么微软的操作系统无法对此卷进行操作，因为它不认为这是FAT文件系统。
NOTE：如前面所说，目前有很多FAT代码有一些错误，常常会出现off by 1,2,8,10或是off by 16的错误。因此，为和现在存的所有代码取得最好的兼容性，强烈建议格式化FAT文件系统时，尽量使簇数的取值不要接近4085或是65525，最好能和这个分害点的值相差16或更多。
同时请注意这里的簇数（count of Cluster）是指数据区所占簇的数量（the count of the data cluster），从簇2算起，而“最大可用簇数”（Maximun valid cluster number for the volume）是簇数+1，“包括保留簇的簇数”（count of cluster including the two reserved cluster）则为簇数+2。
FAT的另外一个重要计算公式：给一个簇号N，它位于FAT表的什么位置呢？对于FAT16和FAT32较容易计算，而FAT12则会复杂一点：
If(BPB_FATSz16 != 0)
FATSz = BPB_FATSz16;
Else
FATSz = BPB_FATSz32;
If(FATType == FAT16)
FATOffset = N * 2;
Else if (FATType == FAT32)
FATOffset = N * 4;
ThisFATSecNum = BPB_ResvdSecCnt + (FATOffset / BPB_BytsPerSec);
ThisFATEntOffset = REM(FATOffset / BPB_BytsPerSec);
REM（…）为求余运算符，就是求FATOffset除以BPB_BytsPerSec的余数。ThisFATSecNum是FAT表中包含簇N的扇区数，如果你想得到第二个FAT表中的扇区数，只要加上FATSz就是，如果想得到第三个FAT表中的扇区数，只需加上FATSz*2，依次类推
现在你得到扇区数，ThisFATSecNum（记住这是针对FAT卷扇区0的偏移量），假设把该值读入到一个指定的8-bit SecBuff，同时假定数据类型WORD是一个16-bit的无符号数，而DWORD是一个32-bit的无符号数，
If(FATType == FAT16)
FAT16ClusEntryVal = *((WORD *) &SecBuff[ThisFATEntOffset]);
Else
FAT32ClusEntryVal = (*((DWORD *) &SecBuff[ThisFATEntOffset])) & 0x0FFFFFFF;
取得该扇区的内容
设置该扇区的值使用如下算式
If(FATType  =  FAT16)
*((WORD *) &SecBuff[ThisFATEntOffset]) = FAT16ClusEntryVal;
Else {
FAT32ClusEntryVal = FAT32ClusEntryVal & 0x0FFFFFFF;
*((DWORD *) &SecBuff[ThisFATEntOffset]) =
(*((DWORD *) &SecBuff[ThisFATEntOffset])) & 0xF0000000;
*((DWORD *) &SecBuff[ThisFATEntOffset]) =
(*((DWORD *) &SecBuff[ThisFATEntOffset])) | FAT32ClusEntryVal;
}
我们看看上述FAT代码是如何工作的，实际上每个FAT32的FAT表项只有28bit可以使用，它的高4位保留，这4位只有在被格式化时会被使用到，在格式化时整个FAT32单元的32bit全部设为0，包括高位的4bit 。
另外要说明的一点，这也是常常被混淆的地方，因为FAT32表项实际上被使用的只有28bit而不是32bit，比如，以下几个FAT32的簇的值为0x1000 0000, 0xF000 0000和0x00000000都表示该簇为空，因为程序忽略了高位4bit 的值。如果当前的簇的值为0x30000000，你想要把数值0x0FFFFFF7写入当前簇来标记坏簇，那么当你的操作结束后该簇的值实际上0x3FFF FFF7，因为你必须舍去0x0FFFFFF7这个坏簇的标记高位的4bit。
因为BPB_BytsPerSec的值一定能够被2和4整除，对于FAT16/FAT32来说，你不必担心元素会超越扇区的边界，但对于FAT12，你就必须小心了。
FAT12的代码会显得复杂点，因为它的每个元素占1.5个字节（12bit）
if (FATType == FAT12)
FATOffset = N + (N / 2);
/* 注意算式没有乘以浮点数1.5。而是除以2的四舍五入*/
ThisFATSecNum = BPB_ResvdSecCnt + (FATOffset / BPB_BytsPerSec);
ThisFATEntOffset = REM(FATOffset / BPB_BytsPerSec);
现在我们必须考虑扇区边界的情况
If(ThisFATEntOffset == (BPB_BytsPerSec – 1)) {
/*这个簇跨越了FAT的扇区边界区域，处理这个问题有很多方法*
/*其中最简单的一种就是当FAT类型为FAT12则同时读取两个*/
/*扇区的内容到内存中，（如果你想读取扇区N，同时你把扇区*/
/*N+1的内容也读入内存中来，除非扇区N是FAT的最后一个扇*/
/*区）这样做实际上是避免扇区的边界检测*/
}
现在我们可以像FAT16一样使用WORD数据类型来对FAT12的数据进行读取，但仍需要注意，如果簇号为偶数，我们取16bit中的低12bit，如果是奇数则取高12bit
FAT12ClusEntryVal = *((WORD *) &SecBuff[ThisFATEntOffset]);
If(N & 0x0001)
FAT12ClusEntryVal = FAT12ClusEntryVal >> 4; /* 簇号为奇数 */
Else
FAT12ClusEntryVal = FAT12ClusEntryVal & 0x0FFF; /* 簇号为偶数*/
取出当前簇的内容。要设置这个簇的内容可以采用如下方式
If(N & 0x0001) {
FAT12ClusEntryVal = FAT12ClusEntryVal << 4; /* 簇号为奇数 */
*((WORD *) &SecBuff[ThisFATEntOffset]) =
(*((WORD *) &SecBuff[ThisFATEntOffset])) & 0x000F;
}
Else {
FAT12ClusEntryVal = FAT12ClusEntryVal & 0x0FFF; /* 簇号为偶数*/
*((WORD *) &SecBuff[ThisFATEntOffset]) =
(*((WORD *) &SecBuff[ThisFATEntOffset])) & 0xF000;
}
*((WORD *) &SecBuff[ThisFATEntOffset]) =
(*((WORD *) &SecBuff[ThisFATEntOffset])) | FAT12ClusEntryVal;
数据区的文件是按下方式与FAT表相对应的：数据区中文件存放的第一个簇的簇号被记录在目录项中，文件就是根据这个簇号和FAT表相关联，数据区中文件的位置由前面讨论的FirstSectorofCluster来计算。
对于一个文件大小为0，即一个没有数据的文件，在目录项中分配的第一个簇号为0，此簇（参见前面讨论的ThisFATSecNum和ThisFATCntOffset）的内容要么是一个EOC标记（End of Cluster簇链结束标记）要么就是该文件下一簇的簇号。EOC的值和FAT类型有关（假设FATContent是需要检测看是否包含EOC标记的簇的内容）
IsEOF = FALSE;
If(FATType == FAT12) {
If(FATContent >= 0x0FF8)
IsEOF = TRUE;
}
else if(FATType == FAT16) {
If(FATContent >= 0xFFF8)
IsEOF = TRUE;
}
else if (FATType == FAT32) {
If(FATContent >= 0x0FFFFFF8)
IsEOF = TRUE;
}
注意：包含EOC标记的簇属于当前文件并且是当前文件的最后一个簇。微软的操作系统设置EOC标记时FAT12使用0x0FFF，FAT16使用0xFFFF，FAT32使用0xFFFFFFFF，但有一些运行在微软系统的工具并不使用这个值
还有一个特殊的标记就是“坏簇”标记，任合包含“坏簇”标记的簇都不应该被列到剩余簇的荡畴内，这个：坏簇“标记对FAT12是0x0FF7，对于FAT16是0xFFF7，对FAT32是0x0FFFFFF7。另外这些坏簇看起来也像是丢失的簇——它们似乎已经分配出去，因为他们的值不为0，它同时他们又不属于任何文件。磁盘修复程序一[一要认出这些被标记坏簇标记的“丢失簇”，并且不去修改他们的内容。
NOTE：对于FAT12和FAT16而言。坏簇标记不可能是某个已经分配簇的簇号，但对于FAT32而言，0x0FFFFFF7就有可能是某个簇的簇号，因此FAT32文件系统必须避免把0x0FFFFFF7这个数字分配出去作为某个簇的簇号。
FAT表中剩余簇的列表就是卷中所有内容为0的簇的列表，这些数据必须尽早取得并记录下来以表示剩余的簇是已经被使用的，这个列并没有存在卷中任何一个地方，他必须在系统挂上（mount）该卷时由FAT表扫描程序获得内容为0的簇的列表。FAT32的BPB_FSInfo扇区可能会包含剩余簇的数量，请阅FAT32关于BPB_FSInfo扇区的主席论部分。
在FAT卷起始部分的两个保留扇区到底是做什么的呢？第一个保留簇GAT[0]，它的低位8bit为BPB_Media，剩余的位用1填充。比如BPB_Media的内容为0xF8，那么FAT12的内容为0xFF8，FAT16为0xFFF8，FAT32的内容为0x0FFFFFF8。第二个保留簇FAT[1]在格式化时被填充EOC标记。FAT12卷域不用，其值始终为EOC标记。FAT16和FAT32此域的高2bit可以被用来用于标记磁盘是否为“dirty”，剩余的位均用1填充。请注意FAT16和FAT32这个两位的位置是为一样的，因为是高2bit
对于FAT16
ClnShutBitMask = 0x8000;
HrdErrBitMask = 0x4000;
对于FAT32
ClnShutBitMask = 0x08000000;
HrdErrBitMask = 0x04000000;
Bit ClnShutBitMask –如果此位为1，那么卷是“clean”。如果为0，那卷是“dirty”的。意味着系统在上次卸载此郑时没有正常地断开连接，此时建议使用ChkDisk/Scandisk等工具来检测磁盘是否有错误
Bit HrdErrBitMask –如果此位为1，表时没有发生磁盘读/写错误。如果为0，表示系统在上次挂载该卷时有发生过磁盘读/写错误，此时建议使用ChkDisk/Scandisk等工具来检测磁盘表面是否有出现新的坏簇。
关于FAT表这里还有两个重要的问题：
1．               FAT表的结束扇区不一定就是FA表的最的一个扇区，FAT表的结尾扇区位于簇号为CountofCluster+1（请参阅前面关于CountofCluster的计算式）的簇中。这个扇区示必须在FAT表的后面。FAT表程序不应该尝试着去访问CountofCluster+1以后的簇。FAT格式化程序应该把这个簇号后面的所有簇用0填充
2．               BPB_FATS z（对于FAT23为BPB_FATSz32）的值会比它实际需要的大，也就是，在FAT表中可能有部分扇区没有被使用。因此FAT表的结束扇区都是由CountofCluster+1来计算得到，而不是使用BPB_FATSz16/32来计算。FAT程序不应该尝试访部这些“额外”的扇区。FAT格式化程序应该把这些扇区用0来填充。