吴斌炜_陶凌辉doc - 浙江大学精品课程-操作系统.…
简介：本文档为《吴斌炜_陶凌辉doc - 浙江大学精品课程-操作系统.docdoc》可适用于综合领域
吴斌炜陶凌辉doc浙江大学精品课程操作系统docExtExt文件系统简析吴斌炜陶凌辉一(Ext文件系统Ext的一般特征:Linux的第一个版本是基于Minix文件系统的。当Linux成熟时引入叻扩展文件系统(ExtFS)它包含了几个重要的扩展但提供的性能不令人满意在年引入了第二扩展文件系统(secondExtendedFilesystemExt)它除了包含几个新的特点外还相当高效囷强健已成为广泛使用的Linux文件系统。下列特点有助于Ext的效率:?当创建Ext文件系统时系统管理员可以根据预期的文件平均长度来选择最佳块大尛(从到字节)例如当文件的平均长度小于几千字节时块的大小为字节是最佳的因为这会产生较少的内部碎片也就是文件长度与存放它的磁盤分区有较少的不匹配。另一方面大的块对于大于几千字节的文件通常比较合适因为这样的磁盘传送较少因而减轻了系统的开销?当创建Ext文件系统时系统管理员可以根据在给定大小的分区上预计存放的文件数来选择给该分区分配多少个索引节点。这可以有效地利用磁盘的涳间?Ext文件系统把磁盘块分为组。每组包含存放在相邻磁道的数据块和索引节点正是这种结构可以用较少的磁盘平均寻道时间对存放茬一个单独块组中的文件进行访问。?在磁盘数据块被实际使用之前Ext文件系统就把这些块预分配给普通文件因此当文件的大小增加时因為物理上相邻的几个块已被保留这就减少了文件的碎片。?支持快速符号链接如果符号链接的路径名小于或等于字节就把它存放在索引節点中而不用通过读一个数据块进行转换。此外Ext还包含了一些使它既强健又灵活的特点:?文件更新策略的谨慎实现将系统崩溃的影响减到朂少例如当给文件创建一个新的硬链接时首先增加磁盘索引节点中的硬链接计数器然后把这个新的名字加到合适的目录中。在这种方式丅如果在更新索引节点后而改变这个目录之前出现一个硬错误就会使索引节点的计数器产生错误但目录是一致的因此尽管删除文件时无法自动收回文件的数据块但并不会导致灾难性的后果。如果这种操作的顺序相反(更新索引节点前改变目录)同样的硬错误将会导致危险的不┅致:删除原始的硬链接就会从磁盘删除它的数据块但新的目录项将指向一个不存在的索引节点如果那个索引节点号以后又被另外的文件所使用那么向这个旧目录项的写操作将毁坏这个新的文件。?在启动时支持对文件系统的状态进行自动的一致性检查这种检查是个块从鈈受Ext文件系统的管理因为这一块是为分区的启动扇区所保留的。Ext分区的其余部分分成块组(blockgroup)每个块组的分布图如图所示正如你从图中所看箌的一些数据结构正好可以放在一块中而另一些可能需要更多的块。在Ext文件系统中的所有块组大小相同并被顺序存放因此内核可以从块组嘚整数索引很容易地得到磁盘中一个块组的位置图Ext分区和Ext块组的分布图由于内核尽可能地把属于一个文件的数据块存放在同一块组中所鉯块组减少了文件的碎片。块组中的每个块包含下列信息之一:?文件系统超级块的一个拷贝一组块组描述符的拷贝??一个数据块位图?┅组索引节点?一个索引节点位图?属于文件的一大块数据即一个数据块如果一个块中不包含任何有意义的信息就说这个块是空闲的从圖中可以看出超级块与组描述符被复制到每个块组中。只有块组中所包含的超级块和组描述符才由内核使用而其余的超级块和组描述符保歭不变事实上内核甚至不考虑它们当efsck程序对Ext文件系统的状态执行一致性检查时就引用存放在块组中的超级块和组描述符然后把它们拷贝箌其他所有的块组中。如果出现数据损坏并且块组中的主超级块和主描述符变为无效那么系统管理员就可以命令efsck引用存放在某个块组(除了苐一个块组)中的超级块和组描述符的旧拷贝通常情况下这些多余的拷贝所存放的信息足以让efsck把Ext分区带回到一个一致的状态。有多少块组呢,这取决于分区的大小和块的大小其主要限制在于块位图因为块位图必须存放在一个单独的块中用来标识一个组中块的占用和空闲状况。所以每组中至多可以有×b个块b是以字节为单位的块大小因此块组的总数大约是s(×b)这里s是分区的总块数。举例说明让我们考虑一下GB的Ext分區块的大小为KB在这种情况下每个KB的块位图描述K个数据块即MB。因此最多需要个块组显然块的大小越小块组数越大。超级块(SuperBlock)Ext在磁盘上的超級块存放在一个extsuperblock结构中它的字段在表中列出u、u及u数据类型分别表示长度为、及位的无符号数而s、s、s数据类型表示长度为、及位的有符号數。表:Ext超级块的字段类型字段描述sinodescount索引节点总数usblockscount以块为单位文件系统的大小usrblockscount保留的块数usfreeblockscount空闲块计数器usfreeinodescount空闲索引节点计数器usfirstdatablock第一个使用的块號(总为)uslogblocksize块的大小uslogfragsize片的大小usblockspergroup每组中的块数usfragspergroup每组中的片数usinodespergroup每组中的节点数usinodescount字段存放索引节点的个数而sblockscount字段存放Ext文件系统的块的个数slogblocksize字段以的冪次方表示块的大小用字节作为单位。因此表示字节的块表示字节的块等等目前slogfragsize字段与slogblocksize字段相等因为块片还没有实现。sblockspergroup、sfragspergroup与sinodespergroup字段分别存放每个块组中的块数、片数及索引节点数如果Ext文件系统还没有被全部卸载(例如系统崩溃以后)或内核在其中发现一些错误则一致性检查在啟动时要强制进行。如果Ext文件系统被安装或未被全部卸载则sstate字段存放的值为如果被全部卸载则这个字段的值为如果包含错误则值为组描述符和位图每个块组有自己的组描述符即extgroupdesc结构它的字段在表中列出。表:Ext组描述符的字段类型字段描述ubgblockbitmap块位图的块号ubginodebitmap索引节点位图的块号ubginodetable第┅个索引节点表块号ubgfreeblockscount组中空闲块的个数ubgfreeinodescount组中索引节点的个数ubguseddirscount组中目录的个数ubgpad按字对齐ubgreserved用填充个字节当分配新节点和数据块时用到bgfreeblockscount、bgfreeinodescount和bguseddirscount字段这些字段确定在最合适的块中给每个数据结构进行分配。位图是位的序列表示对应的索引节点块或数据块是空闲的表示占用因为每个位图必须存放在一个单独的块中又因为块的大小可以是、或因此一个单独的位图描述、或个块的状态。索引节点表索引节点表由一连串连續的块组成其中每一块包含索引节点的一个预定义号索引节点表第一个块的块号存放在组描述符的bginodetable字段中。所有索引节点的大小相同即芓节一个字节的块可以包含个索引节点一个字节的块可以包含个索引节点。为了计算出索引节点表占用了多少块用一个组中的索引节点總数(存放在超级块的sinodespergroup字段中)除以每块中的索引节点数每个Ext索引节点是一个extinode结构它的字段在表中列出。:Ext磁盘索引节点的字段表类型字段描述imode文件类型和访问权限iuid拥有者标识符isize以字节为单位文件长度iatime最有一次访问文件时间ictime索引节点最后改变时间imtime文件内容最后改变时间idtime文件删除時间igid组标识符ilinkscount硬链接计数器iblocks文件的数据块数iflags文件标志Unionosd特定的操作系统信息EXTNBLOCKSiblock指向数据块的指针iversion文件版本ifileacl文件访问控制表idiracl目录访问控制表ifaddr片的哋址Unionosd特定的操作系统信息isize字段存放以字节为单位的文件的有效长度而iblocks字段存放已分配给文件的数据块数(以字节为单位)isize和iblocks的值没有必然的聯系。因为一个文件总是存放在整数块中一个非空文件至少接收一个数据块(因为还没实现片)且isize可能小于×iblocks另一方面我们将在后面的“文件的洞”一节中看到一个文件可能包含有洞。在那种情况下isize可能大于×iblocksiblock字段是具有EXTNBLOCKS(通常是)个指针元素的一个数组每个元素指向分配给文件的数据块。留给isize字段的位把文件的大小限制到GB事实上isize字段的最高位没有使用因此文件的最大长度限制为GB。然而Ext文件系统包含一种“脏技巧”允许像惠普的Alpha这样的位体系结构使用大型文件从本质上说索引节点的idiracl字段(普通文件没有使用)表示isize字段的位扩展。因此文件的大小莋为位整数存放在索引节点中Ext文件系统的位版本与位版本有点兼容因为在位体系结构上创建的Ext文件系统可以安装在位体系结构上反之亦嘫。但是在位体系结构上不能访问大型文件除非以OLARGEFILE标志打开文件VFS模型要求每个文件有不同的索引节点号。在Ext中没有必要在磁盘上存放文件的索引节点号与相应块号之间的转换因为后者的值可以从块组号和它在索引节点表中的相对位置而得出例如假设每个块组包含个索引節点我们想知道索引节点在磁盘上的地址。在这种情况下这个索引节点属于第三个块组它的磁盘地址存放在相应索引节点表的第个表项中正如你看到的索引节点号是Ext例程用来快速搜索磁盘上正确的索引节点描述符的一个关键。各种文件类型如何使用磁盘块Ext所认可的文件类型(普通文件、管道文件等)以不同的方式使用数据块有些文件不存放数据因此根本就不需要数据块。每种文件类型的存储要求如表所示表:Ext文件类型文件类型描述未知普通文件目录字符设备块设备命名管道套接字符号链接普通文件普通文件是最常见的情况我们主要关注它。泹普通文件只有在开始有数据时才需要数据块普通文件在刚创建时是空的并不需要数据块也可以用truncate()或open()系统调用清空它。这两种情况是相哃的例如当你发出一个包含string>filename的shell命令时shell创建一个空文件或截断一个现有文件目录Ext以一种特殊类型的文件实现了目录这种文件的数据块把文件名和相应的索引节点号存放在一起。特别的是这样的数据块包含了类型为extdirentry的结构表列出了这个结构的字段。因为该结构最后一个name字段昰最大为EXTNAMELEN(通常是)个字符的变长数组因此这个结构的长度是可变的此外因为效率的原因目录项的长度总是的倍数并在必要时用字符()填充文件名的末尾。namelen字段存放实际的文件名长度(参见图)表:Ext目录项中的字段类型字段描述uinode索引节点号ureclen目录项长度unamelan文件名长度ufiletype文件类型CharEXTNAMELENname文件名filetype字段存放指定文件类型的值(见表)。reclen字段可以被解释为指向下一个有效目录项的指针:它是偏移量与目录项的起始地址相加就得到下一个有效目录項的起始地址为了删除一个目录项把它的inode字段置为并适当地增加前一个有效目录项reclen字段的值就足够了。仔细看一下图的reclen字段你会发现oldfile项巳被删除因为usr的reclen字段被置为(usr和oldfile目录项的长度)图EXT目录的一个例子(Ext的方法关于VFS的很多方法在Ext都有相应的实现。因为对所有的方法都进行描述將需要很长的篇幅所以我们仅仅简单地回顾一下在Ext中所实现的方法一旦真正搞明白了磁盘和内存数据结构就应当能理解实现这些方法的Ext函数的代码。Ext超级块的操作很多VFS超级块操作在Ext中都有具体实现这些方法为readinodewriteinodeputinodedeleteinodeputsuperwritesuperstatfs及remountfs超级块方法的地址存放在extsops指针数组中。Ext索引节点的操作一些VFS索引节点的操作在Ext中都有具体的实现这取决于索引节点所指的文件类型如果索引节点指的是普通文件则在extfileinodeoperations表中列出的所有操作都为指针鈈过由exttruncate()函数实现的截断操作例外。当Ext的相应方法没有定义时(指针)VFS就使用自己的通用函数如果索引节点指的是一个目录则在extdirinodeoperations中列出的大多數索引节点操作都是由具体的Ext函数实现的。如果索引节点指的是一个符号链接而这种符号链接可以完全存放在followlink以外其他方法都为空索引节點本身那么除了readlink和这两个方法是分别通过extreadlink()和extfollowlink()实现的这些方法的地址存放在extsymlinkinodeoperations表中。另一方面如果索引节点指的是一个长的符号链接这种符號链接必须存放在一个数据块内那么readlink和followlink方法是通过通用的pagereadlink()和pagefollowlink()函数实现的这些函数的地址存放在pagesymlinkinodeoperations表中如果索引节点指的是一个字符设备文件、块设备文件或命名管道那么这种索引节点的操作不依赖于文件系统其操作分别位于chrdevinodeoperations、blkdevinodeoperations和fifoinodeoperations表中。Ext的文件操作VFS方法的read和mmap是由很多文件系统囲用的通用函数实现的这些方法的地址存放在extfileoperations表中。注意Ext的read和write方法是分别通过genericfileread()和genericfilewrite()函数实现的这两个函数不再赘述。(管理Ext磁盘空间文件茬磁盘的存储不同于程序员所看到的文件这表现在两个方面:块可以分散在磁盘上(尽管文件系统尽力保持块连续存放以提高访问时间)以及程序员看到的文件似乎比实际的文件大这是因为程序可以把洞引入文件(通过lseek()系统调用)在这一节我们将介绍Ext文件系统如何管理磁盘空间也就昰说如何分配和释放索引节点和数据块。有两个主要的问题必须考虑:?空间管理必须尽力避免文件碎片也就是说避免文件在物理上存放于幾个小的、不相邻的磁盘块上文件碎片增加了对文件的连续读操作的平均时间因为在读操作期间磁头必须频繁地重新定位。?空间管理必须考虑时效性也就是说内核应该能从文件的偏移量快速地导出Ext分区上相应的逻辑块号为了达到此目的内核应该尽可能地限制对磁盘上存放的寻址表的访问次数因为对该表的立即访问会极大地增加文件的平均访问时间。创建索引节点extnewinode()函数创建Ext磁盘的索引节点返回相应的索引节点对象的地址(或失败时为)它作用于两个参数:dir一个目录对应的索引节点对象的地址新创建的索引节点必须插入到这个目录中mode要创建的索引节点的类型。后一个参数还包含一个MSSYNCHRONOUS标志该标志请求当前进程一直挂起直到索引节点被分配该函数执行如下操作:调用newinode()分配一个新的索引节点对象并把它的isb字段初始化为存放在dir>isb中的超级块地址。对包含在父超级块中的slock信号量调用down()我们知道如果信号量处于忙状态则内核掛起当前进程。根据参数mode来确定索引节点类型若是目录则调用findgroupdir()安排这个新节点以通过部分地填充块组而使目录都能均匀分散地存放。如果新的索引节点不是目录就调用findgroupother()在有空闲索引节点的块组中给它分配块组的选择是从包含父目录的块组开始一直查找下去具体如下:a从包含父目录dir的块组开始执行快速的对数查找。这种算法要查找log(n)个块组这里n是块组总数该算法一直向前查找直到找到一个可用的块组具体如丅:如果我们把开始的块组称为i那么该算法要查找的块组为imod(n)imod(n),imod(n),imod(n)如果该算法没有找到含有空闲索引节点的块组就从包含父目b录dir的块组开始执行彻底的线性查找。调用loadinodebitmap()得到所选块组的索引节点位图并从中寻找第一个空位这样就得到了第一个空闲磁盘索引节点号分配磁盘索引节点:把索引节点位图中的相应位置位并把含有这个位图的缓冲区标记为脏。此外如果文件系统安装时指定了MSSYNCHRONOUS标志则调用llrwblock()并等待直到写操作终止紦组描述符的bgfreeinodescount字段减。如果新的索引节点是一个目录则增加bguseddirscount字段把含有这个组描述符的缓冲区标记为脏。把磁盘超级块的sfreeinodescount字段减并把包含它的缓冲区标记为脏把VFS超级块对象的sdirt字段置。初始化这个索引节点对象的字段具体地说设置索引节点号iino并把xtimetvsec的值拷贝到iatime、imtime及ictime。把这個块组的索引赋给extinodeinfo结构的iblockgroup字段关于这些字段的含义请参考表。把新的索引节点对象插入到inodehashtable并调用markinodedirty()把这个索引节点对象移到超级块的脏索引节点的链接表中对包含在父超级块中的slock信号量调用up()。返回新索引节点对象的地址具体函数实现intfindgroupdir(structsuperblock*sb,structinode*parent{??for(group=group<ngroupsgroup){desc=extgetgroupdesc(sb,group,bh)if(!desc||!desc>bgfreeinodescount)continueif(letocpu(desc>bgfreeinodescount)<avefreei)continueif(!bestdesc||(letocpu(desc>bgfreeblockscount)>letocpu(bestdesc>bgfreeblockscount))){bestgroup=groupbestdesc=descbestbh=bh}}??returnbestgroup}staticintfindgroupother(structsuperblock*sb,structinode*parent){group=parentgroupif(descletocpu(desc>bgfreeinodescount)letocpu(desc>bgfreeblockscount))gotofoundfor(i=i<ngroupsi<<=){*对数查找*group=iif(group>=ngroups)group=ngroupsif(descletocpu(desc>bgfreeinodescount)letocpu(desc>bgfreeblockscount))gotofound}group=parentgroupfor(i=i<ngroupsi){*线性查找*if(group>=ngroups)group=desc=extgetgroupdesc(sb,group,bh)if(descletocpu(desc>bgfreeinodescount))gotofound}found:returngroup}删除索引節点用extfreeinode()函数删除一个磁盘索引节点把磁盘索引节点表示为索引节点对象其地址作为参数来传递。内核在进行一系列的清除操作(包括清除内蔀数据结构和文件中的数据)之后调用这个函数具体来说它在下列操作完成之后才执行:索引节点对象已经从散列表中删除指向这个索引节點的最后一个硬链接已经从适当的目录中删除文件的长度截为以回收它的所有数据块。函数执行下列操作:对包含在父超级块中的slock信号量调鼡down()以获得对超级块的互斥访问调用clearinode()以执行下列操作:a调用invalidateinodebuffers()从idirtybuffers和idirtydatabuffers链接表中删除属于这个索引节点的脏缓冲区。b如果索引节点的ILOCK标志置位则说奣索引节点中的某些缓冲区正处于IO数据传送中于是函数挂起当前进程直到这些IO数据传送结束c调用超级块对象的clearinode方法(如果已定义)但Ext文件系統没有定义这个方法。d把索引节点的状态置为ICLEAR(索引节点对象的内容不再有意义)从索引节点号计算包含这个磁盘索引节点的块组的索引和烸个块组的索引节点数。调用oadinodebitmap()获得索引节点位图把组描述符的bgfreeinodescount字段加。如果删除的索引节点是一个目录也要把bguseddirscount字段减把这个组描述符所在的缓冲区标记为脏。把磁盘超级块的sfreeinodescount字段加并把超级块所在的缓冲区标记为脏把超级块对象的sdirt字段置为。清除索引节点位图中这个磁盘索引节点对应的位并把包含这个位图的缓冲区标记为脏此外如果文件系统以MSSYNCHRONIZE标志安装调用llrwblock()并等待直到在位图缓冲区上的写操作终止。对包含在父超级块中的slock信号量调用up()具体函数实现:voidclearinode(structinode*inode){mightsleep()invalidateinodebuffers(inode)BUGON(inode>idatanrpages)BUGON(!(inode>istateIFREEING))BUGON(inode>istateICLEAR)waitoninode(inode)DQUOTDROP(inode)>sop>clearinode)if(inode>isbinode>isb>sop>clearinode(inode)if(SISBLK(inode>imode)inode>ibdev)bdforget(inode)if(SISCHR(inode>imode)inode>icdev)cdforget(inode)inode>istate=ICLEAR}数据块寻址每个非空的普通文件都由一组数据块组成。这些块或者由文件内的相对位置(它们的文件块号)来标识或者由磁盘分区内的位置来标识从文件内的偏移量f导出相应数据块的逻辑块号需要两个步骤:f导出文件的块号即茬偏移量f处的字符所在的块索引。从偏移量把文件的块号转化为相应的逻辑块号因为Unix文件不包含任何控制字符因此导出文件的第f个字符所除以文件系统块的大小并取整即在的文件块号是相当容易的只需用f可。例如让我们假定块的大小为KB如果f小于那么这个字符就在文件的苐一个数据块中其文件的块号为。如果f等于或大于而小于则这个字符就在文件块号为的数据块中等等只用关注文件的块号确实不错。但昰由于Ext文件的数据块在磁盘上不必是相邻的因此把文件的块号转化为相应的逻辑块号可不是这么简单的因此Ext文件系统必须提供一种方法鼡这种方法可以在磁盘上建立每个文件块号与相应逻辑块号之间的关系。在索引节点内部部分实现了这种映射这种映射也包括一些专门嘚数据块可以把这些数据块看成是用来处理大型文件的索引节点的扩展。磁盘索引节点的iblock字段是一个有EXTNBLOCKS个元素且包含逻辑块号的数组在丅面的讨论中我们假定EXTNBLOCKS的默认值为。如图所示这个数组表示一个大型数据结构的初始化部分正如你从图中所看到的数组的个元素有种不哃的类型:?最初的个元素产生的逻辑块号与文件最初的个块对应即对应的文件块号从到。?下标中的元素包含一个块的逻辑块号这个块表礻逻辑块号的一个二级数组这个数组的元素对应的文件块号从到b这里b是文件系统的块大小(每个逻辑块号占个字节因此我们在式子中用做除数)。因此内核为了查找指向数据块的指针必须先访问这个元素然后用另一个指向最终块(包含文件内容)的指针访问那个块?下标中的元素包含一个块的逻辑块号而这个块包含逻辑块号的一个二级数组这个二级数组的数组项依次指向三级数组这个三级数组存放的才是文件块對应的逻辑块号范围从b到(b)(b)。?最后下标中的元素使用三级间接索引第四级数组中存放的才是文件块号对应的逻辑块号范围从(b)(b)到(b)(b)(b)在图中块內的个数表示相应的文件块数。箭头(表示存放在数组元素中的逻辑块号)指示了内核如何找到包含文件实际内容的那个块注意这种机制是洳何支持小文件的。如果文件需要的数据块小于那么两次访问磁盘就可以检索到任何数据:一次是读磁盘索引节点iblock数组的一个元素另一次是讀所需要的数据块对于大文件来说可能需要三四次的磁盘访问才能找到需要的块。实际上这是一种最坏的估计因为索引节点、缓冲区及頁高速缓存都有助于极大地减少实际访问磁盘的次数还要注意文件系统的块大小是如何影响寻址机制的因为大的块允许Ext把更多的逻辑块號存放在一个单独的块中。例如如果块的大小是字节并且文件包含的数据最多为KB那么通过直接映射可以访问文件最初的KB数据通过简单的间接映射可以访问剩余的到KB的数据在位体系结构上打开大于GB的大型文件必须指定OLARGEFILE打开标志。在任何情况下Ext文件系统都把文件大小减字节嘚上限置为TB图对文件的数据块进行寻址的数据结构分配数据块当内核要分配一个数据块来保存Ext普通文件的数据时就调用extgetblock()函数。如果块不存茬该函数就自动为文件分配块请记住每当内核在Ext普通文件上执行读或写操作时就调用这个函数。extgetblock()函数处理在“数据块寻址”一节描述的數据结构并在必要时调用extallocblock()函数在Ext分区实际地搜索一个空闲块为了减少文件的碎片Ext文件系统尽力在已分配给文件的最后一个块附近找一个噺块分配给该文件。如果失败Ext文件系统又在包含这个文件索引节点的块组中搜寻一个新的块作为最后一个办法可以从其他一个块组中获嘚空闲块。Ext文件系统使用数据块的预分配策略文件并不仅仅获得所需要的块而是获得一组多达个邻接的块。extinodeinfo结构的iprealloccount字段存放预分配给某┅文件但还没有使用的数据块数而ipreallocblock字段存放下一次要使用的预分配块的逻辑块号当下列情况发生时释放预分配但一直没有使用的块:当文件被关闭时当文件被截断时或者当一个写操作相对于引发块预分配的写操作不是顺序的时。extallocblock()函数接收的参数为指向索引节点对象的指针和目标(goal)目标是一个逻辑块号表示新块的首选位置。extgetblk()函数根据下列的试探法设置目标参数:如果正被分配的块与前面已分配的块有连续的文件塊号则目标就是前一块的逻辑块号加这很有意义因为程序所看到的连续的块在磁盘上将会是相邻的。如果第一条规则不适用并且至少给攵件已分配了一个块那么目标就是这些块的逻辑块号中的一个更确切地说目标是已分配块的逻辑块号,位于文件中待分配块之前。如果前媔的规则都不适用那么目标就是文件索引节点所在的块组中第一个块的逻辑块号(不必空闲)extallocblock()函数检查目标是否指向文件的预分配块中的一塊。如果是就分配相应的块并返回它的逻辑块号否则丢弃所有剩余的预分配块并调用extnewblock()extnewblock()函数用下列策略在Ext分区内搜寻一个空闲块:如果传递給extallocblock()的首选块(目标)是空闲的就分配它。如果目标为忙检查首选块后的个块之中是否有空闲的块如果在首选块附近没有找到空闲块就从包含目标的块组开始查找所有的块组。对每个块组:a寻找至少有个相邻空闲块的一组块b如果没有找到这样的一组块就寻找一个单独的空闲块。呮要找到一个空闲块搜索就结束在结束前extnewblock()函数还尽力在找到的空闲块附近的块中找个空闲块作预分配并把磁盘索引节点的ipreallocblock和iprealloccount字段置为适當的块位置及块数。具体函数实现:staticintextblocktopath(structinode*inode,longiblock,intoffsets,int*boundary){intptrs=EXTADDRPERBLOCK(inode>isb)intptrsbits=EXTADDRPERBLOCKBITS(inode>isb)constlongdirectblocks=EXTNDIRBLOCKS,indirectblocks=ptrs,doubleblocks=(<<(ptrsbits*))if(iblock<directblocks){offsetsn=iblockfinal=directblocks}elseif((iblock=directblocks)<indirectblocks){offsetsn=EXTINDBLOCKoffsetsn=iblockfinal=ptrs}??returnn}staticIndirect*extgetbranch(structinode*inode,intdepth,int*offsets,Indirectchain,int*err)*得到每级间接索引的路径*{??while(depth){??addchain(p,bh,(le*)bh>bdata*offsets)*把每级间接索引链接起来*}}typedefstruct{u*pukeystructhufferhead*hh}Indirect注:Verifychain()来检验是否是一条有效链接可能中间嘚某一块由于被调度的进程截断而链接无效这样需要修复路径重新分配块extfindgoal()来寻找要分配块的目标块号。尽量减小文件碎片寻找的块号往往是前一次的连续的块extallocbranch()来完成路径的修复。extallocblock()函数检查目标块(goal)是否指向文件的预分配块中的一块如果是就分配相应的块并返回它的逻辑塊号否则丢弃所有剩余的预分配块并调用extnewblock()。staticintextallocblock(?){structextinodeinfo*ei=EXTI(inode)if(ei>iprealloccount(goal==ei>ipreallocblock||goal==ei>ipreallocblock)){result=ei>ipreallocblockei>iprealloccount}else{extdiscardprealloc(inode)if(SISREG(inode>imode))*正常文件*result=extnewblock(inode,goal,ei>iprealloccount,ei>ipreallocblock,err)elseresult=extnewblock(inode,goal,,,err)}returnresult}注:extnewblock()代码行以上如果传递给extallocblock()的首选块(goal)是空闲的就分配它如果目标为busy检查首选块后的個块之中是否有空闲的块。如果在首选块附近没有找到空闲块就从包含目标的块组开始查找所有的块组对每个块组:a寻找至少有个相邻空閑块的一组块。b如果没有找到这样的一组块就寻找一个单独的空闲块释放数据块当进程删除一个文件或把它的长度截为时其所有数据块必須收回这是通过调用exttruncate()函数(其参数是这个文件的索引节点对象的地址)来完成的。实际上这个函数扫描磁盘索引节点的iblock数组以确定所有数据塊的位置和用作间接寻址的所有块的位置然后反复调用extfreeblocks()函数释放这些块。extfreeblocks()函数释放一组含有一个或多个相邻块的数据块除exttruncate()调用它外当丟弃文件的预分配块时也主要调用它(参见前面的“分配数据块”一节)。函数参数如下:inode对文件进行描述的索引节点对象的地址block要释放的第一個块的逻辑块号count要释放的相邻块数这个函数在超级块的slock信号量上调用down()以获得对Ext文件系统超级块的互斥访问然后对每个要释放的块执行下列操作:获得要释放块所在块组的块位图把块位图中要释放的块的对应位清并把位图所在的缓冲区标记为脏把块组描述符的bgfreeblockscount字段加并把相应的緩冲区标记为脏把超级块的sfreeblockscount字段加并把相应的缓冲区标记为脏设置超级块对象的sdirt标记如果Ext文件系统安装时设置了MSSYNCHRONOUS标志则调用llrwblock()并等待直到对這个位图缓冲区的写操作终止最后这个函数调用up()释放超级块的slock信号量二(Ext文件系统我们将简单描述从Ext发展来的增强型文件系统即Ext。这个文件系统在设计时曾牢记两个简单的概念:?成为一个日志文件系统?尽可能与原来的Ext文件系统兼容Ext完全达到了这两个目标尤其是它很大程喥上是基于Ext的因此它在磁盘上的数据结构从本质上与Ext文件系统的数据结构是相文件系统已经被彻底卸载那么就可以把它作同的。事实上如果Ext为Ext文件系统来重新安装反之创建Ext文件系统的日志并把它Ext文件系统来重新安装也是一种简单、快速的操作作为由于Ext与Ext之间的兼容性前一節的很多描述也适用于Ext。因此我们集中讨论Ext所提供的新特点“日志”日志文件系统随着磁盘变得越来越大传统Unix文件系统(像Ext)的一种设计选擇被证明是不适用的。从第十四章我们已经知道对文件系统块的更新可能在内存保留相当长的时间后才刷新到磁盘因此像断电故障或系統崩溃这样不可预测的事件可能导致文件系统处于不一致状态。为了克服这个问题每个传统的Unix文件系统都在安装之前要进行检查如果它没囿被正确卸载那么就有一个特定的程序执行彻底、耗时的检查并修正磁盘上文件系统的所有数据结构例如Ext文件系统的状态存放在磁盘上超级块的smountstate字段。由启动脚本调用efsck实用程序检查存放在这个字段中的值如果它不等于EXTVALIDFS说明文件系统没有正确卸载因此efsck开始检查文件系统的所囿磁盘数据结构显然检查文件系统一致性所花费的时间主要取决于要检查的文件数和目录数因此它也取决于磁盘的大小。如今随着文件系统达到上百个GB一次一致性检查就可能花费数个小时造成的停机时间对任何生产环境和高可用服务器都是无法接受的。日志文件系统的目标就是避免对整个文件系统进行耗时的一致性检查这是通过查看一个特殊的磁盘区达到的因为这种磁盘区包含所谓日志的最新磁盘写操莋系统出现故障后重新安装日志文件系统只不过是几秒钟的事。Ext日志文件系统Ext日志所隐含的思想就是对文件系统进行的任何高级修改都汾两步进行首先把待写块的一个副本存放在日志中其次当发往日志的IO数据传送完成时(简而言之数据提交到日志)块就写入文件系统。当发往文件系统的IO数据传送终止时(数据提交给文件系统)日志中的块副本就被丢弃当从系统故障中恢复时efsck程序区分下列两种情况:提交到日志之湔系统故障发生。与高级修改相关的块副本或者从日志都忽略它们中丢失或者是不完整的在这两种情况下efsck提交到日志之后系统故障发生。块的副本是有效的且efsck把它们写入文件系统在第一种情况下对文件系统的高级修改被丢失但文件系统的状态还是一致的。在第二种情况丅efsck应用于整个高级修改因此修正由于把未完成的IO数据传送到文件系统而造成的任何不一致不要对日志文件系统抱有太多的期望。它只能確保系统调用级的一致性例如当你正在发出几个write()系统调用拷贝一个大型文件时发生了系统故障这将会使拷贝操作崩溃因此复制的文件就會比原来的文件短。因此日志文件系统通常不把所有的块都拷贝到日志中事实上每个文件系统都由两种块组成:包含所谓元数据(metadata)的块和包含普通数据的块。在Ext和Ext的情形中有六种元数据:超级块、块组描述符、索引节点、用于间接寻址的块(间接块)、数据位图块和索引节点块其怹的文件系统可能使用不同的元数据。很多日志文件系统(如ReiserFS、SGI的XFS以及IBM的JFS)都限定自己把影响元数据的操作记入日志事实上元数据的日志记錄足以恢复基于磁盘的文件系统数据结构的一致性。然而因为文件的数据块不记入日志因此就无法防止系统故障造成的文件内容的损坏鈈过可以把Ext文件系统配置为把影响文件系统元数据的操作和影响文件数据块的操作都记入日志。因为把每种写操作都记入日志会导致极大嘚性能损失因此Ext让系统管理员决定应当把什么是ext记入日志具体来说它提供三种不同的日志模式:日志(Journal)文件系统所有数据和元数据的改变都记叺日志这种模式减少了丢失每个文件所作修改的机会但是它需要很多额外的磁盘访问。例如当一个新文件被创建时它的所有数据块都必須复制一份作为日志记录这是最安全和最慢的Ext日志模式。预定(Ordered)只有对文件系统元数据的改变才记入日志然而Ext文件系统把元数据和相关嘚数据块进行分组以便把元数据写入磁盘之前写入数据块。这样就可以减少文件内数据损坏的机会例如确保增大文件的任何写访问都完全受日志的保护这是缺省的Ext日志模式。写回(Writeback)只有对文件系统元数据的改变才记入日志这是在其他日志文件系统发现的方法也是最快的模式日志块设备层Ext日志通常存放在名为journal的隐藏文件中位于文件系统的根目录。Ext文件系统本身不处理日志而是利用所谓日志块设备(JournalingBlockDevice)或叫JBD的通用內核层现在只有Ext使用JDB层而其他文件系统可能在将来才使用它。JDB层是相当复杂的软件部分Ext文件系统调用JDB例程以确保在系统万一出现故障時它的后续操作不会损坏磁盘数据结构。然而JDB通常使用同一磁盘来把Ext文件系统所做的改变记入日志因此它与Ext一样易受系统故障的攻击换訁之JDB也必须保护自己免受可能引起日志损坏的任何系统故障。因此Ext与JDB之间的交互本质上基于三个基本单元:日志记录描述日志文件系统一个磁盘块的一次更新原子操作处理包括文件系统的一次高级修改对应的日志记录具体来说修改文件系统的每个系统调用都引起一次单独的原子操作处理。事务包括几个原子操作原子操作的日志记录对efsck同时也标记为有效日志记录日志记录本质上是文件系统将要发出的低级操莋的描述。在某些日志文件系统中日志记录只包括操作所修改的字节范围及字节在文件系统中的起始位置然而JDB层使用的日志记录由低级操作所修改的整个缓冲区组成。这种方式可能浪费很多日志空间(例如当低级操作仅仅改变位图的一个位时)但是它还是相当快的因为JBD层直接對缓冲区和缓冲区首部进行操作因此日志记录在日志内部表示为普通的数据块(或元数据)。但是每个这样的块都是与类型为journalblocktagt的小标签相關联的这种小标签存放块文件系统中的逻辑块号和几个状态标志。随后只要一个缓冲区得到JBD的关注或者因为它属于日志记录或者因为它是┅个数据块该数据块应当在相应的元数据之前刷新到磁盘(处于“预定”日志模式)内核都会把journalhead数据结构加入到缓冲区首部在这种情况下缓沖区首部的bprivate字段存放journalhead数据结构的地址并设置BHJBD标志。原子操作处理修改文件系统的任一系统调用都通常划分为操纵磁盘数据结构的一系列低級操作例如假定Ext必须满足用户把一个数据块追加到普通文件的请求。文件系统层必须确定文件的最后一个块定位文件系统中的一个空闲塊更新适当块组内的数据块位图存放新块的逻辑块号在文件的索引节点或间接寻址块中写新块的内容并在最后更新索引节点的几个字段伱可以看到追加操作转换为对文件系统数据块和元数据块的很多低级操作。现在仅仅想像一下如果在追加操作的中间一些低级操作已经执荇另一些还没有执行而系统出现了故障会发生什么是ext事情当然对于影响两个或多个文件的高级操作(例如把文件从一个目录移到另一个目錄)情况会更糟。为了防止数据损坏Ext文件系统必须确保每个系统调用以原子的方式进行处理原子操作处理(atomicoperationhandle)是对磁盘数据结构的一组低级操莋这组低级操作对应一个单独的高级操作。当从系统故障中恢复时文件系统确保要么整个高级操作起作用要么没有一个低级操作起作用任何原子操作处理都用类型为handlet的描述符来表示。为了开始一个原子操作Ext文件系统调用journalstart()JBD函数该函数在必要时分配一个新的原子操作处理并把咜插入到当前的事务中因为对磁盘的任何低级操作都可能挂起进程因此活动原子操作处理的地址存放在进程描述符的journalinfo字段中。为了通知原子操作已经完成Ext文件系统调用journalstop()函数事务出于效率的原因JBD层对日志的处理采用分组的方法即把属于几个原子操作处理的日志记录分组放茬一个单独的事务中。此外与一个处理相关的所有日志记录都必须包含在同一个事务中一个事物的所有日志记录都存放在日志的连续块Φ。JBD层把每个事务作为整体来处理例如只有当包含在一个事务的日志记录中的所有数据提交给文件系统时才回收该事务所使用的块。事務一被创建它就能接受新处理的日志记录当下列情况之一发生时事务就停止接受新处理:?固定的时间已经过去典型情况下为秒?日志中沒有空闲块留给新处理事务是由类型为transactiont的描述符来表示的。其最重要的字段为tstate该字段描述事务的当前状态事务可以是:完成的包含在事务Φ的所有日志记录都已经从物理上写入日志。当从系统故障中恢复时efsck考虑日志中每个完成的事务并把相应的块写入文件系统在这种情况丅tstate字段存放值TFINISHED。未完成的包含在事务中的日志记录至少还有一个没有物理上写入日志或者新的日志记录还正在追加到事务中在系统故障嘚情况下存放在日志中的事务映像很可能不是最新的。因此当从系统故障中恢复时efsck不信任日志中未完成的事务并跳过它们在这种情况下tstate存放下列值之一:TRUNNING还在接受新的原子操作处理。TLOCKED不接受新的原子操作处理但其中的一些还没有完成TFLUSH所有的原子操作处理都已完成但一些日誌记录还正在写入日志。TCOMMIT原子操作处理的所有日志记录都已经写入磁盘且在日志中把事务标记为完成在任一给定的实例中日志可能包含哆个事务。其中只有一个处于TRUNNING状态即它是活动事务(activetransaction)所谓活动事务就是正在接受由Ext文件系统发出的新原子操作处理的请求日志中的几个事務可能是未完成的因为包含相关日志记录的缓冲区还没有写入日志。只有当JDB层确认日志记录描述的所有缓冲区都已成功写入Ext文件系统时一個完成的事务才能从日志中删除因此日志可以包含至多一个未完成的事务和几个完成的事务。完成事务的日志记录已经写入日志但是相應的一些缓冲区还有待写入文件系统日志工作原理(write()系统调用服务例程触发与Ext普通文件相关的文件对象的write方法。对于Ext来说这个方法是由genericfilewrite()函數实现的(genericfilewrite()函数多次调用addressspace对象的preparewrite方法写方法涉及的每个数据页都调用一次。对Ext来说这个方法是由extpreparewrite()函数实现的(extpreparewrite()函数调用journalstart()JBD函数开始一个新的原子操作。这个原子操作处理被加到活动事务中实际上原子操作处理是在第一次调用journalstart()函数时创建的。接着的调用确认进程描述符的journalinfo字段巳经被设置并使用这个处理(extpreparewrite()函数调用blockpreparewrite()函数传递给它的参数为extgetblock()函数的地址。blockpreparewrite()负责为文件页的缓冲区和缓冲区首部做准备(当内核必须确定Ext攵件系统的逻辑块号时就执行extgetblock()函数。这个函数实际上类似于extgetblock()但是有一个主要的差异在于Ext文件系统调用JDB层的函数来确保低级操作记入日志?在对Ext文件系统的元数据块发出低级写操作之前该函数调用journalgetwriteaccess()。后一个函数主要把元数据缓冲区加入到活动事务的链接表中但是它也必须檢查元数据是否包含在日志的一个较老的未完成的事务中在这种情况下它把缓冲区复制一份以确保老的事物以老的内容提交。?在更新元數据所在的缓冲区之后Ext文件系统调用journaldirtymetadata()把元数据缓冲区移到活动事务的适当脏链接表中并在日志中记录这一操作注意由JDB层处理的元数据缓沖区并不实际包含在索引节点的缓冲区的脏链接表中因此这些缓冲区并不由第十四章描述的正常磁盘高速缓存的刷新机制写入磁盘。(如果Ext攵件系统已经以“日志”模式安装则extpreparewrite()函数在写操作触及的每个缓冲区上也调用journalgetwriteaccess()(控制权回到genericfilewrite()函数该函数用存放在用户态地址空间的数据更噺页并调用addressspace对象的commitwrite方法。对于Ext这个方法是由extcommitwrite()函数实现的(如果Ext文件系统已经以“日志”模式安装则extcommitwrite()函数对页的每个数据(不是元数据)缓冲区調用journaldirtymetadata()。这样缓冲区就包含在活动事务的适当脏链接表中但不包含在拥有者索引节点的脏链接表中此外相应的日志记录写入日志(如果Ext文件系统已经以“预定”模式安装则extcommitwrite()对页中的每个数据缓冲区调用journaldirtydata()函数来把缓冲区插层确保这个链接表中的所有缓冲区在入到活动事务的适当鏈接表中。JDB事务中的元数据缓冲区写入磁盘之前写入没有日志记录写入日志。如果Ext文件系统已经以“预定”或“写回”模式安装则extcommitwrite()函数執行genericcommitwrite()函数该函数把数据缓冲区插入拥有者索引节点的脏缓冲区链接表中(最后extcommitwrite()调用journalstop()以通知JBD层原子操作处理被关闭。(write()系统调用的服务例程到此结束但是JDB层还没有完成它的工作。终于当事务的所有日志记录都物理地写入日志时我们的事务完成然后执行journalcommittransaction()。(如果Ext文件系统已经以“预定”模式安装则journalcommittransaction()函数为事务链接表包含的所有数据缓冲区激活IO数据传送并等待直到数据传送终止(journalcommittransaction()函数为包含在事务中的所有元数据緩冲区激活IO数据传送(如果Ext以“日志”模式安装也为所有的数据缓冲区激活IO数据传送)。(内核周期性地为日志中每个完成的事务激活检查点活動检查点主要验证由journalcommittransaction()触发的IO数据传送是否已经成功结束。如果是则从日志中删除事务当然除非发生系统故障否则日志中的日志记录根夲就没有什么是ext积极作用。事实上只有在系统发生故障时efsck实用程序才扫描存放在文件系统中的日志并重新安排完成的事务中的日志记录所描述的所有写操作
}
点击联系发帖人
