你手里有一块硬盘,大小为1T 你还有一堆文件 这些文件在硬盘看来,就是一堆二进制数据而已 你准备把这些文件存储在硬盘上,并在需要的时候读取出来。 要设计怎样的软件,才能更方便地在硬盘中读写这些文件呢?1 首先我不想和复杂的扇区,设备驱动等细节打交道,因此我先实现了一个简单的功能,将硬盘按逻辑分成一个个的块,并可以以块为单位进行读写。 每个块就定义为两个物理扇区的大小,即1024字节,就是1KB啦。 硬盘太大不好分析,我们就假设你的硬盘只有1MB,那么这块硬盘则有1024个块。 OK,我们开始存文件啦! 准备一个文件 随便选个块放进去,3号块吧! 成功!首战告捷!2 再存一个文件! 诶?发现问题了,万一这个文件也存到了3号块,不是把原来的文件覆盖了么?不行,得有一个地方记录,现在可使用的块有哪些,像这样。 块0:未使用 块1:未使用 块2:未使用 块3:已使用 块4:未使用 。。。 块1023:未使用 那我们就用0号块,来记录所有块的使用情况吧!怎么记录呢? 位图! 那我们给块0起个名字,叫块位图,之后这个块0就专门用来记录所有块的使用情况,不再用来存具体文件了。 当我们再存入一个新文件时,只需要在块位图中找到第一个为0的位,就可以找到第一个还未被使用的块,将文件存入。同时,别忘了把块位图中的相应位置1。 完美!3 下面,我们尝试读取刚刚的文件。 咦?又遇到问题了,我怎么找到刚刚的文件呢?根据块号么?这也太蠢了,就像你去书店找书,店员让你提供书的编号,而不是书名,显然不合理。 因此我们给每个文件起一个名字,叫文件名,通过它来寻找这个文件。 那必然就要有一个地方,记录文件名与块号的对应关系,像这样。 葵花宝典。txt:3号块 数学期末复习资料。mp4:5号块 低并发编程的秘密。pdf:10号块 。。。 别急,既然都要选一个地方记录文件名称了,不妨多记录一点我们关心的信息吧,比如文件大小、文件创建时间、文件权限等。 这些东西自然也要保存在硬盘上,我们选择用一个固定大小的空间,来表示这些信息,多大空间呢?128字节吧。 为啥是128字节呢?我乐意。 我们将这128字节的结构体,叫做一个inode。 之后,我们每存入一个新的文件,不但要占用一个块来存放这个文件本身,还要占用一个inode来存放文件的这些元信息,并且这个inode的所在块号这个字段,就指向这个文件所在的块号。 如果一个inode为128字节,那么一个块就可以容纳8个inode,我们可以将这些inode编上号。 如果你觉得inode数不够,也可以用两个或者多个块来存放inode信息,但这样用于存放数据的块就少了,这就看你自己的平衡了。 同样,和块位图管理块的使用情况一样,我们也需要一个inode位图,来管理inode的使用情况。我们就把inode位图,放在1号块吧! 同时,我们把inode信息,放在2号块,一共存8条inode,这样我们的2号块就叫做inode表。 现在,我们的文件系统结构,变成了下面这个样子。 注意:块位图是管理可用的块,每一位代表一个块的使用与否。inode位图管理的是一条一条的inode,并不是inode所占用的块,比如上图中有8条inode,则inode位图中就有8位是管理他们的使用与否。4 现在,我们的文件很小,一个块就能容下。 但如果需要两个块、三个块、四个块呢? 很简单,我们只需要采用连续存储法,而inode则只记录文件的第一个块,以及后面还需要多少块,即可。 这种办法的缺点就是:容易留下大大小小的空洞,新的文件到来以后,难以找到合适的空白块,空间会被浪费。 看来这种方式不行,那怎么办呢? 既然在inode中记录了文件所在的块号,为什么不扩展一下,多记录几块呢? 原来在inode中只记录了一个块号,现在扩展一下,记录8个块号!而且这些块不需要连续。 嗯,这是个可行的办法! 但是这也仅仅能表示8个块,能记录的最大文件是8K(记住,一个块是1K),现在的文件轻松就超过这个限制了,这怎么办? 很简单,我们可以让其中一个块,作为间接索引。 这样瞬间就有263个块(多了2561个块)可用了,这种索引叫一级间接索引。 如果还嫌不够,就再弄一个块做一级间接索引,或者做二级间接索引(二级间接索引则可以多出2562561个块)。 我们的文件系统,暂且先只弄一个一级间接索引。硬盘一共才1024个块,一个文件263个块够大了。再大了不允许,就这么任性,爱用不用。 好了,现在我们已经可以保存很大的文件了,并且可以通过文件名和文件大小,将它们准确读取出来啦!5 但我们得精益求精,我们再想想看这个文件系统有什么毛病。 比如,inode数量不够时,我们是怎么得知的呢?是不是需要在inode位图中找,找不到了才知道不够用了? 同样,对于块数量不够时,也是如此。 要是有个全局的地方,来记录这一切,就好了,也方便随时调整,比如这样 inode数量 空闲inode数量 块数量 空闲块数量 那我们就再占用一个块来存储这些数据吧!由于他们看起来像是站在上帝视角来描述这个文件系统的,所以我们把它放在最开始的块上,并把它叫做超级块,现在的布局如下。 我们继续精益求精。 现在,块位图、inode位图、inode表,都是是固定地占据这块1、块2、块3这三个位置。 假如之后inode的数量很多,使得inode表或者inode位图需要占据多个块,怎么办? 或者,块的数量增多(硬盘本身大了,或者每个块变小了),块位图需要占据多个块,怎么办? 程序是死的,你不告诉它哪个块表示什么,它可不会自己猜。 很简单,与超级块记录信息一样,这些信息也选择一个块来记录,就不怕了。那我们就选择紧跟在超级块后面的1号块来记录这些信息吧,并把它称之为块描述符。 当然,这些所在块号只是记录起始块号,块位图、inode位图、inode表分别都可以占用多个块。 好了,大功告成!6 现在,我们再尝试存入一批文件。葵花宝典。txt数学期末复习资料。mp4赘婿1。mp4赘婿2。mp4赘婿3。mp4赘婿4。mp4低并发编程的秘密。pdf 诶?这看着好不爽,所有的文件都是平铺开的,能不能拥有层级关系呢?比如这样葵花宝典。txt数学期末复习资料。mp4赘婿赘婿1。mp4赘婿2。mp4赘婿3。mp4赘婿4。mp4低并发编程的秘密。pdf 我们将葵花宝典。txt这种称为普通文件,将赘婿这种称为目录文件,如果要访问赘婿1。mp4,那全文件名要写成 赘婿赘婿1。mp4。 如何做到这一点呢?那我们又得把inode结构拿出来说事了。 此时需要一个属性来区分这个文件是普通文件,还是目录文件。 缺什么就补什么嘛,我们已经很熟悉了,专门加一个4字节,来表示文件类型。 如果是普通文件,则这个inode所指向的数据块仍然和之前一样,就是文件本身原封不动的内容。 但如果是目录文件,则这个inode所指向的数据块,就需要重新规划了。 这个数据块里应该是什么样子呢?可以是一个一个指向不同inode的紧挨着的结构体,比如这样。 这样先通过赘婿这个目录文件,找到所在的数据块。再根据这个数据块里的一个个带有inode信息的结构体,找到这个目录下的所有文件。 完美!7 不过这样的话,你想想看,如果想要查看一下赘婿这个目录下的所有文件(比如ll命令),将文件名和文件类型都展示出来,怎么办呢? 就需要把一个个结构体指向的inode从inode表中取出,再把文件名和文件类型取出,这很是浪费时间。 而让用户看到一个目录下的所有文件,又是一个极其常见的操作。 所以,不如把文件名和文件类型这种常见的信息,放在数据块中的结构体里吧。 同时,inode结构中的文件名,好像就没啥用了,这种变长的东西放在这种定长的结构中本身就很讨厌,早就想给它去掉了。而且还能给其他信息省下空间,比如文件所在块的数组,就能再多几个了。 太好了,去掉它! OK,大功告成,现在我们就可以给文件分门别类放进不同目录下了,还可以在目录下创建目录,无限套娃!8 现在的文件系统,已经比较完善了,只是还有一点不太爽。 我们访问到一个目录下,可以很舒服地看到目录里的文件,然后再根据名称访问这个目录下的文件或者目录,整个过程都是一个套路。 但是,最上层的目录下的所有文件,即根目录,现在仍然需要通过遍历所有的inode来获得,能不能和上面的套路统一呢? 答案非常简单,我们规定,inode表中的0号inode,就表示根目录,一切的访问,就从这个根目录开始! 好了,这回没有然后了! 我们最后来欣赏下我们的文件系统架构。 你是不是觉得这没啥了不起的。但这个破玩意,它就叫文件系统后记 这个文件系统,和linux上的经典文件系统ext2基本相同。 下面是我画的ext2文件系统的结构(字段部分只画了核心字段) 估计你是看不清了,我说下主要异同点: 1。超级块前面是启动块,这个是PC联盟给硬盘规定的1KB专属空间,任何文件系统都不能用它。 2。ext2文件系统首先将整个硬盘分为很多块组,但如果只有一个块组的话,和我们的文件系统整体结构就完全一样了,分别是超级块、块描述符、块位图、inode位图、inode表、数据块。 3。ext2文件系统的inode表中用15个块来定位文件,其中第13个块为一级间接索引、14个为二级间接索引、15个为三级间接索引。 4。ext2文件系统的文件类型分得更多,还有常见的如块设备文件、字符设备文件、管道文件、socket文件等。 5。ext2文件系统的超级块、块描述符、inode表中记录的信息更多,但核心的和我们的文件系统一样,而且这些字段在后续的ext3和ext4中不断增加,保持向前兼容。 6。ext2文件系统的2号inode为根目录,而我们的系统是0号inode为根目录,这个很随意,你设计一个文件系统定一个187号inode为根目录也没人拦着你。 如果你想了解ext2文件系统的全部细节,有三种方式。 1。看源码,linux1。0后的源码都有ext2文件系统的实现,源码是最准确的。 2。看官方文档,这里有个pdf连接。https:www。nongnu。orgext2docext2。pdf 3。看优质博客,这里我推荐一个。http:docs。linuxtone。orgebooksC