linux-VFS中的数据结构
虚拟文件系统所隐含的主要思想在于引入了一个通用的文件模型,这个模型能够表示所有支持的文件系统。该模型严格遵守传统Unix文件系统提供的文件模型。
你可以把通用文件模型看作是面向对象的,在这里,对象是一个软件结构,其中既定义了数据结构也定义了其上的操作方法。出于效率的考虑,Linux的编码并未采用面向对象的程序设计语言(比如C++)。因此对象作为数据结构来实现:数据结构中指向函数的域就对应于对象的方法。
通用文件模型由下列对象类型组成:
· 超级块(superblock)对象: 存放系统中已安装文件系统的有关信息。对于基于磁盘的文件系统,这类对象通常对应于存放在磁盘上的文件系统控制块,也就是说,每个文件系统都有一个超级块对象.
超级块
很多具体文件系统中都有超级块结构,超级块是这些文件系统中最重要的数据结构,它是来描述整个文件系统信息的,可以说是一个全局的数据结构。Minix、Ext2等有超级块,VFS也有超级块,为了避免与后面介绍的Ext2超级块发生混淆,这里用VFS超级块来表示。VFS超级块是各种具体文件系统在安装时建立的,并在这些文件系统卸载时自动删除,可见,VFS超级块确实只存在于内存中,同时提到VFS超级块也应该说成是哪个具体文件系统的VFS超级块。VFS超级块在inculde/fs/fs.h中定义,即数据结构super_block,该结构及其主要域的含义如下:
struct super_block
{
/************描述具体文件系统的整体信息的域*****************
kdev_t s_dev; /* 包含该具体文件系统的块设备标识符。
例如,对于 /dev/hda1,其设备标识符为 0x301*/
unsigned long s_blocksize; /*该具体文件系统中数据块的大小,
以字节为单位 */
unsigned char s_blocksize_bits; /*块大小的值占用的位数,例如,
如果块大小为1024字节,则该值为10*/
unsigned long long s_maxbytes; /* 文件的最大长度 */
unsigned long s_flags; /* 安装标志*/
unsigned long s_magic; /*魔数,即该具体文件系统区别于其它
文系统的一个标志*/
/**************用于管理超级块的域******************/
struct list_head s_list; /*指向超级块链表的指针*/
struct semaphore s_lock /*锁标志位,若置该位,则其它进程
不能对该超级块操作*/
struct rw_semaphore s_umount /*对超级块读写时进行同步*/
unsigned char s_dirt; /*脏位,若置该位,表明该超级块已被修改*/
struct dentry *s_root; /*指向该具体文件系统安装目录的目录项。*/
int s_count; /*对超级块的使用计数*/
atomic_t s_active;
struct list_head s_dirty; /*已修改的索引节点形成的链表 */
struct list_head s_locked_inodes;/* 要进行同步的索引节点形成的链表*/
struct list_head s_files
/***********和具体文件系统相联系的域*************************/
struct file_system_type *s_type; /*指向文件系统的
file_system_type 数据结构的指针 */
struct super_operations *s_op; /*指向某个特定的具体文件系统的用
于超级块操作的函数集合 */
struct dquot_operations *dq_op; /* 指向某个特定的具体文件系统
用于限额操作的函数集合 */
u; /*一个共用体,其成员是各种文件系统
的 fsname_sb_info数据结构 */
};
所有超级块对象(每个已安装的文件系统都有一个超级块)以双向环形链表的形式链接在一起。链表中第一个元素和最后一个元素的地址分别存放在super_blocks变量的s_list域的 next 和 prev域中。s_list域的数据类型为struct list_head,在超级块的s_dirty域以及内核的其他很多地方都可以找到这样的数据类型;这种数据类型仅仅包括指向链表中的前一个元素和后一个元素的指针。因此,超级块对象的s_list域包含指向链表中两个相邻超级块对象的指针。图8.2说明了list_head 元素、next 和 prev是如何嵌入到超级块对象中的。
图8.2 超级块链表
超级块最后一个u 联合体域包括属于具体文件系统的超级块信息:
union {
struct Minix_sb_info Minix_sb;
struct Ext2_sb_info Ext2_sb;
struct ext3_sb_info ext3_sb;
struct hpfs_sb_info hpfs_sb;
struct ntfs_sb_info ntfs_sb;
struct msdos_sb_info msdos_sb;
struct isofs_sb_info isofs_sb;
struct nfs_sb_info nfs_sb;
struct sysv_sb_info sysv_sb;
struct affs_sb_info affs_sb;
struct ufs_sb_info ufs_sb;
struct efs_sb_info efs_sb;
struct shmem_sb_info shmem_sb;
struct romfs_sb_info romfs_sb;
struct smb_sb_info smbfs_sb;
struct hfs_sb_info hfs_sb;
struct adfs_sb_info adfs_sb;
struct qnx4_sb_info qnx4_sb;
struct reiserfs_sb_info reiserfs_sb;
struct bfs_sb_info bfs_sb;
struct udf_sb_info udf_sb;
struct ncp_sb_info ncpfs_sb;
struct usbdev_sb_info usbdevfs_sb;
struct jffs2_sb_info jffs2_sb;
struct cramfs_sb_info cramfs_sb;
void *generic_sbp;
} u;
通常,为了效率起见u域的数据被复制到内存。任何基于磁盘的文件系统都需要访问和更改自己的磁盘分配位示图,以便分配和释放磁盘块。VFS允许这些文件系统直接对内存超级块的u联合体域进行操作,无需访问磁盘。
但是,这种方法带来一个新问题:有可能VFS超级块最终不再与磁盘上相应的超级块同步。因此,有必要引入一个s_dirt标志,来表示该超级块是否是脏的,也就是说,磁盘上的数据是否必须要更新。缺乏同步还导致我们熟悉的一个问题:当一台机器的电源突然断开而用户来不及正常关闭系统时,就会出现文件系统崩溃。Linux是通过周期性地将所有“脏”的超级块写回磁盘来减少该问题带来的危害。
与超级块关联的方法就是所谓的超级块操作。这些操作是由数据结构super_operations来描述的,该结构的起始地址存放在超级块的s_op域中,稍后将与其他对象的操作一块介绍。
· 索引节点(inode)对象: 存放关于具体文件的一般信息。对于基于磁盘的文件系统,这类对象通常对应于存放在磁盘上的文件控制块(FCB),也就是说,每个文件都有一个索引节点对象。每个索引节点对象都有一个索引节点号,这个号唯一地标识某个文件系统中的指定文件。
VFS的索引节点
文件系统处理文件所需要的所有信息都放在称为索引节点的数据结构中。文件名可以随时更改,但是索引节点对文件是唯一的,并且随文件的存在而存在。有关使用索引节点的原因将在下一章中进一步介绍,这里主要是强调一点,具体文件系统的索引节点是存储在磁盘上的,是一种静态结构,要使用它,必须调入内存,填写VFS的索引节点,因此,也称VFS索引节点是动态节点。这里用VFS索引节点来避免与下一章的Ext2索引节点混淆。VFS索引节点的数据结构inode在/includ/fs/fs.h中定义如下(2.4.x版本):
struct inode
{
/**********描述索引节点高速缓存管理的域****************/
struct list_head i_hash; /*指向哈希链表的指针*/
struct list_head i_list; /*指向索引节点链表的指针*/
struct list_head i_dentry;/*指向目录项链表的指针*/
struct list_head i_dirty_buffers;
struct list_head i_dirty_data_buffers;
/**********描述文件信息的域****************/
unsigned long i_ino; /*索引节点号*/
kdev_t i_dev; /*设备标识号 */
umode_t i_mode; /*文件的类型与访问权限 */
nlink_t i_nlink; /*与该节点建立链接的文件数 */
uid_t i_uid; /*文件拥有者标识号*/
gid_t i_gid; /*文件拥有者所在组的标识号*/
kdev_t i_rdev; /*实际设备标识号*/
off_t i_size; /*文件的大小(以字节为单位)*/
unsigned long i_blksize; /*块大小*/
unsigned long i_blocks; /*该文件所占块数*/
time_t i_atime; /*文件的最后访问时间*/
time_t i_mtime; /*文件的最后修改时间*/
time_t i_ctime; /*节点的修改时间*/
unsigned long i_version; /*版本号*/
struct semaphore i_zombie; /*僵死索引节点的信号量*/
/***********用于索引节点操作的域*****************/
struct inode_operations *i_op; /*索引节点的操作*/
struct super_block *i_sb; /*指向该文件系统超级块的指针 */
atomic_t i_count; /*当前使用该节点的进程数。计数为0,
表明该节点可丢弃或被重新使用 */
struct file_operations *i_fop; /*指向文件操作的指针 */
unsigned char i_lock; /*该节点是否被锁定,用于同步操作中*/
struct semaphore i_sem; /*指向用于同步操作的信号量结构*/
wait_queue_head_t *i_wait; /*指向索引节点等待队列的指针*/
unsigned char i_dirt; /*表明该节点是否被修改过,若已被修改,
则 应当将该节点写回磁盘*/
struct file_lock *i_flock; /*指向文件加锁链表的指针*/
struct dquot *i_dquot[MAXQUOTAS]; /*索引节点的磁盘限额*/
/************用于分页机制的域**********************************/
struct address_space *i_mapping; /* 把所有可交换的页面管理起来*/
struct address_space i_data;
/**********以下几个域应当是联合体****************************************/
struct list_head i_devices; /*设备文件形成的链表*/
struct pipe_inode_info i_pipe; /*指向管道文件*/
struct block_device *i_bdev; /*指向块设备文件的指针*/
struct char_device *i_cdev; /*指向字符设备文件的指针*/
/*************************其他域***************************************/
unsigned long i_dnotify_mask; /* Directory notify events */
struct dnotify_struct *i_dnotify; /* for directory notifications */
unsigned long i_state; /*索引节点的状态标志*/
unsigned int i_flags; /*文件系统的安装标志*/
unsigned char i_sock; /*如果是套接字文件则为真*/
atomic_t i_writecount; /*写进程的引用计数*/
unsigned int i_attr_flags; /*文件创建标志*/
__u32 i_generation /*为以后的开发保留*/
/*************************各个具体文件系统的索引节点********************/
union; /*类似于超级块的一个共用体,其成员是各种具体文件系统的fsname_inode_info数据结构 */
}
对inode数据结构的进一步说明
· 每个文件都有一个inode,每个inode有一个索引节点号i_ino。在同一个文件系统中,每个索引节点号都是唯一的,内核有时根据索引节点号的哈希值查找其inode结构。
· 每个文件都有个文件主,其最初的文件主是创建了这个文件的用户,但以后可以改变。每个用户都有一个用户组,且属于某个用户组,因此,inode结构中就有相应的i_uid,i_gid,以指明文件主的身份。
· inode 中有两个设备号,i_dev和i_rdev。首先,除特殊文件外,每个节点都存储在某个设备上,这就是i_dev。其次,如果索引节点所代表的并不是常规文件,而是某个设备,那就还得有个设备号,这就是i_rdev。
· 每当一个文件被访问时,系统都要在这个文件的inode中记下时间标记,这就是inode中与时间相关的几个域。
· 每个索引节点都会复制磁盘索引节点包含的一些数据,比如文件占用的磁盘块数。如果i_state域的值等于I_DIRTY,该索引节点就是“脏”的,也就是说,对应的磁盘索引节点必须被更新。i_state域的其它值有I_LOCK(这意味着该索引节点对象已加锁),I_FREEING(这意味着该索引节点对象正在被释放)。每个索引节点对象总是出现在下列循环双向链表的某个链表中:
(1) 未用索引节点链表。变量inode_unused的next域 和prev域分别指向该链表中的首元素和尾元素。这个链表用做内存高速缓存。
(2) 正在使用索引节点链表。变量inode_in_use指向该链表中的首元素和尾元素。
(3) 脏索引节点链表。由相应超级块的s_dirty域指向该链表中的首元素和尾元素。
这三个链表都是通过索引节点的i_list域链接在一起的。
· 属于“正在使用”或“脏”链表的索引节点对象也同时存放在一个称为inode_hashtable链表中。哈希表加快了对索引节点对象的搜索,前提是系统内核要知道索引节点号及对应文件所在文件系统的超级块对象的地址。由于散列技术可能引发冲突,所以,索引节点对象设置一个i_hash域,其中包含向前和向后的两个指针,分别指向散列到同一地址的前一个索引节点和后一个索引节点;该域由此创建了由这些索引节点组成的一个双向链表。
与索引节点关联的方法也叫索引节点操作,由inode_operations结构来描述,该结构的地址存放在i_op域中,该结构也包括一个指向文件操作方法的指针(参见下一节“文件对象”)。
· 目录项(dentry)对象: 存放目录项与对应文件进行链接的信息。VFS把每个目录看作一个由若干子目录和文件组成的常规文件。例如,在查找 路径名/tmp/test时 , 内核为 根目录“/ ”创建一个目录项对象, 为根目录下的 tmp项创建一个第二级目录项对象,为 /tmp 目录下的test项创建一个第三级目录项对象。
目录项对象
每个文件除了有一个索引节点inode数据结构外,还有一个目录项dentry(directory enrty)数据结构。dentry 结构中有个d_inode指针指向相应的inode结构。读者也许会问,既然inode结构和dentry结构都是对文件各方面属性的描述,那为什么不把这两个结构“合而为一”呢?这是因为二者所描述的目标不同,dentry结构代表的是逻辑意义上的文件,所描述的是文件逻辑上的属性,因此,目录项对象在磁盘上并没有对应的映像;而inode结构代表的是物理意义上的文件,记录的是物理上的属性,对于一个具体的文件系统(如Ext2),Ext2_ inode结构在磁盘上就有对应的映像。所以说,一个索引节点对象可能对应多个目录项对象。
dentry 的定义在include/linux/dcache.h中:
struct dentry {
atomic_t d_count; /* 目录项引用计数器 */
unsigned int d_flags; /* 目录项标志 */
struct inode * d_inode; /* 与文件名关联的索引节点 */
struct dentry * d_parent; /* 父目录的目录项 */
struct list_head d_hash; /* 目录项形成的哈希表 */
struct list_head d_lru; /*未使用的 LRU 链表 */
struct list_head d_child; /*父目录的子目录项所形成的链表 */
struct list_head d_subdirs; /* 该目录项的子目录所形成的链表*/
struct list_head d_alias; /* 索引节点别名的链表*/
int d_mounted; /* 目录项的安装点 */
struct qstr d_name; /* 目录项名(可快速查找) */
unsigned long d_time; /* 由 d_revalidate函数使用 */
struct dentry_operations *d_op; /* 目录项的函数集*/
struct super_block * d_sb; /* 目录项树的根 (即文件的超级块)*/
unsigned long d_vfs_flags;
void * d_fsdata; /* 具体文件系统的数据 */
unsigned char d_iname[DNAME_INLINE_LEN]; /* 短文件名 */
};
下面对dentry结构给出进一步的解释。
一个有效的dentry结构必定有一个inode结构,这是因为一个目录项要么代表着一个文件,要么代表着一个目录,而目录实际上也是文件。所以,只要dentry结构是有效的,则其指针d_inode必定指向一个inode结构。可是,反过来则不然,一个inode却可能对应着不止一个dentry结构;也就是说,一个文件可以有不止一个文件名或路径名。这是因为一个已经建立的文件可以被连接(link)到其他文件名。所以在inode结构中有一个队列i_dentry,凡是代表着同一个文件的所有目录项都通过其dentry结构中的d_alias域挂入相应inode结构中的i_dentry队列。
在内核中有一个哈希表dentry_hashtable ,是一个list_head的指针数组。一旦在内存中建立起一个目录节点的dentry 结构,该dentry结构就通过其d_hash域链入哈希表中的某个队列中。
内核中还有一个队列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域指向的队列中。
从上面的叙述可以看出,一个文件系统中所有目录项结构或组织为一个哈希表,或组织为一颗树,或按照某种需要组织为一个链表,这将为文件访问和文件路径搜索奠定下良好的基础。
· 文件(file)对象: 存放打开文件与进程之间进行交互的有关信息。这类信息仅当进程访问文件期间存在于内存中。
下面我们讨论超级块、索引节点、目录项及文件的数据结构,它们的共同特点有两个:
· 充分考虑到对多种具体文件系统的兼容性
· 是“虚”的,也就是说只能存在于内存
这正体现了VFS的特点,在下面的描述中,读者也许能体会到这一点。