开篇将带你们回到1974年,
有时,进步无法察觉,非常是当你正身处其中时。而对比新旧资料之间的差别,找寻这些推进改革的信息源,我们就可以清晰地看见进步的发生。在Linux(以及大部份Unix系统)中,都可以印证这一点。
UnixV7是Unix操作系统的一个重要的初期版本,于1979年发布,是贝尔实验室最后一个广泛分发的版本。它是第一个真正可移植的Unix版本,被移植到了多种平台上,包括DECPDP-11,VAX,x86,Motorola68000等。UnixV7的VAX移植版本,称作UNIX/32V,是流行的4BSD系列Unix系统的直接先祖。许多老牌的Unix用户觉得UnixV7是Unix发展的顶峰。
UnixV7ResearchRelease的源代码可以在unix-history-repo^[3]^这个由DiomidisSpinellis维护的项目中找到。假如你想深入了解Unix的设计原理,可以参考MauriceJ.Bach的精典专著TheDesignoftheUnixOperatingSystem^[4]^,并查看ResearchV7Snapshot^[5]^这个分支的代码库。
KenThompson(坐着的)和DennisRitchie在大型计算机PDP-11上工作,她们是贝尔实验室(BellLabs)的研究员,在20世纪70年代初期开发了Unix操作系统及其文件系统。
Machines
1974年,计算机拥有一个“核心”,即中央处理单元。但是,在个别计算机中,这个“核心”已经发生了变化。不再是由多个部件(如算术逻辑单元、寄存器、顺序控制器和微码储存器)组成的设备,而是一颗单一的集成芯片linux伊甸园,单个芯片上集成了数千个晶体管。它们被称作“小型计算机”。
Kernels
在Unix中,我们通过配置头文件(headerfile)来处理系统资源。如右图所示,这儿显示了头文件中配置的默认值^[6]^,数据结构是链表,所示值是相应的字段大小。假如要修改它们,则须要编辑文件,重新编译和链接内核,之后重新启动系统。
它有一个文件系统缓冲区缓存(filesystembuffercache),使用NBUF(29)个c盘块,每位c盘块的大小是512字节,拿来暂时储存c盘上的数据块和inode,因而加速文件系统访问。另外还有一个索引节点链表(inodearray),它有NINODE(200)个条目,每位条目对应一个文件的元数据,还可以同时挂载NMOUNT(8)个文件系统。每位用户最多可以运行MAXUPRC(25)个进程,总共有NPROC(150)个系统进程。每位进程最多可以打开NOFILE(20)个文件。
阅读Bach的专著和V7源代码是很有趣的,虽然它们已然完全过时。由于这种源代码中呈现出的许多核心概念愈发清晰,结构更简约,有时甚至带有古老的风格。但是,正是这种概念定义了Unix文件系统。V7Unix被写入了POSIX标准红旗linux操作系统,然后的每位文件系统都必须遵循它。假如您想了解更多相关示例,请参考ButIsItAtomic?^[8]^
核心概念
Unix文件系统的基本概念和结构来自这个系统。其中一些概念甚在现代系统中仍然存在。
c盘由一系列数据块(block)组成,从第0块开始,仍然到第n块结束。在文件系统的开始部份,我们可以找到超级块(superblock)。它坐落文件系统的第1块。超级块储存了文件系统的一些基本信息,例如文件系统的大小、空闲块的数目、空闲索引节点的数目等。当我们执行挂载(mount)系统调用时,系统会找到一个空闲的挂载结构(mountstructure^[8]^),但是从c盘上读取超级块,把它作为挂载结构的一部份。
Inode
显存中的超级块(in-memorysuperblock)是c盘上超级块的副本,用于推进文件系统的访问速率。它包含一个short类型的数组,用于储存一个索引节点链表(inodearray)在c盘上的位置。
索引节点(inode^[9]^)是一个描述文件内容和属性的结构,文件内容由一系列数据块(block)组成,每位数据块的大小是固定的(一般是512字节或1024字节),文件属性包含文件名、大小、权限、时间戳等元数据(metadata)。
c盘上的inode如上图所示。每位512字节的c盘块可以容纳8个inode,因而它们在64字节边界上对齐。
文件系统中的inode链表是一个short类型的计数器,它的最大值是65535,也就是说文件系统中最多只能有65535个inode。因为每位文件都须要一个inode,因而每位文件系统最多只能容纳65535个文件。
每位文件具有一些固定属性:
(2字节)mode,它包含了文件的类型和访问权限;
(2字节)nlink,它表示这个文件有多少个名子;
(2字节)uid,文件的所有者;
(2字节)gid,文件所有者的组ID;
(4字节)size,文件的宽度,以字节为单位(定义为off_t,长整型);
(40字节)addr链表,包含了文件的数据块在c盘上的地址;
(3x4字节)三个时间,atime(访问时间),mtime(更改时间)和ctime(所谓的创建时间,但实际上是最后一个inode修改的时间)。
总大小为64字节。
bmap()
Addr链表包含40个字节,但它储存了13个c盘块地址,每位地址使用3个字节。这对于24位来说十分适用,或则说对应于16个大小为512字节的兆块,总文件系统大小为8M千字节,即8GB。
中型计算机PDP-11RL02c盘驱动器的前面板(来自pdp-11.nl[10])
PDP-11RL0202Kc盘盒^[11]^可容纳10.4MB,而更新的RA92^[12]^可储存1.5GB。
Addr链表在bmap()^[13]^函数中被使用。该函数接收一个inode(ip)和一个逻辑块号bn,并返回一个数学块号。也就是说,它将文件中的一个块映射到c盘上的一个块,因而得名。
前10个块表针直接储存在inode中。诸如,要访问块0,bmap()将在inode中查找^[14]^di_addr[0]并返回该块号。
额外的块储存在一个间接块中,而间接块则储存在inode中。对于更大的文件,会分配一个双间接块,并指向更多的间接块,最终特别大的文件须要甚至三次间接块。
代码首先确定须要多少层间接轮询^[15]^,也就是要通过多少个间接块就能找到文件内容的c盘块。之后,获取相应的间接块^[16]^。最后,代码根据适当的次数解析间接轮询^[17]^,也就是按照层数依次从间接块中读取其他间接块或直接块的地址,直至找到文件内容的c盘块。
对于越来越大的文件,原始的Unix文件结构采用了逐步降低的间接访问次数。这样产生了一个压缩的链表,其中较短的文件可以直接通过inode中的数据进行访问,而较大的文件则须要通过越来越多的间接访问来获取数据。为了提升性能,保持间接块在文件系统缓冲区高速缓存中是至关重要的。
这些扩充性取决于块大小(初期为512字节,如今为4096字节)和块号的字节大小(最初为3字节unix 系统目录,后来为4字节甚至8字节)。
Atomicwrites
文件的写入是在加锁的状态下进行的,因而它们仍然具有原子性。虽然是跨越多个数据块的写入操作,也是这么。这一点在ButIsItAtomic?^[18]^中有详尽讨论。
这也意味着即便有多个写入进程,在单个文件上,任何时刻只能有一个c盘写入操作处于活跃状态。这对数据库系统的开发者来说十分不便利。
Namingfiles
目录是一个具有特殊类型和固定记录结构^[19]^的文件。
一个目录条目包含一个inode号(一个无符号整数)和一个文件名,文件名的宽度最多可以达到14个字节。这促使一个c盘块可以容纳32个目录条目,而一个目录文件的直接块可以引用的10个c盘块可以容纳320个目录条目。
上层(lower)的文件系统中饱含了大量的文件。这种文件没有名称,只有编号。
下层(upper)的文件系统使用一种特殊类型的文件,具有简单的16字节记录结构,用于为文件分配最多14个字符的名称。一个特殊的函数namei()将文件名转换为inode号。
传递给namei()的路径名具有层次结构:它们可以包含/作为路径分隔符,并以�(NUL)作为中止符。路径名若以/开头,则遍历将从文件系统的根目录开始,产生绝对路径名;若不以/开头,则遍历将从u.u_cdir,即当前目录开始。
该函数挨个消耗路径名的各个组成部份,使用当前活动目录,并在该目录中线性搜索当前组件的名称。当找到最后一个路径名组件或在任何阶段找不到组件时,该函数结束。假如在路径中的任何目录的任何点上,我们没有x权限^[20]^,它也会结束。
该函数按次序挨个处理路径名的各个组成部份。它使用当前目录,并在该目录中线性搜索当前组成部份的名称。函数的结束条件有两种情况:一是找到了路径名的最后一个组成部份,二是在路径的任何目录中,出现了难以访问^[21]^的情况。
挂载点是特殊条目^[22]^,它会从当前节点和文件系统的目录条目切换到挂载文件系统的根inode。这促使Unix中的所有文件系统看上去像是一棵单一的树,假如要进行"硬碟更改"的操作,只需简单地切换到不同的目录。
最终,该函数将返回给定路径名的inode表针,按照须要和需求创建(或删掉)inode(和目录条目)。它是目录遍历和访问权限检测的集中点。
一些创新的看法以及限制
这个初期的Unix文件系统具有许多挺好的特点:
它将多个文件系统呈现为一个统一的树状结构;
文件是无结构的字节链表;
这种链表以可动态降低深度的动态字段的方式储存。它们内部使用一种逐步嵌套的间接块系统,其中链表的元素可以是指向其他链表或数据的表针,因而产生层次嵌套的结构。这促使c盘搜索的复杂度为O(1);
上层文件系统创建文件和下层的文件系统组织文件相互隔离,分工明晰。获取inode的惟一方法是路径名遍历,但是在此过程中一直检测权限;
文件名中只有极少的特殊字符,即/和�(空字符)。
但也有显著的限制:
文件只能有16M个块;
文件系统只能有特别有限的65535个inode。
还有一些令人厌恶的限制:
文件只能有一个正在写入的进程,这会造成并发性受限;
目录查找是线性扫描,因而对于小型目录(超过320个条目),速率显得十分慢;
没有强制文件锁定系统。但存在几种用于咨询式文件锁定的系统。
还有一些特殊情况:
在UnixV7系统中,没有delete()系统调用,而是unlink()系统调用,它可以删掉一个文件的名子,但是这些没有任何文件名和打开文件句柄的文件会被手动清除。这会造成一些不符合预期的结果,比如,只有当一个完全没有文件名的文件被完全关掉时,它占用的c盘空间才能被释放。许多Unix系统管理员都以前问过她们的c盘空间去哪了,当她们删掉了/var/log目录下的日志文件,却忘掉了有一些进程还在使用它;
最初没有mkdir()和rmdir()系统调用,这造成了存在可被借助的竞态条件。竞态条件是指在多线程或多进程环境中,因为操作的次序和时机不确定性,可能造成安全漏洞或错误行为的情况。这在Unix的后续版本中得到了修补;
有一些操作在特定条件下具有原子性(比如write(2)系统调用),或则经过更改后具有原子性(mknod(2)和mkdir(2))。
在结构上,inode表和块和inode的空闲映射坐落文件系统的开头,c盘空间也是从c盘的后端线性分配的。这引起了频繁的轮询操作,而且可能造成文件系统的碎片化(即文件储存在非相邻的块中)。
遍历目录结构意味着从c盘开头读取目录的inode,之后向后联通到更远的数据块,再从c盘开头读取下一个路径名组成部份的下一个inode,并向后联通到相应的数据块。这个过程在每位路径名组成部份上来回进行,速率并不快。
改进
在以后的发展中,minix文件系统忠实承继了PDP-11V7Unix文件系统,保留了它的特点包括局限。但是,随着时间的推移,在现代的Linux系统中,因为其不再具备实用性unix 系统目录,它早已从内核源代码中移除。
在稍后的一篇文章中,我们将会了解到关于BSD快速文件系统,怎么更好地布局c盘上的数据,怎么实现更长的文件名、更多的inode,以及怎样通过考虑c盘的化学特点来推动速率。
要解决目录查找时间线性下降、单个写入者或有限的文件元数据这种问题须要更新的文件系统。