（计算机应用技术专业论文）linux中基于连续块的b树文件系统的设计与实现.pdf

华中科技大学硕士学位论文 摘要 ( 作为一种很有发展前途的操作系统，l i n u x 一出现就受到了企业服务器操作 系统市场的青睐，它的安全性和稳定性使其在该领域一枝独秀，市场占有率一直 保持强势增长。 访问速度和i o 效率是衡量服务器性能的重要标准。作为目前l i n u x 的主流 文件系统，e x t 2 文件系统在处理大文件和巨型目录结构时有一定的局限性。究其 原因，是由它的基本组织结构决定的，它是为中小型文件量身定做的，采用传统的 线性表和多级指针索引静态地组织数据，灵活性和效率都不高，随着海量存储器， 磁盘阵列的出现，e x t 2 文件系统的管理已经显得力不从心。2 7 。 为了从根本上改变这种现状，实现对文件的快速高效访问，加强对大型文件 系统的支持和管理，从改变文件系统的基本布局结构入手，提出并实现了一种基 于平衡块的b + 树文件系统( e b f s ) ，从三方面对文件系统的性能进行扩展：一方面， 采用b + 树来组织大文件数据，磁盘空闲块以及目录项。使用b + 树索引结构，对 于大型文件和目录对象而言，访问速度有了明显提高，时间复杂度从o ( n ) 提升到 o ( 1 0 9n ) ：而且b + 树结构也扩充了文件系统的寻址空间，由原来的4 g b 增长到5 1 2 万亿字节；第二方面，用连续块分配策略替代传统的块分配策略，减少了分配时 的i o 次数，保证文件数据尽量连续存储，减少了外部碎片，提高了文件顺序访 问的效率；第三方面，对于小型文件，直接将文件数据存放在i n o d e 节点的内嵌 数据区，提高小文件i o 性能的同时减少了内部碎片。 e b f s 文件系统己成功试用于我们同中国船舶重工集团公司7 0 9 研究所合作 开发的国防预研项目分布式实时操作系统d r l i n u x 中，该系统已通过国家 有关部门鉴定，具有良好的应用前景。 关键词：l i n u x ：文件系统；连续块；i n o d e 节点；b + 树 华中科技大学硕士学位论文 a b s t r a c t a sad r o m i s i n go p e r a t i o ns y s t e m ，l i n u xw a sf u l l y f a v o r e d b yt h e m a r k e to f e n t e r p r i s es e r v e ro p e r a t i o ns y s t e mb yi t sa d v a n t a g ei ns e c u r i t ya n ds t a b i l i t yl i n u xi s p e e r l e s s w h i c hm a d e i tm u c hs u p e r i o rt h a no t h e ro p e r a t i o ns y s t e m sa n d i t so c c u p a n c y k e e p si n c r e a s i n gi nt h es e r v e r m a r k e t a c c e s ss l c l e e da n di oe f f i c i e n c ya r et h ei m p o r t a n ts t a n d a r d si nj u d g i n g t h es e r v e r s p e r f o r m a n c e a st h em a i nf i l es y s t e m o fc u r r e n tl i n u xo s ，e x t 2f i l es y s t e mh a ss o m e d r a w b a c k si n p r o c e s s i n g t h e b i g f i l e sa n d g i a n tb i b l i o g r a p h i c s t r u c t u r e s t h e s e p r o b l e m s a r ed e t e r m i n e db ye x t 2 s i n t e r n a ls t r u c t u r e t h ee x t 2f i l e s y s t e mw a s d e s i g n e df o rt l em i d d l eo rs m a l lf i l e s ，i ta d o p t e dt r a d i t i o n a ll i n e a rl i s t a n dm u l t i l e v e l p o i n t e r si n d e xs t r u c t u r et oo r g a n i z ed a t as t a t i c a l l y , s oi t sf l e x i b i l i t ya n de f f i c i e n c ya r e n o tv e r yi d e a l w i t ht h ea p p e a r a n c eo f t h em a s s s t o r a g ea n d d i s ca r r a y , t h em a n a g e m e n t a b i l i t yo f e x t 2f i l es y s t e mi sn o te q u a lt oi t sa m b i t i o n i no r d e rt oc h a n g et h e s es i t u a t i o n s ，i m p l e m e n tt h er a p i da c c e s st of i l e s ，s t r e n g t h e n t h e s u p p o r t a n dm a n a g e m e n tf o r l a g e s c a l e f i l e s y s t e m ，w eb r i n g f o r w a r da n d i m p l e m e n ta f i l es y s t e mb a s e do ne x t e n ta n do r g a n i z e db yb + t r e e ( e b f s ) w h i c hc a n e x p a n dt h ef u n c t i o n so f f i l es y s t e mi nt h r e ea s p e c t s ：f i r s t l y , u s i n gb + t r e et oo r g a n i z e t h el a r g ef i l ed a t u m ，f r e eb l o c k sa n dd i r e c t o r ye n t r i e s b yb + t r e e i n d e x i n gs t r u t u r e ，t h e a c c e s ss p e e do fl a r g ef i l e sa n dd i r e c t o r y si sr a i s e do b v i o u s l y , t h et i m ec o m p l e x i t yi s i m p r o v e d f r o mo ( n ) t oo ( 1 0 9n ) i nt h em e a n t i m e ，t h ea d d r e s sa b i l i t yi se x p a n d e df r o m 4 g bt o512t r i l l i o n s e c o n d l y , t h et r a d i t i o n a lb l o c ka l o c a t i o np o l i c yi sr e p l a c e db yt h e e x t e n ta l l o c a t i o np o l i c y , w h i c hc a r lr e d u c et h ey ot i m e si na l l o c a t i o n ，k e e pt h ef i l e d a t u ms t o r e ds p a t i a l l y ，l e s s e nt h ee x t e r n a lf r a g m e n t i o na n di m p r o v et h ee f f i c i e n c yo f a c c e s s t h i r d l y , t os m a l lf i l e ，w ec a n s t o r et h ef i l ed a t u m d i r e c t l yi nt h ei n l i n ed a t af i e l d o ft h ei n o d e ，w h i c hc a ni m p r o v et h ei op e r f o r m a n c eo fs m a l lf i l ea n dl e s s e ni n t e r n a l f r a g m e n t i o n e b f ss h o w sg r e a tp e r f o r m a n c eo ni t st e s tr u ni nd r l i n u xs y s t e m ，ah i g h t e c h p r o j e c td e v e l o p e db y o u rr e s e a r c hg r o u pa n dt h es t a t ee x p l o r a t i o nr e s e a r c hi n s t i t u t eo f s h i p i n d u s t y ，t h es y s t e m h a s p a s s e dt h ea u t h e n t i c a t i o na n d h a san i c e rm a r k e t f o r e g r o u n d k e yw o r d s ：l i n u x ；f i l es y s t e m ；e x t e n t ；i n o d e ；b + t r e e 华中科技大学硕士学位论文 l绪论 1 1l i n u x 简介 l i n u x 是由l i n u xb e n e d i c tt o r v a l d s 等众多软件高手共同开发的，一种能运行 于多种平台( 如p c 及其兼容机，a l p h a 工作站，s u ns p a r c 工作站) 、源代码公 开、免费，功能强大、遵守p o s i x 标准、与u n i x 兼容的操作系统。 1 1 1l i n u x 历史 在计算机技术的发展史上，u n i x 操作系统的出现是一个重要的里程碑。早期 的u n i x ，特别是内核第6 版的源代码，曾免费供美国及一些西方大学和科研机构 使用。一方面为高校和科研机构普及使用计算机提供了条件；另一方面，也是最 重要的，为计算机软件的核心技术“操作系统”的教学和试验提供了条件。后来， u n i x 成了商品，其源代码受到了版权的保护，而且第6 版慢慢变得陈旧了，便逐 渐不再用u n i x 内核的源代码作为教材。 在这种情况下，出于教学的需要，荷兰教授a n d r e ws t a n e n b a u m 编写了一 个小型的“类u n i x ”操作系统m i n i x ，在p c 机上运行。其源代码在2 0 世纪8 0 年代 后期和9 0 年代前期曾被广泛采用。但是，m i n i x 虽然不失为一个不错的教学工具， 却缺乏实用价值。看到m i n i x 的这种缺点，芬兰大学生l i n u st o r v a l d s 决定在自己 的p c 机上，以m i n i x 为起点，按照u n i x 的设计，开发出一个真正可以实用的 u n i x 内核，并将其命名为l i n u x 。l i n u st o r v a l d s 的一个最重要的决定就是将其基 本完成的第一个l i n u x 内核版本放在了互联网上，一来把自己写的代码公诸于众， 二来邀请有兴趣的人参与。他的这种做法很快就引起了热烈的反应，并且与美国 “自由软件基金会“f s f 主张的开放源代码不谋而合。当时f s f 已经有计划要开发 一个类u n i x ( 但又不是u n i x ，所以称为g n u ，即g n ui sn o tu n i x ) 的操作系统 和应用环境，而l i n u x 的出现自然使得由l i n u st o r v a l d s 主持的l i n u x 内核开发、 改进和维护成为了f s f 的主要项目之一。另外，f s f 的其他项目，如g n u 的c 编译器g e e 、程序调试工具g d b 、还有各种s h e l l 和应用程序，乃至w e b 服务器 a p a c h e 、浏览器m o z i l l a ( 实际上就是n e t s c a p e ) 等等，则正好与之配套成龙。正 是在这种开发模式和开发环境下，l i n u x 逐渐发展和壮大起来，已经成为了i t 市 场的主要动力。 华中科技大学硕士学位论文 l _ 2 2l i n u x 的特点 l i n u x 的特点主要有以下几点i j 叫： 1 良好的开放性。l i n u x 是一个免费的、开放源码的操作系统，它是 f s f 的主要成员，任何人都可以通过i n t e m e t 免费得到它。用户可以按自己的要求 修改源码，并进行发布，只要遵守g p l 中的规定即可。 2 多平台支持。l i n u x 最初是在i n t e l8 0 3 8 6 平台上实现的，但是已经被移植 到各种主要的c p u 系列上，包括a l p h a 、m 6 8 k 、m i p s 、s p a r c 、p o w e r p c 等等。 同时，在同一个系列的c p u 上，l i n u x 内核还支持不同的系统结构，既支持常规 的单c p u 结构，也支持多c p u 结构。 3 符合国际通用标准。l i n u x 是符合p o s i x l 0 0 3 1 标准的操作系统。 p o s i x l 0 0 3 1 标准定义了一个最小的u n i x 操作系统接口，任何操作系统只有符合 这一标准，才可能运行u n i x 程序。因此许多u n i x 应用程序不需要修改就可以直 接运行在l i n u x 上。 4 l i n u x 是一个i n t e r n e t 软件。全世界的软件开发者都可以通过i n t e m e t 进行合作开发l i n u x 。正是这些才华非凡的人员每时每刻把最新的软件技术引进 l i n u x ，才使l i n u x 有最新鲜的血液，保持最强劲的生命力。 5 拥有先进的网络特性。l i n u x 对网络的支持比大部分操作系统都更出色，这 是由它的“网络之子”的背景所决定的。它几乎支持目前所有的网络协议，而且其 使用性能已经经历了实际应用的考验。 6 拥有真正的多用户、多任务能力。l i n u x 是一个多用户操作系统，允许多个 用户同时访问系统而不会造成用户之间的相互干扰。同时l i n u x 还具有多任务的 能力，同一个用户可以通过创建多个任务来并行处理多个工作。 7 动态链接能力。l i n u x 操作系统并非采用静态的链接方式，而是如同 w i n d o w s 中的“动态链接库”方法来实现应用程序和标准库的使用，从而使系统的 运行具有高效性。 1 1 3l i n u x 的功能 随着互联网的发展以及公开源代码的强大吸引力，越来越多的人加入到l i n u x 的项目开发中，并对l i n u x 内核和其子系统作出了巨大的贡献。l i n u x 的广泛平台 支持特性、以及由遵从p o s i x 标准带来的应用程序的可移植性，使得l i n u x 受到 了前所未有的欢迎。 华中科技大学硕士学位论文 从技术上讲，l i n u x 提供了下列功能【4 ，5 】： 1 多用户、多进程、多处理器( s m p ) 环境。 2 进程间通信机制。 3 进程控制。 4 高效、健全的存储管理机制。 5 p o s i x 风格的终端管理。 6 支持各种网络协议。 7 支持各种硬件。 8 动态和共享库。 9 支持多种文件系统。 1 2 课题背景 作为一种很有发展前途的操作系统，l i n u x 出现就受到了企业服务器操作 系统市场的青睐，它的安全性和稳定性使其在该领域一枝独秀，市场占有率一直 保持强势增长。根据有关统计，l i n u x 已经成为增长幅度最快的服务器操作系统， 而且在今后5 年中l i n u x 的增长速度将比其他所有操作系统的增长速度的总和还 要快。 l i n u x 在性能、可用性、安全性、协同性以及可管理性等方面所显示的明显 优势，已经赢得系统管理员的广泛认可和赞许。在中国的服务器操作系统市场上， 一批合资或本土的软件公司如中科红旗、中软总公司也纷纷投资开发基于开放源 代码的l i n u x 服务器操作系统。 l i n u x 在高端服务器应用上主要有如下优势： 1 有很高的稳定性和安全性 在x 8 6 硬件平台上运行时，l i n u x 是非常可靠和稳定的，可以长时间 稳定的运行。而且由于l i n u x 对账号和权限的管理比较严密，不容易受到入侵和 感染。 2 强大的网络功能 l i n u x 天生就是一个网络操作系统，几乎所有的网络协议和网络接口都 已经被定制在l i n u x 中。l i n u x 内核在处理网络协议方面比标准的u n i x 更具执行 效率，在每一个端口上有更高的吞吐量。 3 低成本 l i n u x 的开放源代码特性，让企业用户以很低的成本就拥有稳定安全而功能强 华中科技大学硕士学位论文 大的应用平台。 尽管如此，l i n u x 作为服务器也存在一些不足之处。其中一个关键问题就是 e x t 2 文件系统。尽管l i n u x 可以支持种类繁多的文件系统，但是几乎所有的l i n u x 发行版都用e x t 2 作为默认的文件系统。e x t 2 文件系统的思想是在9 0 年代初提出 的，当时由于硬盘等存储媒介的容量较小，设计者考虑的对象主要是中小文件。 当时，没人能想像得出硬盘的容量近年来会增长得如此迅速。随着海量存储器， 磁盘阵列的出现，e x t 2 文件系统的管理已经显得力不从心。 e x t 2 文件系统在处理大文件和巨型目录结构时有定的局限性：它在处理大 文件时显得不是很有效率，不能处理超过4 g 字节大小的文件，并且性能也不是 很好。而且无法回收巨型目录。对于一般的计算机用户而言，这种局限可能不是 很明显，但在中和高端服务器中，就非常关键了。比如服务器的数据库的容量， 往往超过4 g 字节，而某些磁盘阵列的文件系统的大小，更要用t b 字节来统计了。 随着硬盘的容量增大，访问文件的速度也越来越慢，文件系统的性能也会逐渐下 降。对于那些实时性要求很高的系统来说，显然不能满足要求。 要从根本上改变这种现状，有两个途径：一种是从硬件上着手，提高对存储 媒介的i o 速度，减少访问延迟；另一种是从软件着手，改变文件系统的布局结 构，使用效率更高的算法对文件组织进行访问。 本课题的意义正在于此，即探寻一种新的数据结构来组织文件系统的磁盘布 局，从而加强对大型文件系统的支持和管理，提高对文件的快速高效访问，优化 性能。本课题是中国船舶重工集团公司7 0 9 研究所与本课题组合作的国防预研项 目d r l i n u x 分布式实时操作系统的子项目。 1 3 相关研究领域及其发展现状 1 3 1 文件系统的历史 l i n u x 的第一个文件系统是m i n i x ，它原本是为m i n i x 操作系统所使用的。 l i n u s t o r v a l d s 写l i n u x 之前，学习的就是t a n e n b a u m 所写的o p e r a t i n gs y s t e m s d e s i g n a n di m p l e m e n t a t i o n ，由于该书以t a n e n b a u m 自己写的m i n i x 系统为例，所 以l i n u s 就将m i n i x 文件系统改写后用于l i n u x ，但这个文件系统有几个主要的缺 陷】： 1 磁盘分区必须小于6 4 m b 。 2 必须使用1 4 个字符定长的文件名。 华中科技大学硕士学位论文 3 难于扩展。 在虚拟文件系统被加入内核后，1 9 9 2 年4 月，第一个专门为l i n u x 所写的文 件系统e x t ( 扩充文件系统) 被加入了0 9 6 c 版本。e x t 使m i n i x 的缺陷得以改进， 一是它最大可支持2 g b 的磁盘分区，二是其文件名最长可达2 5 5 个字符。但它仍 有自己的缺陷：它使用链表管理未分配的数据块和节点，这样当文件系统投入使 用后，链表变得杂乱无序，文件系统中会产生很多碎片。 1 9 9 3 年，r e m yc a r d 对e x t 做出了改进，写成了e x t 2 。e x t 2 有如下几个方面 的特点： 1 用变长的目录项，这样既可以不浪费磁盘空间，又能支持最长2 5 5 个字符 的文件名。 2 用位图( b i t m a p ) 来管理数据块和节点的使用情况，解决了e x t 出现的问 题。 3 易于扩展。 节点中使用了1 5 个数据块指针，这样最大可支持4 t b 的磁盘分区 最重要的点，在磁盘上的布局做了改进，即使用了块组的概念，从而使数据的 读和写更快、更有效，也是系统变得更安全可靠。 e x t 2 是为l i n u x 设计的一个可扩展的高性能文件系统，它是目前为止l i n u x 中最 成功的文件系统，也是当前l i n u x 文件系统的基础。 1 1 3 2 适用于服务器的l i n u x 日志文件系统 e x t 2 的设计者主要考虑的是文件系统性能方面的问题。e x t 2 在写入文件内容 的同时并没有同时写入文件的元数据( 和文件有关的信息，例如：权限、所有者 以及创建和访问时间) 。换句话说，l i n u x 先写入文件的内容，然后等到有空的时 候才写入文件的元数据。这样若出现写入文件内容之后但在写入文件的m e t a - d a t a 之前系统突然断电，就可能造成在文件系统就会处于不一致的状态。当系统重新 启动f s c k 开始扫描时，它会检测到这些没有彻底卸载的文件系统，并做出合理 的假设一文件系统可能没有为l i n u x 文件系统驱动程序准备好。这就很有可能 导致元数据在某种情况下陷入困境。所以，为了弥补这种情况，f s c k 将开始彻 底的扫描并且全面地检查元数据，修正这一过程中找到的任何错误。迄今为止， 为确保文件系统的一致性，这种方法可能听起来并不是个坏主意，但是却不是最 佳的解决方案。问题出自于这样一个事实一f s c k 必须扫描文件系统全部的元数 据，以确保文件系统的一致性。对所有的元数据做彻底的一致性检查是一项极为 华中科技大学硕士学位论文 费时的工作。通常至少要花上好几分钟才能完成。更糟糕的是，文件系统越大， 完成这个彻底的扫描所花费的时间就越长。这就是个大问题，因为当f s c k 做它 自己事情的时候，l i n u x 系统实际上就是被切断的，并且如果你有一个庞大数量 的文件系统存储( 包含数1 0 亿个文件) ，f s c k 可能要运行1 0 个小时以上。在任务 紧要的数据中心的环境里，也就是在系统正常运行极为重要的环境下，标准的 f s c k 工作可能会造成破坏性的结果i6 - 8 。 幸运的是，有更好的解决方案，这就是新的目志式文件系统。日志文件系统 比传统的文件系统安全，因为它用独立的日志文件跟踪磁盘内容的变化。就像关 系型数据库( r d b m s ) ，日志文件系统可以用事务处理的方式，提交或撤消文件 系统的变化。 日志式文件系统在强调数据完整性的企业级服务器中有着重要的需求，是文 件系统发展的方向。日志式文件系统的思想来自于如o r a c l e 等大型数据库。数据 库操作往往是由多个相关的、相互依赖的子操作组成，任何一个子操作的失败都 意味着整个操作的无效性，对数据库数据的任何修改都要回复到操作以前的状态。 日志式文件系统采用了类似的技术。在分区中保存有个日志记录文件，文件系 统写操作首先是对记录文件进行操作，若整个写操作由于某种原因( 如系统掉电) 而中断，则在下次系统启动时就会读日志记录文件的内容来恢复没有完成的写操 作。而这个过程一般只需要几秒钟到几分钟，而不是e x t 2 文件系统的f s c k 那样在 大型服务器情况下可能需要几个小时来完成扫描。这种技术允许撤消对文件系统 做的改变( 只要把日志中的数据覆盖) ，或者在发生崩溃时恢复数据( 只要把镜像拷 贝到文件系统中) 。日志文件系统提供了更好的性能表现( 数据是并行地写入进日 志，然后再逐步写入文件系统) ，和更好的崩溃恢复性能【6 ，乳“l 。 l i n u x 系统缺少日志式文件系统是限制推广其在企业级应用的一个重要制约 因素。因此就出现了多种不同的日志式文件系统，目前有很多项目使用“目志文件 系统”的技术，开发新的文件系统准备取代广泛使用的e x t 2 文件系统。由于其中 一些项目进展迅速，从理论进入了可用阶段，比如s g i 公司的x f s 文件系统 1 2 0 3 】 的文件系统和卷管理( v o l u m em a n a g e r ) ，c e d a 【1 4 】文件系统，g f s 1 5 。 】文件系统以 及e x t 3 文件系统。它们虽然有不同的特点和开发方式，但都使用了“日志文件系 统”的技术，并且都可能成为e x t 2 文件系统的继任者。 s o l 公司的开放源代码产品x f s 文件系统在开发者社区中引起过很多关注。 x f s 文件系统已经在s o l 公司自己的操作系统i r i x 上稳定使用了很多年，它是 一个完全6 4 位的日志文件系统，开放源代码的x f s 已经移植到了l i n u x 上来， 华中科技大学硕士学位论文 其测试版本已经推出，同时也处于快速的开发中。 e x t 3 文件系统正在l i n u x 内核黑客的领导下开发，目标是提供e x t 2 文件系 统的一个更新版本。通过在原有e x t 2 系统的元数据块上增加日志信息，声称要保 持与e x t 2 系统的向前和向后兼容性。这个文件系统也许称为e x t 2 的下一个版本 更为合适些。而且e x t 3 还支持异步的日志。 以上几种文件系统都比当前使用的e x t 2 文件系统具有更好的性能，也各具特 色，他们将在未来的时间里继续竞争，以取代l i n u x 操作系统中使用多年的e x t 2 文件系统。 1 4 本文主要内容 本文着眼于文件系统的底层布局结构，在分析l i n u x 现有文件系统e x t 2 在处 理大型文件时的局限性的基础上，提出了一种基于连续块的b + 树文件结构，性能 测试表明，改进后的新系统在处理速度和性能等方面都有了较大的提高。 本文第二章介绍了e x t 2 文件系统的布局结构和工作原理。第三章和第四章是 本文的主体部分。在第三章中，从空闲块管理、文件结构和目录结构三方面对e x t 2 分析，并提出解决方案和新的设计思想，架构出一种基于连续块的b + 树文件系统 e b f s ( e x t e n t b a s e da n d b + t r e ef i l es y s t e m ) 的整体模型。在第四章对e b f s 的三 个主要模块的具体实现进行了描述，主要是数据结构和基本操作的算法介绍。第 五章分别从文件内部数据访问的性能和对文件集中文件操作的性能两方面对 e b f s ，e x t 2 进行了系统测试和分析比较。 华中科技大学硕士学位论文 2l i n u x 的文件系统分析 分析源代码是学习操作系统最直接有效的方法。在课题研究过程中，笔者对 l i n u x 2 4 8 文件系统部分的大量源代码( 约8 万行) 进行了仔细的阅读和分析，不 仅对l i n u x 文件系统的关键技术有了比较透彻的了解，同时也掌握了一些写源代码 的基本技巧和规范，为e b f s 文件系统的实现和编写奠定了基础。 本章首先阐述虚拟文件系统( v i r t u a lf i l es y s t e m ) 1 拘i 作原理，了解v f s 是如何 支持和管理不同的真实文件系统，并为上层用户提供透明接口的；然后对l i n u x 内核的一个真实文件系统e x t 2 文件系统具体分析，e x t 2 是目前l i n u x 版本中应用最 广泛的主流文件系统，也是本课题研究和改进的基础。 2 1 虚拟文件系统 2 1 1 概述 作为一个最著名的自由软件，l i n u x 确实名不虚传，几乎处处体现了“自由”， 你可以定制裁剪适合自己系统要求的内核，或者轻松添加别人开发的新模块，还 可以自己写一个新的l i n u x 支持的文件系统，例如本文要实现e b f s 文件系统。 l i n u x 的一个最重要特点就是它支持许多不同的文件系统( 女1 e x t 2 ，v f a t m s d o s ，h p f s ，u f s ) ，而且还支持这些文件系统相互之间进行访问。要实现这个 目的，就要将对各种不同文件系统的操作和管理纳入到一个统一的框架中。让内 核中的文件系统界面称为一条文件系统“总线”，使得用户程序可以通过同一个文 件系统操作界面，也就是同一组系统调用，对不同的文件系统( 以及文件) 进行 操作。这样，就可以对用户程序隐去各种不同文件系统的实现细节，为用户程序 提供一个统一的、虚拟的文件系统界面，这就是所谓的虚拟文件系统。这个抽象 的界面主要由一组标准的、抽象的文件操作构成，以系统调用的形式提供给用户 程序，立【l r e a d o ，w r i t e ( ) ，i s e e k 0 等等。v f s 与具体文件系统的关系如图2 1 所示。严格 来说，v f s 并不是一种实际的文件系统，它只存在于内存中，不存在于任何外存 空间。v f s 在系统启动时建立，在系统关闭时消亡【1 8 】。 v f s 的功能包括【”。2 1 】： 1 对逻辑文件系统的数据结构进行抽象，以一种统一的数据结构进行管理。 2 将设备同对应的文件系统联系起来。 3 处理一些面向文件的通用操作。 华中科技大学硕士学位论文 4 涉及到针对文件系统的操作时，v f s 把它们映射到与控制文件、目录以及 节点相关的物理文件系统。 用户空间 系统 匝匹耍互蟹翻 fj f f - _ i 文件系统操作的系统调 用界面r e a d 0 ，w r i t e 0 o p e n 0 c l o s e 0 等 w r i t 等等 通过f i l e 结构中的f o p 指针 实现的“文件系统总线“ 图2 1v f s 与具体文件系统的关系示意图 当某个进程发布了一个面向文件的系统调用时，内核将调用v f s 中相应的函 数，这个函数处理一些与物理结构无关的操作，并且把它重新定向为真实文件系 统中相应的函数调用，后者则用来处理那些与物理结构相关的操作。 超级块和i n o d e 节点是文件系统中最重要的数据结构，在2 2 节中，将以e x t 2 文件系统为例，具体介绍它们的结构和用途。这里主要强调一点，文件系统( 如 e x t 2 ) 中的超级块和索引节点是存储在磁盘上的静态结构。要使用它，必须调入 内存。文件系统的超级块在向v f s 注册时填充到对应的v f s 超级块中。而文件 系统的索引节点则是在其标识的文件对象被系统进程访问时被调入内存，填充到 相应的v f s 节点中。 每当包含文件系统的块设备被装配时( 包括根文件系统) ，v f s 都会读入它的超 级块。每种类型文件系统的超级块读例程( r e a ds u p e r ) 必须要识别出该文件系统 的拓扑结构，并把这些信息映射到一个v f s 超级块数据结构中。v f s 文件系统包 含了系统中所有装配文件系统的列表和它们的vfs 超级块信息。每个v f s 超级块 对应一个装配的文件系统的相关信息，包含文件系统类型，指向该文件系统超级 块操作的函数集合的指针和指向该文件系统的第一个i n o d e 节点的指针。通过这些 信息，v f s 就可以将用户请求和实际文件系统连接起来了。 在系统进程访问目录和文件时，系统会调用搜索系统中v f s 节点的进程。例 如，对一个目录敲i s 命令或对文件使用c a t 命令都会使v f s 文件系统搜索代表其所 华中科技大学硕士学位论文 在文件系统的v f si n o d e 节点组。v f s 节点中包括指向索引节点操作例程集的指针 和文件的描述信息。 由于系统中的每个文件和目录都是由一个v f s i n o d e 节点表示的所以有一些 i n o d e 节点会被经常访问。这些经常被访问的i n o d e 节点记录在缓存中以加速访问过 程。如果要访问的i n o d e 节点不在i n o d e 缓存中，那么系统会调用文件系统的专门例 程来读入相应的i n o d e 节点。读入i n o d e 节点的操作会使得它被加入至u i n o d e 缓存中， 而对该i n o d e 节点的后续访问使得它被保存在i n o d e 缓存中。那些访问频率较低的 v f si n o d e 节点会被从i n o d e 缓存中删除掉。 2 1 2 文件系统的注册、安装和卸载 1 文件系统的注册 在内核被编译时，可以选择支持的文件系统。这些文件系统在系统引导时， 在v f s 中进行注册。如果文件系统是作为内核的可载入模块，则在实际安装时注 册，并在模块卸载时注销。注册函数内嵌在文件系统的初始化例程中，作用就是 在v f s q h 进行注册，并填写一个叫做f i l e _ s y s t e m _ t y p e 的数据结构。 f i l e _ s y s t e m _ t y p ef i l e _ s y s t e m _ t y p ef i l e s y s t e m _ t y p e ：竺垫塑2ih ：唑咧! i ，- i ：翌坚型! i b 箸dqb 器刮p r o c ib 箸d m s d o s l n e x tl “| n e x tl _ j l n e x t i 图2 2 已注册文件系统链表 每个f i l e 数据结构包含下列信息：s y s t e m 指寝趣级块读_ t 钢y p 程e ( r e a d _ s u p e r ) 的指牝当藏于该文件系统类垫的实穰被装配对由 v f s 文件系统调用该锄程读取超级块。 文件系统名：文件系统的名称：s z # e x t 2 ， 所器设备：这个文件系统是否需要设备支持 并不是所有的文件系统都噩有保存它们的 设备。如 p r o c 文件系统不要末有支持它的块设备，如需要鼬该位为l ? 否则为o ， 每个f i l e _ s y s t e m _ t y p e 结构代表一种已经注册的文件系统，这些节点组成一条 f i l e s y s t e m _ t y p e 单向链表，表头【= h f i l e s y s t e m s 指定。如图2 2 所示。注册函数为i n t r e g i s t e r _ f i l e s y s t e m ( s t r u c tf i l e s y s t e m _ t y p e + f s ) 其执行过程就是遍历这个单向链表，如果找到对应的节点，说明已经注册， 退出。否则，将该结构挂在链尾。 1 0 华中科技大学硕士学位论文 2 文件系统的安装 要使用一个文件系统，仅仅注册是不行的，还必须安装这个文件系统。在安 装l i n u x 时，硬盘上已经有一个分区安装了e x t 2 文件系统，它被用来作为根文件系 统，根文件系统在启动时自动安装。其实在启动后看到的文件系统，都是在启动 时安装的。而如果你需要自己安装文件系统，则需要指定三种信息：文件系统的 名称、包含文件系统的物理块设备、新文件系统在当前文件系统拓扑结构中的安 装点。 例如：$ m o u n t ti s 0 9 6 6 0 d e v h d c m n t c d r o m 其中，i s 0 9 6 6 0 就是文件系统的名称，d e v h d c 时包含文件系统的物理块设备， m n t c d r o m 就是将要安装到的目录，即安装点。 虚拟文件系统对上述命令的执行过程如下： s t e pl i 寻找对瘦的文件系统信息。v f s 黝f i l e _ s y s t e m s 在e 注勰文件系统链表 中查找含确1 s 0 9 6 6 8 类型名鼢1 t e j y s t m t y p e 节点从而我勤该类文件 系统的超级块读取钠程的入口， s t e p2 i 如果在上述链表串找韵匹配的文件系统鼬说鞠魂核支持该文佟系统 番鼬说明该文件系统司能由司装载模块支持。v f s 会请求内核装入相直的文件系 统模块院时该文件系统在v f s 中注册并视始化， s t e p3 l 不管是哪种情况? 如v f s 无法找虱指定的文擘 系统鼬返回错误。 s t e p4 ：v f s 检验给定的物理块设备是否e 经安装。如果指定的抉设备b 被安装， 鼬返回错误，释一个块设备r 能安装勤一个巨录t 不能多次安装。 s t e ps ：v f s 奁找作为新文件系统安装点的g 录的v f s 索昏节点。珐- v f s 索引节点 司能在索；l 节点高速缓存中也由司能需妥扶安装点所在的块设备中读 取。趣果该安装点b 经安装其健文件系统则返回错误。因为国一g 录 r 能强霹安装个文件系统， s t e p6 i 所表检查通过后m o m 吣才转a 正式的安装i 作，v f s 安装代码为额的文件系统 分配v f s 超级块系统中斫舂的y f s 超级块保存在在s u p e rb l o c k s 皆t $ j t f j s u p e r b l o c k 数据结构指针数组中， s t e p7 ：调再该类文件系统的超级块读取仍程。将对应文件系统的信息映艇哼v f s 超级块 印。 s t e p8 ：申请一个峪m o u n t 结c l j ，填充正确内容后挂勤e 安装文件系统链表中， s t e p9 ：如战功安装戳所舂b 安装的文件系统形成如图2 3 所示的结构 从图中可以看出，每个已安装的文件系统由一个v f s m o u n t 结构描述，所有的 华中科技大学硕士学位论文 v f s m o u n t 结构形成一个练表，用v f s m n t l i s t 来指向链表头，这个链表称为己安装文 件系统链表。系统中还有另外两个指向这种结构体的指针，v f s m n t t a i l 和 m r uv f s m n t ，分别指向链表尾和最近使用过的v f s m o u n t 结构。每个v f s m o u n t 结构包 含该文件系统所在的块设备号和设备名( r a n td e v ，r a n td e v n a m e ) 、文件系统安 装点的目录名称( m n td i r n a m e ) ，以及指向为该文件系统分配的v f s 超级块的指针 ( s t r u c ts u p e r b l o c k + m n t _ s b ) 。而v f s 超级块中则包含描述文件系统的 f i l e s y s t e m _ t y p e 结构的指针( s t r u c t f i l e s y s t e m _ t y p e + s _ t y p e ) ，文件系统安装目录的 节点指针( sc o v e r e d ) 和该文件系统根节点的指针r sm o u n t e d ) 。 超级块 图2 3 已安装文件结构示意图 下面三个函数使用来操作已安装文件系统链表的，它们都在f s s u p e r c 中实现。 s t r u c tv f s m o u n t + a d dv f s m n t ( k d e v _ td e g c o n s t c h a r + d e v _ n a m e c o h s rc h a r + t i l t _ n a m e ) 在链表尾加入一个v f s m n t 结构，返回指向该结构的指针。 s t r u c tv f s m o u n t + l o o k u pv f s m n t ( k d e vt 幽v j 从链表中寻找指定设备号的v f s m n t 结构，成功则返回指向该结构的指针，否 则返回0 。 v o i d r e m o v e _ v f s m n t ( k d e v td e v ) 从链表中移走指定设备号的v f s m n t 结构，并释放其所占的内核内存空间。无 返回值。 3 文件系统的卸载 如果系统的某些进程正在使用该文件系统的某个文件的话，该文件系统不能 卸载。例如当系统的某个进程正在使用m n t c d r o m 目录或它的子目录的话，就无 法卸载装配在m n “c dr o m n 录上的文件系统。如果文件系统中的文件或目录正在 华中科技大学硕士学位论文 使用，在v f si n o d e 节点的缓存中就会有来自该文件系统的v f s i n o d e 节点。检查 程序通过在i n o