(译)Design and Implementation of the Second Extended Filesystem(1)

Introduction

Linux类似Unix操作系统,运行于PC-386机器上。最初在Minix操作系统上扩展实现,当时最初的版本仅支持Minix文件系统。Minix文件系统包含两个致命的限制:块地址以16位integers存储,所以最大文件系统的大小受限于64兆;同时,目录包含固定大小的入口,最大文件名只可包含14个字符。

我们设计实现两类新的文件系统使其包含于标准Linux内核,它们称为“Extended File System” (Ext fs) and “Second Extended File System” (Ext2 fs),提供新的特性与限制。

本文将描述Linux文件系统的历史,简单介绍实现Unix文件系统的基础概念,提出Linux中VFS的实现原理,且详细介绍Second Extended File System内核代码和用户模式工具。

History of Linux filesystems

早些年代,Linux是在Minix操作系统下交叉开发的。在两个系统间共享磁盘比设计一个新的文件系统简单多了,所以Linus Torvalds决定在Linux上实现对Minix文件系统的支持。Minix文件系统确实是有效且相对无缺陷的一类软件。

但是,Minix文件系统设计中的限制太过于局限,所以人们开始思考在Linux上实现新的文件系统。

为了使新的文件系统加入Linux内核更加简单方便,虚拟文件系统层诞生了。VFS层最初由Chris Provenzano实现,之后在被集成到Linux内核前由Linus Torvalds改写。

在VFS集成到内核后,一个新的文件系统“Extended File System”在1992年4月被实现并添加进Linux 0.96c。它解决了Minux的两大局限:最大大小为2G且最大文件名长度为255个字符。这在当时是一个很大的进步,但是有些问题仍旧存在。对于独立访问,inode的修改和数据修改的时间戳并没有支持。这个文件系统使用链表来记录空闲的块和inode,这带来了较差的性能:当使用过该文件系统后,这些链表变得无序所以文件系统将存在各种碎片。

两种新的文件系统的Alpha版本在1993年一月的发布回应了这些问题:Xia文件系统和Second Extended File System。Xia文件系统很大程度上依赖于Minix文件系统内核代码,且只在此基础上增加了一些改进。基本上,它提供了长文件名,支持更大的分区和三类时间戳。另一方面,Ext2fs在Extfs代码的基础上做了很多改编和很大的改进。它设计遵循进化并具有未来发展的空间。

当这两种文件系统发布时,它们提供了本质上相同的特性。由于Xia的最小设计,Xiafs比Ext2fs更稳定。当文件系统更广泛的被使用,Ext2fs中的bugs被修复,很多改进和新的特性被集成其中。Ext2fs如今非常稳定,将要正式成为标准的Linux文件系统。

这张表总结了不同文件系统所提供的特性:

Minix FS Ext FS Ext2 FS Xia FS
Max FS size 64 MB 2 GB 4 TB 2 GB
Max file size 64 MB 2 GB 2 GB 64 MB
Max file name 16/30 c 255 c 255 c 248 c
3 times support No No Yes Yes
Extensible No No Yes No
Var. block size No No Yes No
Maintained Yes No Yes ?

Basic File System Concepts

每一种Linux文件系统都实现了一组从Unix操作系统文件中衍生出来的基本概念,比如inodes,比如目录就是简单的包含一系列入口的文件,设备可以通过请求IO来访问这些特殊的文件。

Inodes

每个文件都可以用一种结构来描述,称作inode。每个inodel包含文件的属性信息:文件类型,访问权限,文件拥有者,时间戳,大小,指向数据块的指针。分配给文件的数据块的地址存储于该文件的inode。当用户请求该文件的IO操作时,内核代码将当前的偏移量改变成一个块的号码,使用这个号码作为块地址表中的一个索引来读写物理块。下图显示了一个inode的结构:

Directories

目录是一种分层树结构。每个目录都包含文件和子目录。

目录是一种特殊类型的文件。实际上,一个目录就是一个文件包含一系列入口,每个入口包含一个inode号和一个文件名。当一个进程使用一个路径名时,内核代码在目录中查询对应的inode号。当文件名转换为inode号,inode被载入内存并且用于后续的请求。

该图呈现了目录:

Links

Unix文件系统实现了link的概念。若干个名字可以关联于同一个inode。Inode包含一个域来记录和文件关联的号。添加一个连接只是简单的新建一个目录入口,inode号指向inode,且将inode连接数加1。当一个连接被删除时,例如,有用户使用rm命令来删除文件,内核只是减少了连接数,当连接数为0时才释放该inode。

这种类型的连接叫做硬连接,只能用于单一的文件系统:不能创建跨文件系统(跨分区)的硬连接。而且,硬连接只能指向文件:不能创建目录的硬连接来避免目录树中的幻影周期(apparition of a cycle)。

另一种连接存在于大多数的Unix文件系统中。符号连接只是简单的包含文件名的文件。当路径名到inode的转化过程中,内核如果遇到符号链接,它会用例如目标文件的名字来替换连接的名字,并重新开始路径名的解析。因为符号链接并不指向一个inode,所以它可以创建跨文件系统的符号连接。符号链接可以指向任何类型的文件,即使是不存在的文件。符号链接非常有用,它们相比于硬连接有较少的限制。但是,它们使用硬盘空间,分配给它们的inode和它们的数据块,导致路径名到inode转换时的开销,因为内核遇到符号连接时需要重新解析文件名。

Device special files

在类似Unix的操作系统中,设备可以通过特殊文件来访问。设备特殊文件在文件系统中不占用任何空间。只是一个指向设备驱动器的访问指针。

有两种特殊类型的文件存在:字符和块特殊文件。字符特殊文件允许以字符模式进行IO操作,块特殊文件需要通过高速缓存缓冲区函数将数据写入块。当IO请求于一个特殊文件时,它将转换到一个伪设备驱动器。一个特殊文件被一个主设备号和一个次设备号引用,一个用于识别设备类型,一个用于识别单元。

The Virtual File System

Principle

Linux内核包含一个虚拟文件系统层,当系统对文件调用操作时使用。VFS只是当物理文件系统代码处理IO时用于处理面向文件的系统调用和调用必须的函数时的一个间接层。

这个间接的机制通常在Unix类似的操作系统中使用来便于集成和同时使用多个文件系统。

当进程处理一个面向文件的系统调用时,内核调用VFS中的函数。这个函数解决结构独立的处理操作和重定向在物理文件系统代码中的调用函数,而这个函数用于负责处理结构独立的操作。文件系统代码使用缓冲区高速缓存功能处理设备IO请求。机制描述如下图:

The VFS structure

VFS定义了一套函数,每个文件系统都需要来实现。这个接口由相关联的三类对象:文件系统、inode和打开的文件的一套操作组合而成。

VFS知道内核支持的文件系统类型。VFS在内核配置中定义一个表。该表中每个入口都描述一类文件系统:它包含文件系统类型的名字和mount操作调用时的函数指针。当文件系统被加载时,适当的mount函数被调用。这个函数负责读取磁盘的超级块,初始化内部变量,返回一个加载的文件系统的描述符给VFS。当文件系统被加载后,VFS函数使用这个描述符来访问物理文件系统。

一个加载文件系统的描述符包含几类数据:所有文件系统类型通用的信息、物理文件系统内核代码提供的函数指针和物理文件系统代码维护的私有数据。包含在文件系统描述符中的函数指针允许VFS访问文件系统内部。

VFS使用的其他两类描述符:inode描述符和打开文件描述符。每个描述符包含和使用文件相关的信息以及物理文件系统提供的一套操作。当inode描述符包含可以处理所有文件函数的指针(例如,create,unlink),而文件描述符只包含可以处理打开的文件操作的函数指针(例如,read,write)。

The Second Extended File System

Motivations

Second Extended File System设计和实现来处理一些存在于first Extended File System的问题。我们的目的是提供一个功能强大的文件系统,能够实现Unix的文件语义和提供高级特性。

当然,我们希望Ext2fs拥有杰出的性能。我们也希望能够提供一个强健的文件系统来减少数据在密集使用时丢失的危险。最后,Ext2fs至少能够提供扩展允许用户受益于新特性而不必重新格式化文件系统。

“Standard” Ext2fs features

Ext2fs支持标准Unix文件类型:普通文件,目录,设备特殊文件和符号连接。

Ext2fs能够管理在大分区上创建的文件系统。当原始的内核代码严格限制最大文件系统大小为2GB,最近再VFS层将这个限制提高到了4TB。所以,现在可以使用大磁盘而不需要创建很多分区。

Ext2fs提供长文件名。它使用可变长度的目录入口。最大文件名长度为255个字符,这个限制可以应需扩展到1012。

Ext2fs为超级用户(root)保留一部分块。通常是5%的块被保留。这方便让管理员在文件系统被用户进程填满的情况中恢复过来。

“Advanced” Ext2fs features

除了标准Unix的特性,Ext2fs还支持一些Unix文件系统中不常出现的扩展。

文件属性允许用户在操作一些文件时修改内核行为。用户可以为文件或者目录设置属性。在目录中建立新的文件将继承这个目录的属性。

BSD或者系统VRelease4 semantics在载入时可以选择,载入选项允许管理员选择文件创建语义。当文件系统使用BSD载入时,创建的文件拥有和其上层目录相同的组号。System V语义就有些复杂:如果目录有setgid位设置,新的文件继承目录的组号,子目录也继承组号和setgid位;否则,文件和子目录都选择创建时调用进程的主组号。

BSD类似的同步更新可以在Ext2fs中使用。载入选项允许管理员请求元数据(inodes, bitmap blocks, indirect blocks and directory blocks)被修改时同步写入磁盘。这有利于保持严格的元数据一致性,但是导致了糟糕的性能。实际上,这个特性一般不需要,因为除了带来性能的损失外,它也会造成用户数据的损害而文件系统并不能检查到。

Ext2fs允许管理员选择文件系统的逻辑块的大小。块大小可以是1024、2048和4096字节。选择大的块大小可以提高IO速度,因为它会减少IO请求,减少访问一个文件所需要的磁头寻道。另一方面,大块却会浪费较多的磁盘空间。平均来说,最后分配给文件的那个块只占用了一半,所以当块更大,更多的空间会被浪费。

Ext2fs实现了快速符号连接,它不使用任何文件系统中的数据块。目标名存储在inode中而非数据块。这种策略可以节省一些磁盘空间(没有数据块需要分配),提高连接操作(访问连接不需要读取数据块)。当然,inode中的可用空间也是有限的,所以不是所有的连接都可以以快速符号连接的方式实现。快速符号连接中目标名的最大大小为60个字符。我们在最近计划对小文件扩展这个模式。

Ext2fs跟踪文件系统的状态。超级块中有个特殊的域被内核代码用来预测文件系统的状态。当文件系统加载成可读写模式事,它的状态被设置成“Not Clean”。当被卸载或者重新加载成可读模式时,它的状态被设置成“Clean”。在启动时,文件系统校验器通过该信息决定文件系统是否需要校验。内核代码也在该域中记录错误信息、当不一致被检测到时,文件系统被标记为“Erroneous”。文件系统校验器就会强制对文件系统进行检查,不管它是否显示是clean状态。

经常跳过文件系统的检查有些时候会很危险,Ext2fs提供两种方式来进行定期的强制检查。在超级块中保留一个加载计数器。每次文件系统加载成可读写模式时,这个计数器自动加一。当它达到最大值时,文件系统校验器就会强制检查整个文件系统,不管它是否是clean状态。最后校验时间和最大校验周期也保留在超级块中。这两个域允许管理员请求定期检查。当最大检查周期达到时,校验器不管文件系统的状态就会强制检查。Ext2fs提供工具来协调文件系统的行为。Tune2fs程序可用于修改:

-错误行为。当检测到不一致性时,文件系统标记为“Erroneous”并且可执行以下三个操作中的一个:继续正常执行,重载文件系统为只读模式避免破坏整个文件系统,造成内核崩溃并重启文件系统校验。

-最大加载计数

-最大校验周期

-为超级用户保留的逻辑块数

加载选项也可用于改变内核错误行为。

某属性允许用户请求安全删除文件,当该文件被删除后,随机数据被写入实现分配给文件的磁盘块。这防止恶意用户通过磁盘编辑器获取文件之前的内容。

最后,受4.4BSD文件系统的启发,新的文件类型最近被添加进Ext2fs。不可变文件只能用于读,任何人都不能写和删除它们。这可用于保护敏感的配置文件。只可追加的文件可以以可写模式打开但是数据都被追加在文件的尾部。和不可变文件一样,它们不能被删除和重命名。这通常用于日志文件。

Physical Structure

Ext2fs的物理结构很大程度上受BSD文件系统的影响。文件系统是由块组组成。块组类似于BSD的FFS柱面组。但是这个块组并不绑定于磁盘块上的物理层,现代驱动器对顺序访问有了优化且可以对操作系统隐藏它们的物理结构。

文件系统的物理结构:

Boot
Sector
Block
Group 1
Block
Group 2

Block
Group N

每个块组包含一个关键文件系统控制信息的冗余副本(超级块和文件系统描述符),也包含一部分文件系统(为图块,位图inode,一组inode表,数据块)。块组的物理结构:

Super
Block
FS
descriptors
Block
Bitmap
Inode
Bitmap
Inode
Table
Data
Blocks

使用块组在可靠性上是一个很大的成功:由于控制结构被备份到每个块组,所以当超级块损坏时可以很简单的恢复文件系统。这个结构也带来了很好的性能:减少inode表和数据块的距离,减少了文件IO的磁头需找时间。

在Ext2fs中,目录是一组可变长入口的链表结构。每个入口包括inode号,入口长度,文件名和它的长度。通过使用可变长入口,在目录中实现了不浪费磁盘空间而实现长文件名。目录入口的物理结构:

inode number entry length name length filename

举例,包含三个文件的目录:file1, long_file_name, and f2:

i1 16 05 file1

 

i2 40 14 long_file_name

 

i3 12 02 f2

Leave a Reply

Your email address will not be published. Required fields are marked *