《Linux内核链表及其在虚拟文件系统中的应用.pdf》由会员分享，可在线阅读，更多相关《Linux内核链表及其在虚拟文件系统中的应用.pdf（5页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、2011 年 3 月第 16 卷 第 2 期?西?安?邮?电?学?院?学?报JOURNAL OF XI?AN UNIVERSIT Y OF POSTS AND TELECOMMUNICATIONSMar.2011Vol?16 No?2收稿日期:2011?01?20基金项目:西安邮电学院中青年科研基金资助项目(103?0439)作者简介:梁琛(1978?),女,讲师,硕士,研究方向:Linux 操作系统、嵌入式系统,E?mail:mumulc ;陈莉君(1964?),女,教授,硕士,研究方向:Linux 操作系统。Linux 内核链表及其在虚拟文件系统中的应用梁?琛,陈莉君(西安邮电学院 计算机
2、学院,陕西 西安?710121)摘要:为了提高代码的重用性,Linux 内核提供了一种抽象的双向循环链表结构。通过对这种双向循环链表及其在Linux 虚拟文件系统中的应用进行分析,可以了解这种链表的巧妙之处。这种链表可以将不同结构体类型的数据链接起来,并可以使用相同的链表操作,从而能有效地提高编程效率。关键词:Linux 内核;链表;虚拟文件系统中图分类号:T P311.5?文献标识码:B?文章编号:1007?3264(2011)02?0029?05?在 C 语言程序中经常用到双向循环链表来组织数据,链表中每个结点的信息是定义在结构体类型中的,当使用的结构体类型不同时,需要创建不同的链表,并且
3、需要为每一个链表编写插入、删除、查找等基本操作函数,但是通常链表这些基本操作的执行步骤是基本相同的,而只是由于结构体类型不同,就需要重写代码,花费程序员大量不必要的时间。在Linux 内核源代码中也大量用到了这种数据结构,如果需要为每一个链表都编写基本操作函数,就会有大量的重复性代码。在研究 Linux 的虚拟文件系统时,发现其中使用的双向循环链表并不需要编写这样的冗余代码,而是提供了一种更好的使用方式,使得不同结构体类型的结点都可以通过这种链表链接起来,而且可以使用相同的链表操作,从而提高代码的重用性。本文将对 Linux 内核 2.6 版以后的源码中使用的双向循环链表进行分析,研究Linu
4、x 内核中双向循环链表的构造、基本操作及其在虚拟文件系统中的应用,以及如何在用户程序中利用这种巧妙的设计,提高编程效率。1?传统的双向循环链表在 C 语言程序中若想根据需要动态地分配和释放内存单元,通常可以使用链表结构来组织数据 1。1.1?双向循环链表的类型定义传统的双向循环链表是将每个结点的基本信息定义在结构体类型中,并在结构体类型中增加指向本结构体类型的前向指针和后向指针,用来指示本结点的前驱结点和后继结点 2,从而将若干个结点有机的链接起来,若首尾结点也连接起来,就构成了双向循环链表 3,其结构如图 1 所示,其中 head 为头指针。结构体类型的定义如下:struct dlink?E
5、lemT ype data;?struct dlink*next,*prev;图 1?双向循环链表结构1.2?双向循环链表的基本操作通常在对结点类型不同的链表进行相同的操作时,需要针对不同结构体类型编写不同的函数来完成。例如,对于插入操作,若找到了要插入结点 p 在链表中的位置,所需要做的工作就是:修改插入结点的前后向指针,以及其前驱结点的后向指针和后继结点的前向指针,如图 2 所示。例如,对于结点类型为 struct dlink1 和 structdlink2 这两个不同结构体类型的链表,需要提供两个插入函数,接口形式如下:int insert1(struct dlink1*head1,st
6、ruct dlink1*P1);int insert2(struct dlink2*head2,struct dlink2*P2);图 2?双向循环链表的插入操作分别代表在 head1 所指示的 dlink1 类型的链表中插入结点 P1,和在 head2 所指示的 dlink2 类型的链表中插入结点 P2。虽然都是向链表中插入一个结点,执行的操作是一样的,但是由于使用的链表结点类型不同,就需要编写不同的函数,造成了代码冗余。对于其它的基本操作,包括删除、查找等都存在同样的问题。2?Linux 内核中的双向循环链表Linux 内核源代码中有很多地方都需要用双向循环链表来组织数据,比如进程、文件、
7、模块等,若使用传统的链表结构会造成大量的冗余代码,降低代码的重用 性,因此,Linux 内核 源码 在 include/linux/list.h 中提供了双向循环链表。2.1?结构体类型定义区别于传统的双向循环链表,在 list.h 中定义了这样一个结构体类型 4:struct list_head?struct list_head*next,*prev;在这个结构体类型定义中,并没有数据成员,而只有两个指向本结构体类型的指针,分别指向其前驱结点和后继结点,因此,这个结构体的主要作用就是嵌套在其它结构体类型的定义中起到链接作用。如果需要构造某种结构体类型的链表,只需要在该结构体类型中定义一个 l
8、ist_head 指针成员即可,通过这个指针成员就可以将这种结构体类型的结点链接起来,形成链表。2.2?几个重要的宏不同结构体类型的结点怎样链接起来呢?以下几个重要的宏起关键作用。(1)初始化链表#defineLIST _ HEAD _ INIT(name)&name,&name#define LIST _HEAD(name)struct list_head name=LIST _HEAD_INIT(name)通过这两个宏完成了链表的初始化,它们的作用相当于将链表的前后向指针指向了自己,如图 3所示。图 3?链表的初始化在 list.h 中还提供了另外一个初始化宏,同样可以完成初始化的工作。#
9、define INIT_LIST_HEAD(ptr)do?(ptr)-next=(ptr);(ptr)-prev=(ptr);?while(0)(2)遍历链表宏#define _list_for_each(pos,head)for(pos=(head)-next;pos!=(head);pos=pos-next)head 是指向整个链表的头指针,pos 是指向每个结点中后向指针成员的指针,通过 pos 指针不停的向后移动,可以达到遍历整个链表的目的 5。(3)获取整个结构体变量的地址宏通过遍历链表,获得的是所需结点中后向指针成员的地址,而非结点自身的地址,那么,如何通过这个地址来获取整个结点的
10、地址呢?这就引入了list_entry 宏 6。这个宏可以通过结构体中某个成员的地址来获取整个结构体的地址,这是设计非常巧妙的一个宏,也是比较难理解的一个关键宏。#define list_entry(ptr,type,member)?container_of(ptr,type,member)这个宏的作用是获取指针 ptr 指向的 member成员所在结点的首地址,这个结点类型是 type 结构体类型。其中 ptr 是指向 member 的指针,member是 type 结构体类型的成员。关系如图 4 所示。图 4?链表中结点首地址的获取?30?西?安?邮?电?学?院?学?报?2011 年 3
11、月这个宏里面还包含另外一个宏 container_of,这个宏位于 linux/kernel.h 中,它的定义为:#define container_of(ptr,type,member)(?const typeof(type*)0)-member)*_mptr=(ptr);(type*)(char*)_mptr-offsetof(type,member);)这个宏包含两条语句:?const typeof(type*)0)-member)*_mptr=(ptr);首先将地址 0 转化成 type 类型的指针变量,然后再引用 type 结构体类型中的 member 成员(即(type*)0)-m
12、ember)。typeof(type*)0)-member)就是返回 member 成员的数据类型。因此这条语句就是定义了与 member 成员相同数据类型的_mptr,并用 ptr 对它进行初始化。?(type*)(char*)-mptr offsetof(type,member);其中的 offsetof 也是一个宏,它在 linux/std?def.h 中这样定义 7:#define offsetof(TYPE,MEMBER)(size_t)&(TYPE*)0)-MEMBER)&(TYPE*)0)-MEMBER)就是取得TYPE 结构体中 MEMBER 成员的地址,再对它强制类型转换成
13、size_t 类型(即 unsigned int 类型),就可以得到一个 unsigned int 类型的数,因为这里使用的是地址为 0 的结构体,因此得到的这个值就是 MEMBER 成员相对于结构体首地址的偏移量。将_mptr 强制类型转换成(char*),这样再与offsetof 宏相减时就是以字节为单位相减,得到的就是两个地址的差值。因此,用 member 成员的地址,减去 member 成员距本结点首地址的偏移量,得到的就是本结点的首地址。2.3?双向循环链表的基本操作Linux 内核中提供了很多链表的基本操作接口,以下列出常用的几个,还有其它一些基本操作接口,在此不做赘述。(1)插入
14、链表中的插入分为头插和尾插,在 Linux 内核中提供相对应的两个接口:static inline void list_add(struct list _head*new,struct list_head*head);static inline void list_add_tail(struct list_head*new,struct list_head*head);它们 分别 完成 在链 表表 头和 表尾 插 入结点 new。(2)删除Linux 内核提供这样的接口:static inline void list_del(struct list _head*entry);将删除 entry
15、 结点。(3)合并除了针对结点的插入、删除操作,Linux 链表还提供了整个链表的插入功能:static inline void list_splice(struct list_head*list,struct list_head*head);将 list 和 head 指示的两个链表合并起来。3?双向循环链表在 Linux 虚拟文件系统中的应用?Linux 使用了虚拟文件系统来支持除了 Linux自身支持的 Ext3 文件系统之外的其它各种不同的文件系统 8。双向循环链表在 Linux 虚拟文件系统中有着广泛的应用。3.1?Linux 虚拟文件系统中常用的几种数据结构在虚拟文件系统中,有以下
16、一些数据结构,它们都用到了双向循环链表。(1)超级块对象:存放系统中已安装文件系统的有关信息。(2)索引节点:存放关于具体文件的一般信息。(3)目录项对象:存放目录项与对应文件进行链接的信息。(4)文件对象:存放打开的文件与进程之间进行交互的有关信息。以下是索引节点结构的定义:struct inodestruct list_head i_hash;?/*指向哈希链表的指针*/struct list_head i_list;?/*指向索引节点链表的指针*/struct list_head i_dentry;?/*指向目录项链表的指针*/?unsigned long i_ino;/*索引节点号*/
17、?;3.2?双向循环链表在虚拟文件系统中的应用以索引节点为例,在结构体类型定义中,定义了?31?第 2 期梁琛,等:Linux 内核链表及其在虚拟文件系统中的应用三个 list_head 指针,使用这些指针可以建立三个链表,分别为哈希链表、索引节点链表以及目录项链表。以目录项链表为例,链表的结构如图 5所示。图 5?索引节点中目录项链表结构(1)初始化链表struct list_head head;LIST _HEAD(head);创建了一个空链表,链表表头是 head 9。也可以下面的形式初始化:INIT _LIST _HEAD(&head);(2)插入假设有一个新的索引节点 new_ino
18、de 需要添加到链表头,可以这样操作:list_add(&new_inode.i_dentry,&head);由此看出,目录项链表中记录的并不是新插入索引节点 new_inode 的地址,而是其中的 i_dentry成员的地址。(3)删除当需要删除目录项链表中的索引节点 new_in?ode 时,可以这样操作:list_del(&new_inode.i_dentry);(4)遍历定义一个(struct list_head*)指针变量 pos,然后调用list_for_each(pos,&head)就可以对目录项链表进行遍历。(5)通过链表指针获取结点首地址要访问目录项链表中第一个索引节点,可以
19、这样调用:list_entry(&head.next,struct inode,i_den?try);4?在用户程序中的应用如果把双向循环链表用于用户程序,也能大大提高代码的重用性。可以在用户程序自定义的结构体类型中定义一个或多个 list_head 指针,用于链接不同的链表。例如,将传统的循环双向链表使用的结构体进行改写,其中只有一个 list_head 指针,结构体类型定义如下:struct dlinkElemT ype data;struct list_head list;首先,初始化链表。struct list_head head;LIST_HEAD(head);或 INIT_LIST
20、 _HEAD(&head);其次,以插入结点 new 为例,可以通过 list_add(&new.list,&head);将 new 结点插入到 head 所指示的链表当中。接下来若要遍历链表,提取链表中的每个元素,可以如下方式来操作 10:list_for_each(pos,&head)newdata=list_entry(pos,struct dlink,list);其中,pos 是(struct list_head*)的指针变量,它是遍历过程中的向后移动的指针,newdata 用来获取链表上每个结点的首地址。其余的操作基本思想大致相同,在此不做分析。5?结论本文研究分析了 Linux 内
21、核中常用的双向循环链表结构,并对其在虚拟文件系统中的应用进行了分析。分析表明 Linux 内核中使用的双向循环链表结构是一种能有效提高代码重用性,提高编码效率的数据组织方式,若将这种链表结构用于用户程序,也可以提高程序员的编码效率,值得借鉴。参?考?文?献1?谭浩强.C 语言程序设计 M.北京:清华大学出版社,2005.2?刘宾礼,孙俊忠,周智勇,等.链表浅析 J.电脑学习,2010,(1):141?142.3?严蔚敏,吴伟民.数据结构 M.北京:清华大学出版社,2004.4?余 旭.Linux 源码 分析?链表 代码 分析 EB/OL.(2005?11?17)2011?01?04.http:
22、/5?陈莉君.Linux 内核代码赏析与应用(二)-链表之实现 EB/OL.(2008?12?18)2011?01?04.http:/ 内核修炼之道 M.北京:人民邮电出版社,2010.7?毛德操.Linux 内核源代码情景分析 M.杭州:浙江大学出版社,2001.8?陈莉君.Linux 操作系统原理与应用 M.北京:清华大学出版社,2006.9?杨沙洲.深入分析 Linux 内核链表EB/OL.(2004?08?01)2011?01?04.http:/ 年 3 月operworks/cn/linux/kernel/l?chain/10 美 博韦,西斯特著.深入理解 Linux 内核(第 3
23、版)M.陈莉君,张琼声,张宏伟译.北京:中国电力出版社,2008.Linux kernel list and its application in the virtual file systemLIANG Chen,CHEN Li?jun(School of Computer and Science Technology,Xi?an University of Posts and T elecommunications,Xi?an 710121,China)Abstract:In order to improve the reusability of the code,Linux kernel
24、 provides a double circular linkedlist.Analyses on the structure of this list and its application in the virtual file system show that,comparedwith the traditional list,this kind of list is of a wonderful design.Different structured nodes can be linkedtogether based on this list,and they can use a s
25、ame list operation,thus the efficiency of programming canbe increased.Key words:Linux kernel;list;virtual file system 责任编辑:孙书娜(上接第 28 页)A testing project management framework based on tree controlWANG Zhong?min,ZHOU Ai?ling,FAN Lin(School of Computer Science and Technology,Xi?an University of Posts
26、and T elecommunications,Xi?an 710121,China)Abstract:T here are so many species and so large quantity of testing project files which are called very fre?quently during the embedded software testing,that it?s very important for the testing system to managethe project files structurally and efficiently
27、.It is proposed that,tree controls are employed to manage thetesting projects by Win32 API within the development of a host?based embedded software testing platformnamed ARMT est.Experimental testing results show that the testing platform shares a friendly user inter?face and satisfies the requirements for managing the testing projects efficiently.Key words:tree control;embedded software;testing platform;API;project management 责任编辑:孙书娜?33?第 2 期梁琛,等:Linux 内核链表及其在虚拟文件系统中的应用