Title: 概述了MINIX，EXT2，FAT文件系统，看完应该有一个全局的了解
Author: Quan
Date: 18.04.
====================
MINIX:
====================
Minix的文件系统主要包括一下6个部分：
引导块，超级块，i节点位图，区段位图，真正的i节点信息，数据。
引导块：
一般来将，每一个文件分区里面，都必须包含一个引导块。虽然并不是每一个设备的分区都是用来引导的，但是，出于结构的统一以及兼容性方面的考虑，一般文件系统需要将分区的第一个块保留为引导块。因此，我以前曾经犯过的一个错误就是，认为启动盘在windows里面是不能够被识别的，会提示磁盘未格式化。看来我真的是错了，只能将那个启动盘上的系统，windows不能够识别。但是，启动盘里面确实也装载着完整的文件系统。
超级块：
之所以称之为超级块，就是因为这个块是整个文件系统的龙头！从它，可以推算出整个文件系统的信息。在minix中，它包含了i节点数，区段数，块/区段比，最大文件长度，magic number等等信息。这样，整个文件系统中，上面所涉及到的6个部分的分布就清楚了。
位图：
常用的一个数据结构。使用一个bit来代表一个有序逻辑单位，如这里的一个i节点，一个区段，或者是内存中的一页等等。这里，使用位图来表示哪些i节点是可以的或者是不可用的，对于区段的使用方式也是相同的。这样，就是对有序的逻辑单位进行了标记，而且这样的标记是写入磁盘的因此可以长期的保存。所以，必须要确保文件系统的一致性(consistency)，因为标记和真正的逻辑单位并不是同时写入磁盘的。这一点，相当的重要。
i节点：
这个结构和UNIX下的文件系统应该说是一样的。这里保存着对应于每个文件的具体的信息，如文件类型，访问权限，链接信息，文件大小，时间信息，区段号（包括一次间接块和二次间接块）等等与文件密切相关的信息。这样，在系统访问文件的时候，只要找到对应的i节点就可以确定整个文件的所有方面了。宏观一点看，文件系统的实现还是一个层次性的结构，通过超级块找到i节点，通过i节点再找到真正的文件的所有信息，是一个二级指针的结构。这个和intel CPU里面的内存分页访问有几分的类似了，其实总的来说还都是数据结构的提醒。因此，学习别人的系统实现，很大程度上是了解里面的数据结构。
目录：
MINIX下的目录相当的简单：i节点号+文件/目录名称。当然，这里可以统一的称为文件，不需要考虑文件和目录的差别。首先，在使用mkfs初始化文件系统的时候，该设备分区上的根目录就以及存在了，而且是在一个确定的位置。也就是i节点位图里面对应的bit为1，从而对应的i节点的信息就变得有效。在那个i节点所对应的数据区段里面存储着根目录中的文件的信息（这里就不考虑目录和文件的区别了），格式就是i节点号+文件名（当然，通过文件属性就可以知道这是一个普通的文件还是目录文件了）。于是，文件名和真正的文件就通过i节点这个中介完成了最终的连接。这其中可以说跳转了很多次，相当的曲折！
但是，总的来说，从宏观的逻辑上讲，这样的文件系统是“可实现的”，而且功能已经达到了。
参考：
1. Andrew. S. Tanenbaum. Operating System Design & Implementation.
EXT2
====================
EXT2文件系统在物理结构分布上兼备MINIX和BSD文件系统的特质。使用了BOOTSECTOR, SUPERBLOCK，和BLOCK GROUP的结构。使用BLOCK GROUP的理由很直接，这样，在计算出inode之后，磁头并不需要多长时间就可以到达真正的DATA BLOCK。
同时，EXT2的目录采用了可变长度的链表结构，从而可以支持长达255个字符的文件名。这是一个比较大的进步。实现原理就是多使用一个域来标记整个entry的长度，这样，程序就可以找到下一个entry的入口了。在数据结构上，比MINIX的目录多了2个域：entry长度和文件名长度。
一个具体的例子，这是一个软盘上的物理分布图：
offset number of blocks description
0 1boot record
1 1superblock
2 1group descriptors ( in MINIX, no such block )
3 1block bitmap
4 1inode bitmap ( in MINIX, first inode and then block bitmap )
5 23inode table
28 1412 data blocks
因此，与MINIX文件系统相比，这里仅仅多了一个group descriptor，然后block和inode的bitmap位置更换了。其它基本一致。
在大一些的分区里面，会有多个block groups，而且，上面的super block和group descriptor这两个重要的信息还会在一个或者多个block groups里面进行备份。而各个block group里面的结构是一样的，包含的都是块位图，i节点位图，i节点表，数据块。如果理解了MINIX文件系统里面的位图和i节点表的作用，这里的概念就不难理解了。至于为什么要在每个块group里面放置该组的空闲块和空闲i节点的信息，这在前面已经讲过了，从硬盘的物理结构来讲，寻道是最耗时间的，一般在10ms左右，因此，这样可以减少从i节点到真正的block的寻道时间。
和MINIX一样，ROOT目录始终是i节点表的第二个条目。这样，就可以找到所有的文件了。
参考：
1. 包怀中. EXT2文件系统分析.
2. RemyCard, Theodore Ts"o, Stephen Tweedie. Design and Implementationof the Second Extended Filesystem.
3. Dave Poirier. The Second Extended File System.
4. Louis-Dominique Dubeau. Analysis of the Ext2fs structure.
FAT:
====================
FAT分区格式是Microsoft最早支持的分区格式，依据FAT中每个簇链的所占比特位数分为FAT12、FAT16、FAT32三种格式"变种"，但其基本存储方式是相似的。
假设FAT分区是硬盘的第一个分区，那么该FAT分区一般从chs={0,1,1}开始，而并不是从chs={0,0,2}开始的，一般会保留62个扇区。这个算是一个历史原因吧。分区的物理结构分布如下：
DBR->FAT1->FAT2->rootdir->data
其中，DBR即DOS Boot Record，它由MBR装入内存，然后BIOS交出控制权给DBR，从而过渡到操作系统的引导。DBR的第一个可执行语句通常都是一个jmp，接下来放置一些OEM信息，如MSDOS 5.0等等。接下来是BPB即BIOS Parameter Block，记录了磁盘的一些具体信息，如扇区字节数，每簇扇区数（类似与MINIX中的block），保留扇区数（第一个FAT之前的未使用的扇区数，包括DBR），FAT数目（一般有两个FAT），媒体描述符（0xF8表示硬盘，0xF0表示3.5软盘），该FAT分区总的扇区数，每个FAT所占用的扇区数（PC使用这个值，FAT个数，以及隐藏扇区数来计算得到根目录所在的扇区），文件系统版本。最后就是著名的0xaa55了。接下来在DBR喝FAT1之间一般还会有一段保留区域，当然，FAT12和FAT16没有。接下来就是真正的FAT1和FAT1的一个备份FAT2了。接下来就是真正的数据区了，FAT32里面也没有rootdir，因为rootdir也是可以任意的放在数据区中的，不一定是数据区的开始。但是，root的簇一般来讲，是整个文件系统的起始簇，也就是第二个簇。
实际上，以FAT32构建的操作系统如果是win98,系统会使用基本分区的第0扇区和第2扇区存储os引导代码；以FAT32构建的操作系统如果是win2000或winxp,系统会使用基本分区的第0扇区和第0xC扇区，而不仅仅使用分区的第0个扇区，但是不管怎么样，第0个扇区总是被MBR加载到内存中的，因此，后面的扇区即使使用到了也是由第0个扇区加载到内存中的。正是基于这一点，GRUB这样的引导工具才能够使用chain的方式将Windows，或者其它非Linux的系统进行引导。GRUB在这个时候，仅仅扮演的是MBR的角色。这一点非常重要！
在FAT16文件系统中，保留扇区的数据通常设置为1，即仅仅DBR扇区。而在FAT32中，保留扇区的数据通常 取为32，有时候用Partition Magic分过的FAT32分区会设置36个保留扇区，有的工具可能会设置63个保留扇区。操作系统之所以在FAT32中设置保留扇区，是为了对DBR作备份或留待以后升级时用。FAT32中，DBR偏移0x34占2字节的数据指明了DBR备份扇区所在，一般为0x06，即第6扇区。当FAT32分区DBR扇区被破坏导致分区无法访问时。可以用第6扇区的原备份替换第0扇区来找回数据。
下面来看一下真正的FAT表：
FAT表以"F8 FF FF FF" 开头，此4字节为介质描述单元，并不参与FAT表簇链关系。FAT表记录了磁盘数据文件的存储链表，对于数据的读取而言是极其重要的，以至于Microsoft为其开发的FAT文件系统中的FAT表创建了一份备份，就是我们看到的FAT2。FAT2与FAT1的内容通常是即时同步的，也就是说如果通过正常的系统读写对FAT1做了更改，那么FAT2也同样被更新。
FAT文件系统的目录结构其实是一颗有向的从根到叶的树，这里提到的有向是指对于FAT分区内的任一文件(包括文件夹)，均需从根目录寻址来找到。可以这样认为：目录存储结构的入口就是根目录。
FAT16中目录项的结构（括号中的是所占的字节数）：
文件名(8)->扩展名(3)->文件属性(1)->保留(10)->修改时间(2)->修改日期(2)->首簇号(2)->文件长度(4)
这个格式很简单，通过这里面的首簇号就可以从FAT表里面访问到实际的文件内容了。在MINIX的文件系统里面inode表代替了这里的FAT的功能，本质两者还是一样的。但是这里使用的是链表的结构，而MINIX里面使用的索引的结构。FAT的一个很明显的问题就是随着分区变大，FAT将变得十分的臃肿。因为有多少个簇，就需要有双倍或者是四倍的字节数来供FAT消耗。如假设FAT32用满了4G个簇，也就是至少可以寻址2TB的分区，那么FAT将占据16G的空间。而一般考虑到查找效率，FAT都是要被加载到内存的，因此不可想象。一般来讲，FAT不宜超过4MB大小，也就是FAT32里面簇的个数不宜超过1M个，相应的磁盘空间如果按照每簇32K的话，也就是32G的磁盘分区。
FAT32对簇的编号依然同FAT16。顺序上首簇仍然编号为第2簇，通常为根目录所用(这和FAT16是不同的，FAT16的根目录并不占簇区空间，32个扇区的根目录以后才是簇区第1个簇) ，这是FAT16和FAT32一个比较大的不同点。
FAT32下，与EXT2文件系统相比，长文件名的实现比较特别。长文件名依然是记录在目录项中的。为了低版本的OS或程序能正确读取长文件名文件，系统自动为所有长文件名文件创建了一个对应的短文件名，使对应数据既可以用长文件名寻址，也可以用短文件名寻址。长文件名还是按照32个字节的条目来存放的，每个条目里面存放13个字符（注意，使用的是unicode编码，因此占用26个字节，还有一些辅助信息），因此，一个长文件名需要使用多个条目。而且，物理结构上的存放是倒着的：
首先是长文件名的最后一个13字符部分，然后一次完全，直到第一个32字节条目。然后下面存放的才是短文件名，在短文件名里面存放着真正的文件的信息，如创建时间，文件大小等等。因此，短文件名条目的作用是至关重要的。当然，这里面还有一些对应算法，这里就不详谈了。 长文件名的实现有赖于目录项偏移为0xB的属性字节，当此字节的属性为：只读、隐藏、系统、卷标，即其 值为0FH时，DOS和WIN32会认为其不合法而忽略其存在。这正是长文件名存在的依据。
参考：
1. Microsoft Corp. Microsoft Extensible Firmware Initiative FAT32 File System Specification.
2. Shrishail Rana. Fat32 & File System Guide
