Linux-VFS中的数据结构
前言
VFS（虚拟文件系统）四大对象：struct super_block 超级块、struct inode 索引节点、struct dentry 目录项、struct file 文件对象
VFS采用的是面向对象的设计思想，使用一簇数据结构来代表通用文件对象。所以内核中的数据结构都使用C结构体实现。
超级块super_block对象，代表一个具体的已安装文件系统。索引节点inode对象，代表一个具体文件。目录项dentry对象，代表一个目录项，是路径的一个组成部分。文件file对象，代表有进程打开的文件。
每个主要对象中都包含一个操作对象，这些操作对象描述了内核针对主要对象可以使用的方法：
super_operations对象：包含内核针对特定文件系统所能调用的方法。inode_operations对象：包含内核对特定文件所能调用的方法。dentry_operations对象：包含内核对特定目录所能调用的方法。file_operations对象：包含进程针对已打开文件所能调用的方法。
操作对象作为一个指针结构体被实现，此结构体中包含指向操作其父对象的函数指针。对于其中许多方法来说，可以继承使用VFS提供的通用函数，如果通用函数提供的基本功能无法满足需要，就必须使用实际文件系统的独有方法填充这些函数指针，使其指向文件系统实例。
注意，这里所说的对象指的是结构体，不是像C++和Java那样的真正的数据类型。
VFS使用了大量结构体对象，它所包括的对象远远多于上述几种对象，比如：
- 每个注册的文件系统都由file_system_type结构体表示，它描述了文件系统及其性能；
- 每一个安装点都用vfsmount结构体表示，它包含的是安装点的相关信息，如位置和安装标志等。
- 与进程相关的结构体是：file_struct、fs_struct、namespace和file。它们描述了文件系统以及和进程相关的文件。
本文中的代码以linux3.10内核版本的代码为准。
超级块
很多具体文件系统中都有超级块结构，超级块是这些文件系统中最重要的数据结构，它是来描述整个文件系统信息的，可以说是一个全局的数据结构。超级块描述已安装文件系统。文件系统的控制信息存储在超级块中。超级块是文件系统的控制块，有整个文件系统信息，一个文件系统所有的inode都要连接到超级块上，可以说，一个超级块就代表了一个文件系统。
- Minix、Ext2 等有超级块，VFS 也有超级块，为了避免与后面介绍的Ext2 超级块发生混淆，这里用VFS 超级块来表示。
- VFS 超级块是各种具体文件系统在安装时建立的，并在这些文件系统卸载时自动删除
- VFS 超级块确实只存在于内存中，同时提到VFS 超级块也应该说成是哪个具体文件系统的VFS超级块。
VFS 超级块在include/linux/fs.h 中定义，即数据结构super_block，该结构及其主要域的含义如下：
1 | struct super_block { |
所有超级块对象（每个已安装的文件系统都有一个超级块）以双向环形链表的形式链接在一起。链表中第一个元素和最后一个元素的地址分别存放在super_blocks 变量的s_list 域的 next 和 prev 域中。s_list 域的数据类型为struct list_head，在内核的其他很多地方都可以找到这样的数据类型；这种数据类型仅仅包括指向链表中的前一个元素和后一个元素的指针。因此，超级块对象的s_list 域包含指向链表中两个相邻超级块对象的指针。
图1 说明了list_head 元素、next 和 prev 如何嵌入到超级块对象中的。
s_fs_info字段指向属于具体文件系统的超级块信息。为了效率起见，由s_fs_info字段所指向的数据被复制到内存(也就是具体文件系统的超级块)。任何基于磁盘的文件系统都需要访问和更改自己的磁盘分配位图（磁盘分配位图指存在于磁盘中用来标识磁盘每个块是否空闲的一段存储空间），以便分配或释放块。VFS允许这些文件系统直接对内存超级块的s_fs_info字段进行操作，而无需访问磁盘。
与超级块关联的方法就是超级块操作，由super_operations来描述，该结构的起始地址存放在超级块的s_op字段中。super_operations结构如下，代码来自include/linux/fs.h
1 | struct super_operations { |
每一个文件系统都可以定义自己的超级块操作，它可以是上面结构的一个字集，因为有些操作可能不需要，未实现的方法对应的字段置为NULL,当我们要调用其中的一个操作时，比如read_inode,这执行以下操作
1 | sb->s_op->read_inode(inode); |
这里sb存放所涉及超级块对象的地址。super_operations表的read_inode字段存放这函数的地址，因此，这一函数被直接调用。
注意，系统没有定义get_super方法来读超级块，那么，内核如何能够调用一个对象的方法而从磁盘读出该对象？
- 我们将在描述文件系统类型的另一个对象中找到等价的get_sb方法。该方法定义在具体文件系统的file_system_type结构中，在register_filesystem的时候会把该文件系统注册进去。
VFS 的索引节点
索引节点:文件系统处理文件所需要的所有信息都放在称为索引节点的数据结构中索引节点（inode）,是 VFS 中最为重要的一个结构，用于描述一个文件的meta（元）信息，其包含的是诸如文件的大小、拥有者、创建时间、磁盘位置等和文件相关的信息，所有文件都有一个对应的 inode 结构。文件名可以随时更改，但是索引节点对文件是唯一的，并且随文件的存在而存在。
有关使用索引节点的原因将在下一章中进一步介绍.
这里主要强调一点，具体文件系统的索引节点是存储在磁盘上的，是一种静态结构，要使用它，必须调入内存，填写VFS 的索引节点，因此，也称VFS 索引节点为动态节点。
这里用VFS 索引节点来避免与下一章的Ext2 索引节点混淆。VFS 索引节点的数据结构inode 在include/linux/fs.h 中定义如下:
1 | struct inode { |
inode 中几个比较重要的成员：
- i_uid：文件所属的用户
- i_gid：文件所属的组
- i_rdev：文件所在的设备号
- i_size：文件的大小
- i_atime：文件的最后访问时间
- i_mtime：文件的最后修改时间
- i_ctime：文件的创建时间
- i_op：inode相关的操作列表
- i_fop：文件相关的操作列表
- i_sb：文件所在文件系统的超级块
重点说明i_op 和 i_fop 这两个成员：
- i_op 成员定义对目录相关的操作方法列表，譬如 mkdir()系统调用会触发 inode->i_op->mkdir() 方法，而 link() 系统调用会触发 inode->i_op->link() 方法。而 i_fop 成员则定义了对打开文件后对文件的操作方法列表，譬如 read() 系统调用会触发 inode->i_fop->read() 方法，而 write() 系统调用会触发 inode->i_fop->write() 方法
进一步说明：
- 每个文件都有一个inode，每个inode 有一个索引节点号
i_ino。在同一个文件系统中，每个索引节点号都是唯一的，内核有时根据索引节点号的哈希值查找其inode结构。 - 每个文件都有个文件主，其最初的文件主是创建了这个文件的用户，但以后可以改变。每个用户都有一个用户组，且属于某个用户组，因此，inode 结构中就有相应的
i_uid、i_gid，以指明文件主的身份。 - inode 中有两个设备号，
i_dev和i_rdev。首先，除特殊文件外，每个节点都存储在某个设备上，这就是i_dev。其次，如果索引节点所代表的并不是常规文件，而是某个设备，那就还得有个设备号，这就是i_rdev。 - 每当一个文件被访问时，系统都要在这个文件的inode 中记下时间标记，这就是inode中与时间相关的几个域。
- 属于“ 正在使用” 或“ 脏” 链表的索引节点对象也同时存放在一个称为
inode_hashtable 链表中。- 哈希表加快了对索引节点对象的搜索，前提是系统内核要知道索引节点号及对应文件所在文件系统的超级块对象的地址。
- 由于散列技术可能引发冲突，所以，索引节点对象设置一个i_hash 域，其中包含向前和向后的两个指针，分别指向散列到同一地址的前一个索引节点和后一个索引节点；该域由此创建了由这些索引节点组成的一个双向链表。
- 与索引节点关联的方法也叫索引节点操作，由
inode_operations结构来描述，该结构的地址存放在i_op 域中，该结构也包括一个指向文件操作方法的指针。
目录项对象
dentry 的定义在include/linux/dcache.h 中：
目录项的主要作用是方便查找文件。一个路径的各个组成部分，不管是目录还是普通的文件，都是一个目录项对象。
- 如，在路径 /home/liexusong/example.c 中，目录 /, home/, liexusong/ 和文件 example.c 都对应一个目录项对象。
- 不同于前面的两个对象，目录项对象没有对应的磁盘数据结构，VFS 在遍历路径名的过程中现场将它们逐个地解析成目录项对象。
- 请注意，目录项对象在磁盘上并没有对应的镜像，因此在dentry结构中不包含指出该对象已被修改的字段。
- 目录项对象存放在名为dentry_cache的slab分配器高速缓存中。因此，目录项对象的创建和删除是通过调用kmem_cache_alloc()和kmem_cache_free()实现的。
每个目录项对象可以处于以下四种状态之一：
- 空闲状态（free）：处于该状态的目录项对象不包括有效的信息，而且还没有被VFS使用。对应的内存区由slab分配器进行处理。
- 未使用状态（unused）：处于该状态的目录项对象当前还没有被内核使用。该对象的引用计数器d_count的值为0，但其d_inode字段仍然指向关联的索引节点对象。该目录项对象包含有效的信息，但是为了在必要时回收内存，它的内容可能被丢弃。
- 正在使用状态（in use）：处于该状态的目录项对象当前正在被内核使用。该对象的引用计数器d_count的值为正数，其d_inode字段指向关联的索引节点对象。该目录项对象包含有效的信息，并且不能被丢弃。
- 负状态(negative)：与目录项关联的索引节点不复存在，那是因为相应的磁盘索引节点已被删除，或者因为目录项对象是通过解析一个不存在文件的路径名创建的。目录项对象的d_inode字段被置为NULL，但该对象仍然被保存在目录项高速缓存中，以便后续对同一文件目录名的查找操作能够快速完成。术语“负状态”容易使人误解，因为根本不涉及任何负值。
目录项的定义如下：
1 | struct dentry { |
与目录项对象关联的方法称为目录项操作。这些方法由dentry_operations结构加以描述，该结构的地址存放在目录项对象的d_op字段中。尽管一些文件系统定义了它们自己的目录项方法，但是这些字段通常为NULL，而VFS使用缺省函数代替这些方法：
1 | struct dentry_operations { |
下面对dentry 结构给出进一步的解释。
dentry与inode的关系：一个有效的dentry 结构必定有一个inode 结构，这是因为一个目录项要么代表着一个文件，要么代表着一个目录，而目录实际上也是文件。所以，只要dentry 结构是有效的，则其指针d_inode 必定指向一个inode 结构。可是，反过来则不然，一个inode 却可能对应着不止一个dentry 结构；也就是说，一个文件可以有不止一个文件名或路径名。这是因为一个已经建立的文件可以被连接（link）到其他文件名。所以在inode 结构中有一个队列i_dentry，凡是代表着同一个文件的所有目录项都通过其dentry 结构中的d_alias 域挂入相应inode结构中的i_dentry 队列。dentry_hashtable：在内核中有一个哈希表dentry_hashtable ，是一个list_head 的指针数组。一旦在内存中建立起一个目录节点的dentry 结构，该dentry 结构就通过其d_hash 域链入哈希表中
的某个队列中。dentry_unused队列：内核中还有一个队列dentry_unused，凡是已经没有用户（count 域为0）使用的dentry结构就通过其d_lru 域挂入这个队列。- dentry 结构中除了d_alias、d_hash、d_lru 三个队列外，还有d_vfsmnt、d_child 及d_subdir 三个队列。
- 其中d_vfsmnt 仅在该dentry 为一个安装点时才使用。
- 当该目录节点有父目录时，则其dentry 结构就通过d_child 挂入其父节点的d_subdirs 队列中，同时又通过指针d_parent 指向其父目录的dentry 结构，而它自己各个子目录的dentry 结构则挂在其d_subdirs 域指向的队列中。
从上面的叙述可以看出，一个文件系统中所有目录项结构或组织为一个哈希表，或组织为一颗树，或按照某种需要组织为一个链表，这将为文件访问和文件路径搜索奠定下良好的基础。
目录项高速缓存
由于从磁盘读入一个目录项并构造相应的目录项对象需要花费大量时间，所以，在完成对目录项对象的操作后，可能后面还要使用它，因此仍在内存中保留它有重要的意义。
为了最大限度地提高处理这些目录项对象的效率，Linux使用目录项高速缓存，它由两种类型的数据结构组成：
- 一个处于正在使用，未使用或负状态的目录项对象的集合
- 一个散列表，从中能快速获取与给定的文件名和目录名对应的目录项对象。同样，如果访问的对象不再目录项高速缓存中，则散列函数返回一个空值。
目录项高速缓存的作用还相当于索引节点高速缓存（inode cache）的控制器。在内核内存中，并不丢弃与未用目录项相关的索引节点，这是由于目录项高速缓存仍在使用它们。因此，这些索引节点对象保存在RAM中，并且能够借助相应的目录项快速引用他们。
为了减少VFS层遍历文件路径的时间，内核将目录项对象缓存在目录项缓存（简称dcache）中。目录项缓存包括三个主要部分：
- “被使用的”目录项链表。
- “未被使用的”双向链表。
- 散列表和相应的散列函数。
每个目录项对象可以处于四种状态（空闲状态，未使用状态，正在使用状态，负状态）。被使用和未被使用的目录项都对应一个有效的索引节点，而负状态的目录项没有对应的有效索引节点。
所有“未使用”目录项对象都存放在一个“最近最少使用（Least Recently used，LRU）”的双向链表中，该链表按照插入的时间排序。
- 换句话说，最后释放的目录项对象放在链表的首部，所以最近最少使用的目录项对象总是靠近链表的尾部。一旦目录项高速缓存的空间开始变小，内核就从链表的尾部删除元素，使得最近最常用的对象得以保存。
- LRU链表的首元素和尾元素的地址存放在list_head类型的
dentry_unused变量的next字段和prev字段中。目录项对象的d_lru字段包括指向链表中的相邻目录项的指针。
每个“正在使用”的目录项对象都被插入一个正在使用的双向链表中
- 该链表由相应索引节点对象的
i_dentry字段所指向(由于每个索引节点可能与若干硬链接相关联，所以需要一个链表)。 - 目录项对象的d_alias字段存放链表中相邻元素的地址。这两个字段的类型都是struct list_head。
- 当指向相应文件的最后一个硬链接被删除后，一个“正在使用”的目录项对象可能变成负状态。在这种情况下，该目录项对象被移到“未使用”目录项对象组成的LRU链表中。每当内核缩减目录项高速缓存时，“负状态”目录项对象就朝着LRU链表的尾部移动，这样一来，这些对象就逐渐被释放。
散列表是由dentry_hashtable数组实现的，方便虚拟文件系统vfs快速索引dentry。。
- 数组中每个元素是一个指向链表的指针，这种链表就是把具有相同散列表值的目录项进行散列而形成的。
- 该数组的长度取决于系统已经安装的RAM的数量，缺省值是每兆字节RAM包含256个元素。
- 散列函数的产生的值是由目录的目录项对象及其文件名计算出来的。
还有一个链表就是表示父子结构的链表。
与进程相关的文件结构
先解释一下文件描述符、打开的文件描述、系统打开文件表、用户打开文件表的概念以及它们的联系
文件对象
文件描述符(fd)：在Linux 中，进程是通过文件描述符（file descriptors，简称fd）而不是文件名来访问文件的，文件描述符实际上是一个整数。
Linux 中规定每个进程最多能同时使用NR_OPEN个文件描述符(进程最大打开文件数限制sysctl_nr_open)，sysctl_nr_open值在include/linux/fs.h 中定义，为1024×1024（2.0 版中仅定义为256）。
文件位置：每个文件都有一个32 位的数字来表示下一个读写的字节位置，这个数字叫做文件位置。
- 每次打开一个文件，除非明确要求，否则文件位置都被置为0，即文件的开始处，此后的读或写操作都将从文件的开始处执行，但你可以通过执行系统调用
LSEEK（随机存储）对这个文件位置进行修改。
打开的文件描述（open file description）：Linux 中专门用了一个数据结构file 来保存打开文件的文件位置，这个结构称为打开的文件描述。这个数据结构的设置是煞费苦心的，因为它与进程的联系非常紧密，可以说这是VFS 中一个比较难于理解的数据结构。
首先，为什么不把文件位置干脆存放在索引节点中，而要多此一举，设一个新的数据结构呢？
为了避免多个进程对同一个文件的lseek操作相互影响：我们知道，Linux 中的文件是能够共享的，假如把文件位置存放在索引节点中，则如果有两个或更多个进程同时打开同一个文件时，它们将去访问同一个索引节点，于是一个进程的LSEEK 操作将影响到另一个进程的读操作，这显然是不允许也是不可想象的。
既然进程是通过文件描述符访问文件的，为什么不用一个与文件描述符数组相平行的数组来保存每个打开文件的文件位置？
尽管设置平行的数组保存每个打开文件的文件位置可以解决多个进程对一个文件操作的问题，但是无法解决子进程继续操作文件的问题。设置平行的数组这个想法也是不能实现的，原因就在于在生成一个新进程时，子进程要共享父进程的所有信息，包括文件描述符数组。
- 一个文件不仅可以被不同的进程分别打开，而且也可以被同一个进程先后多次打开。一个进程如果先后多次打开同一个文件，则每一次打开都要分配一个新的文件描述符，并且指向一个新的file 结构，尽管它们都指向同一个索引节点，但是，如果一个子进程不和父进程共享同一个file 结构，而是也如上面一样，分配一个新的file 结构，会出现什么情况了？让我们来看一个例子。
- 假设有一个输出重定位到某文件A 的shell script（shell 脚本），我们知道，shell是作为一个进程运行的，当它生成第1 个子进程时，将以0 作为A 的文件位置开始输出，假设输出了2KB 的数据，则现在文件位置为2KB。然后，shell 继续读取脚本，生成另一个子进程，它要共享shell 的file 结构，也就是共享文件位置，所以第2 个进程的文件位置是2KB，将接着第1 个进程输出内容的后面输出。如果shell 不和子进程共享文件位置，则第2 个进程就有可能重写第1 个进程的输出了，这显然不是希望得到的结果。
上面的讨论可以看出设置file 结构的原因。
file 结构中主要保存了文件位置，此外，还把指向该文件索引节点的指针也放在其中。
系统打开文件表:file 结构形成一个双链表，称为系统打开文件表，其最大长度是NR_FILE，在fs.h 中定义为8192。
file 结构在include/linux/fs.h 中定义如下,具体的解释可以去看《Linux内核设计与实现》：
1 | struct file { |
类似于目录项对象，文件对象实际上没有对应的磁盘数据．所以在结构体中没有代表其对象是否为脏、是否需要写回磁盘的标志。文件对象通过f_dentry指针指向相关的目录项对象．目录项会指向相关的索引节点，索引节点会记录文件是否是脏的。
每个文件对象总是包含在下列的一个双向循环链表之中。
- “未使用”文件对象的链表：
- 该链表既可以用做文件对象的内存高速缓存，又可以当作超级用户的备用存储器，也就是说，即使系统的动态内存用完，也允许超级用户打开文件。
- 由于这些对象是未使用的，它们的f_count 域是NULL，该链表首元素的地址存放在变量free_list 中，内核必须确认该链表总是至少包含NR_RESERVED_FILES 个对象，通常该值设为10。
- “正在使用”文件对象的链表。
- 该链表中的每个元素至少由一个进程使用，因此，各个元素的f_count 域不会为NULL，该链表中第一个元素的地址存放在变量anon_list 中。
- 如果VFS 需要分配一个新的文件对象，就调用函数get_empty_filp( )。该函数检测“未使用”文件对象链表的元素个数是否多于NR_RESERVED_FILES，如果是，可以为新打开的文件使用其中的一个元素；如果没有，则退回到正常的内存分配。
每个文件系统都有其自己的文件操作集合,执行诸如读写文件这样的操作。
- 当内核将一个索引节点从磁盘装入内存的时候,就会把指向这些文件操作的指针存放在file_operations结构中，而该结构的地址存放在该索引节点的i_fop字段中。
- 当进程打开这个文件的时候，vfs就用存放在索引节点中的这个地址初始化新文件对象的f_op字段，使得对文件操作的后续调用能够使用这些函数。
- 如果需要，vfs随后也可以通过在f_op字段存放一个新值而修改文件操作的集合。
file的操作集合如下，代码在include/linux/fs.h 中：
1 | struct file_operations { |
用户打开文件表
每个进程用一个files_struct 结构来记录文件描述符的使用情况，这个files_struct结构称为用户打开文件表， 它是进程的私有数据。
files_struct 结构在include/linux/fdtable.h 中定义如下：
1 | struct fdtable { |
- fd_array数组指针指向已经打开的文件对象。因为NR_OPEN_DEFAULT等于BITS_PER_LONG，在64位机器体系结构中这个宏的值为64，所以该数组可以容纳64个文件对象。如果一个进程打开的文件对象超过64个，内核将分配一个新数组，并将fdt指针指向它。所以对适当数量的文件对象的访问会执行的很快，因为它是对静态数组的操作；如果一个进程打开的文件数量过多，那么内核就需要建立新数组。所以如果系统中有大量的进程都要打开超过64 个文件，为了优化性能，管理员可以适当增NR_OPEN_DEFAULT 的预定义值．
- open_fds定义在include/linux/fdtable.h中，
关于文件系统信息的fs_struct 结构
进程和文件的相互作用时，内核必须维护一些数据，其中就有进程的fs_struct 结构。每个进程描述符的fs字段就指向进程的fs_struct结构。
义在include/linux/fs_struct.h 中:
1 | struct fs_struct { |
VFS数据结构间的关系
超级块：对一个文件系统的描述；
索引节点：对一个文件物理属性的描述；
目录项：对一个文件逻辑属性的描述。
文件与进程之间的关系是由另外的数据结构来描述的：
- 一个进程所处的位置是由
fs_struct来描述的 - 一个进程（或用户）打开的文件是由
files_struct来描述的 - 整个系统所打开的文件是由
file结构来描述。
如图2给出了这些数据结构之间的关系：
图2来自链接
总结
参考资料
《深入分析Linux内核源代码》 //书籍内核版本有些旧
《Linux内核设计与实现》 //目前感觉这个版本是最准的
Linux 内核编程之文件系统（一）Linux文件编程之虚拟文件系统(VFS)
Linux 内核编程之文件系统（二）VFS中的目录项对象和文件对象
理解linux文件系统—VFS主要数据结构及之间的关系 //这里面的配图不错
VFS中的基本数据结构
虚拟文件系统
文件系统– 虚拟文件系统相关数据结构