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