linux内核链表分析

一、常用的链表和内核链表的区别

1.1  常规链表结构

       通常链表数据结构至少应包含两个域:数据域和指针域,数据域用于存储数据,指针域用于建立与下一个节点的联系。按照指针域的组织以及各个节点之间的联系形式,链表又可以分为单链表、双链表、循环链表等多种类型,下面分别给出这几类常见链表类型的示意图:

单链表:

linux内核链表分析

双链表:

linux内核链表分析

1.2  Linux 2.6内核链表数据结构

       链表数据结构的定义很简单(节选自[include/linux/list.h],以下所有代码,除非加以说明,其余均取自该文件):

struct list_head { struct list_head *next, *prev;};  list_head结构包含两个指向list_head结构的指针prev和next,由此可见,内核的链表具备双链表功能,实际上,通常它都组织成双循环链表。list_head从字面上理解,好像是头结点的意思。但从这里的代码来看却是普通结点的结构体。在后面的代码中将list_head当成普通的结点来处理。
和第一节介绍的双链表结构模型不同,这里的list_head没有数据域。在Linux内核链表中,不是在链表结构中包含数据,而是在数据结构中包含链表节点。

linux内核链表与普通链表的示意图:

linux内核链表分析

linux内核链表分析

在数据结构课本中,链表的经典定义方式通常是这样的(以单链表为例):

struct list_node {struct list_node *next;ElemTypedata;};
因为ElemType的缘故,对每一种数据项类型都需要定义各自的链表结构。并且对于每种的数据结构还要定义相应的操作函数,比如插入、删除、排序等(这正是linux内核数据结构所要避免的)。

二、  linux内核链表的常用操作函数
linux内核链表的好处:

设计思想:尽可能的代码重用,化大堆的链表设计为单个链表。
    链表的构造:如果需要构造某类对象的特定列表,则在其结构中定义一个类型为list_head指针的成员,通过这个成员将这类对象连 接起来,形成所需列表,并通过通用链表函数对其进行操作。其优点是只需编写通用链表函数,即可构造和操作不同对象的列表,而无需为每类对象的每种列表编写专用函数,实现了代码的重用。如果想对某种类型创建链表,就把一个list_head类型的变量嵌入到该类型中,用list_head中的成员和相对应的处理函数来对链表进行遍历。如果想得到相应的结构的指针,使用list_entry可以算出来。

2.1  新建一个链表

实际上Linux只定义了链表节点,并没有专门定义链表头,那么一个链表结构是如何建立起来的呢?让我们来看看LIST_HEAD()这个宏:

#define LIST_HEAD_INIT(name)      { &(name), &(name) }

#define LIST_HEAD(name)      struct list_head name = LIST_HEAD_INIT(name)

其中的name是struct list_head结构的变量的地址,而不是包含struct list_head的数据结构的变量的地址

2.2  插入\删除\搬移\合并

a)插入

对链表的插入操作有两种:在表头插入和在表尾插入。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)

b) 删除

static inline void list_del(struct list_head *entry);

c) 搬移

Linux提供了将原本属于一个链表的节点移动到另一个链表的操作,并根据插入到新链表的位置分为两类:

static inline void list_move(struct list_head *list, struct list_head *head);

static inline void list_move_tail(struct list_head *list, struct list_head *head);

d) 合并

除了针对节点的插入、删除操作,Linux链表还提供了整个链表的插入功能:

static inline void list_splice(struct list_head *list, struct list_head *head);

2.3  遍历
      遍历是链表最经常的操作之一,为了方便核心应用遍历链表,Linux链表将遍历操作抽象成几个宏。在介绍遍历宏之前,我们先看看如何从链表中访问到我们真正需要的数据项。

a) 由链表节点到数据项变量

list_entry宏是用来根据list_head指针查找链表所嵌入的结构体的地址,具体实现是依赖宏container_of:

#define list_entry(ptr, type, member)    container_of(ptr, type, member)

#define container_of(ptr, type, member)      ({ const typeof( ((type *)0)->member ) *__mptr = (ptr);  
                                                                         (type *)( (char *)__mptr - offsetof(type,member) );})

#define offsetof(type,  member)    ((size_t) &((type *)0)-> member)

container_of有三个参数, ptr是成员变量的指针, type是指结构体的类型, member是成员变量的名字。 container_of 的作用就是在已知某一个成员变量的名字、指针和结构体类型的情况下,计算结构体的指针,也就是计算结构体的起始地址。 计算的方法其实很简单,就是用该成员变量的指针减去它于type结构体起始位置的偏移量。在这个定义中,typeof( ((type *)0)->member ) 就是获得 member 的类型, 然后定义了一个临时的常量指针 __mptr, 指向 member 变量。 把 __mptr 转换成 char * 类型, 因为 offsetof 得到的偏移量是以字节为单位。 两者相减得到结构体的起始位置, 再强制转换成 type 类型。

offsetof在这里,TYPE表示一个结构体的类型,MEMBER是结构体中的一个成员变量的名字。offsetof 宏的作用是计算成员变量 MEMBER 相对于结构体起始位置的内存偏移量,以字节(Byte)为单位。
b) 遍历宏

函数首先定义一个(struct list_head *)指针变量i,然后调用list_for_each(i,&nf_sockopts)进行遍历。在[include/linux/list.h]中,list_for_each()宏是这么定义的:

#define list_for_each(pos, head)

for (pos = (head)->next, prefetch(pos->next); pos != (head);  pos = pos->next, prefetch(pos->next))

它实际上是一个for循环,利用传入的pos作为循环变量,从表头head开始,逐项向后(next方向)移动pos,直至又回到head(prefetch()可以不考虑,用于预取以提高遍历速度)。

大多数情况下,遍历链表的时候都需要获得链表节点数据项,也就是说list_for_each()和list_entry()总是同时使用。对此Linux给出了一个list_for_each_entry()宏,与list_for_each()不同,这里的pos是数据项结构指针类型,而不是(struct list_head *)。

#define list_for_each_entry(pos, head, member)……

某些应用需要反向遍历链表,Linux提供了list_for_each_prev()和list_for_each_entry_reverse()来完成这一操作,使用方法和上面介绍的list_for_each()、list_for_each_entry()完全相同。

三、 内核链表应用举例

双循环链表是linux内核常用的数据结构,这也是linux链表的一个非常有特色的地方。而涉及到链表的函数有链表的定义、链表头的初始化、链表的插入、链表的遍历、链表的删除和链表的回收。下面通过一个内核模块来说明链表的相关操作。

#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/init.h>
#include <linux/slab.h>
#include <linux/list.h>

MODULE_LICENSE("GPL");
MODULE_AUTHOR("David Xie");
MODULE_DESCRIPTION("List Module");
MODULE_ALIAS("List module");

//以上为内核模块的的头文件和模式固定的部分

struct student
{
   char name[100];
   int num;
   struct list_head list;
};

//以上是定义包含有的struct list_head 结构的数据结构

struct student *pstudent;//定义一个结构数组,用来存放数据,注意这里pstudent是数组指针,数组的大小由后面的kmalloc来分配!

struct student *tmp_student;//遍历时临时用来存放指向pstudent[i]的指针

struct list_head student_list;//定义链表头(是一个节点)

struct list_head *pos;//指向头结点的一个指针,会在list_for_each中说明

int mylist_init(void)
{
   int i = 0;
   INIT_LIST_HEAD(&student_list);//初始化链表头,注意参数是一个指针,用了&符号

pstudent = kmalloc(sizeof(struct student)*5,GFP_KERNEL);//为结构体数组分配空间,共有5个数组成员
   memset(pstudent,0,sizeof(struct student)*5);//初始化结构体数组
   for(i=0;i<5;i++)//建立链表
   {
      sprintf(pstudent[i].name,"Student%d",i+1);//初始化并显示学生姓名
      pstudent[i].num = i+1; //初始化学生号码
      list_add( &(pstudent[i].list), &student_list);//将pstudent[i].list节点插入到student_list链表中,注意这里是从头结点处插入的,最后顺序为   5、4、3、2、1
   }
list_for_each(pos,&student_list)//遍历链表,此函数指明pos是一个指向节点头的指针,前面已经定义了它的类型。遍历函数相当于一个for循环,{ }内为循环操作,没循环一次pos=&student_list+1!
{
   tmp_student = list_entry(pos,struct student,list);//list_entry(提取数据结构)指针pos指向结构体struct student中的成员list,返回值为指向list所在的结构体的指针(起始地址)
   printk("<0>student %d name: %s\n",tmp_student->num,tmp_student->name);
}//输出此结构体(结构数组其中的一个成员)的数据信息
   return 0;
}

void mylist_exit(void)//删除节点

   int i ;
   for(i=0;i<5;i++)
{
   list_del(&(pstudent[i].list) );
}
   kfree(pstudent);//释放分配的内存
}

module_init(mylist_init);//内核模块模式固定的部分
module_exit(mylist_exit);//内核模块模式固定的部分

声明:本文是参考了网络上大量的文章写成的!!!

http://www.cnblogs.com/leon19870907/articles/2180529.html

http://hi.baidu.com/pleasehyj/item/918186b851ee55f063388ecd

http://qing.weibo.com/tj/6468794333000x2f.html

http://www.ibm.com/developerworks/cn/linux/kernel/l-chain/index.html

上一篇:[.net 面向对象编程基础] (7) 基础中的基础——流程控制语句


下一篇:Js的History对象