linux list详解

在linux内核中list的使用很频繁,使用管理对象,下面来详细说明其用法。

1链表结构定义

首先看链表的定义,位于:include\linux\types.h

1 struct list_head {
2     struct list_head *next, *prev;
3 };

一般将该数据结构嵌入到其他的数据结构中,从而使得内核可以通过链表的方式管理新的数据结构,比如struct device中:

 1 struct device {
 2     struct device        *parent;
 3 
 4     struct device_private    *p;
 5 
 6     struct kobject kobj;
 7     ...
 8     struct list_head    devres_head;//嵌入的链表
 9 
10     struct klist_node    knode_class;
11     struct class        *class;
12     const struct attribute_group **groups;    /* optional groups */
13 
14     void    (*release)(struct device *dev);
15     struct iommu_group    *iommu_group;
16 }

 2 链表的定义和初始化

有两种方式来定义和初始化链表头:

(1)利用宏LIST_HEAD

(2)利用宏LIST_HEAD_INIT

例如定义链表mylist:

方法1:定义并初始化链表

LIST_HEAD(mylist);

方法2:先定义再初始化链表

struct list_head mylist;  // 定义一个链表

INIT_LIST_HEAD(&mylist); // 用INIT_LIST_HEAD函数初始化链表。

看宏LIST_HEAD就知道就是用宏INIT_LIST_HEAD

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

再看宏INIT_LIST_HEAD的定义:

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

定义的mylist链表,宏展开就是

 struct list_head mylist = { &(mylist), &(mylist) };

链表list_head结构只有两个成员:next和prev。next和prev都被赋值为链表mylist的地址,也就是说,链表初始化后next和prev都是指向自己的。

对于struct device 中嵌入的list成员devres_head的初始化如下这样:

struct device mydevice;
INIT_LIST_HEAD(&mydevice.list); //该函数简单地将list成员的prev和next指针指向自己。

所以链表结点在初始化时,就是将prev和next指向自己。对链表的初始化非常重要,因为如果使用一个未被初始化的链表结点,很有可能会导致内核异常。

3 list的操作:

对链表常用的操作,一般就是添加、删除、遍历等。内核还会有其他的操作,比如替换、移动等,但这些的操作一般都是以添加、删除等操作为基础完成的。

3.1 链表的添加

添加有两种:

(1)list_add 将一个新链表结点插入到一个已知结点的后面;

(2)list_add_tail 将一个新链表结点插入到一个已知结点的前面

看他们的定义:

 1 /**
 2  * list_add - add a new entry
 3  * @new: new entry to be added
 4  * @head: list head to add it after
 5  *
 6  * Insert a new entry after the specified head.
 7  * This is good for implementing stacks.
 8  */
 9 static inline void list_add(struct list_head *new, struct list_head *head)
10 {
11     __list_add(new, head, head->next);
12 }
13 
14 /**
15  * list_add_tail - add a new entry
16  * @new: new entry to be added
17  * @head: list head to add it before
18  *
19  * Insert a new entry before the specified head.
20  * This is useful for implementing queues.
21  */
22 static inline void list_add_tail(struct list_head *new, struct list_head *head)
23 {
24     __list_add(new, head->prev, head);
25 }

上面链表添加的两种方式是以不同的参数调用_list_add,看_list_add的定义

1 static inline void __list_add(struct list_head *new,
2                   struct list_head *prev,
3                   struct list_head *next)
4 {
5     next->prev = new;
6     new->next = next;
7     new->prev = prev;
8     prev->next = new;
9 }

_list_add函数将new结点插入到prev结点和next之间。

(1) list_add函数中以new、head、head->next为参数调用__list_add,将new结点插入到head和head->next之间,即是把new结点插入到已知结点head的后面。

 (2)list_add_tail函数则以new、head->prev、head为参数调用__list_add,将new结点插入到head->prev和head之间,即是把new结点插入到已知结点head的前面。

3.2 链表的删除

删除也是有两种方式:

(1)list_del 删除链表中的一个结点。

(2)list_del_init 删除链表中的一个结点,并初始化被删除的结点(使被删除的结点的prev和next都指向自己);

分别看它们的定义:

 1 static inline void list_del(struct list_head *entry)
 2 {
 3     __list_del(entry->prev, entry->next);
 4     entry->next = LIST_POISON1;
 5     entry->prev = LIST_POISON2;
 6 }
 7 
 8 /**
 9  * list_del_init - deletes entry from list and reinitialize it.
10  * @entry: the element to delete from the list.
11  */
12 static inline void list_del_init(struct list_head *entry)
13 {
14     __list_del_entry(entry);
15     INIT_LIST_HEAD(entry);
16 }

_list_del_entry

1 static inline void __list_del_entry(struct list_head *entry)
2 {
3     __list_del(entry->prev, entry->next);
4 }

所以两者都是调用了_list_del,让prev结点和next结点互相指向。

 1 /*
 2  * Delete a list entry by making the prev/next entries
 3  * point to each other.
 4  *
 5  * This is only for internal list manipulation where we know
 6  * the prev/next entries already!
 7  */
 8 static inline void __list_del(struct list_head * prev, struct list_head * next)
 9 {
10     next->prev = prev;
11     prev->next = next;
12 }

(1)list_del 函数中以entry->prev和entry->next为参数调用__list_del函数,使得entry结点的前、后结点绕过entry直接互相指向,然后将entry结点的前后指针指向LIST_POISON1和LIST_POISON2,从而完成对entry结点的删除。此函数中的LIST_POISON1和LIST_POISON2是内核的处理定义如下。一般删除entry后,应该让entry的prev和next指向NULL的。

1 /*
2  * These are non-NULL pointers that will result in page faults
3  * under normal circumstances, used to verify that nobody uses
4  * non-initialized list entries.
5  */
6 #define LIST_POISON1  ((void *) 0x00100100 + POISON_POINTER_DELTA)
7 #define LIST_POISON2  ((void *) 0x00200200 + POISON_POINTER_DELTA)

(2)list_del_init 函数将entry结点删除后,与_list_del不同的是:还会对entry结点初始化,使entry结点的prev和next都指向其自己。

4 链表在内核中的应用

list_for_each_entry

首先看定义,位于:include\linux\list.h

 1 /**
 2  * list_for_each_entry    -    iterate over list of given type
 3  * @pos:    the type * to use as a loop cursor.
 4  * @head:    the head for your list.
 5  * @member:    the name of the list_struct within the struct.
 6  */
 7 #define list_for_each_entry(pos, head, member)                 8     for (pos = list_entry((head)->next, typeof(*pos), member);     9          &pos->member != (head);     10          pos = list_entry(pos->member.next, typeof(*pos), member))

 实际上是一个 for 循环,用传入的 pos 作为循环变量,从表头 head 开始,逐项向后(next 方向)移动 pos,一直到回到head.。

(1)变量的初始化:pos = list_entry((head)->next, typeof(*pos), member),每次pos拿到的都是链表中一个成员,注意这个成员实际上是一个结构体

(2)执行条件  &pos->member != (head),确定拿到的成员不是head,是head的话,表示list已遍历完。

(3)每循环一次执行 pos = list_entry(pos->member.next, typeof(*pos), member)),是pos指定链表中下一个成员,注意其实际上还是结构体

以上中用到typeof(),它是取变量的类型,这里是取指针pos所指向数据的类型。

4.1 看宏list_entry的定义:

1 /**
2  * list_entry - get the struct for this entry
3  * @ptr:    the &struct list_head pointer.
4  * @type:    the type of the struct this is embedded in.
5  * @member:    the name of the list_struct within the struct.
6  */
7 #define list_entry(ptr, type, member) 8     container_of(ptr, type, member)

4.2 调用了container_of。

 1 /**
 2  * container_of - cast a member of a structure out to the containing structure
 3  * @ptr:    the pointer to the member.
 4  * @type:    the type of the container struct this is embedded in.
 5  * @member:    the name of the member within the struct.
 6  *
 7  */
 8 #define container_of(ptr, type, member) ({             9     const typeof( ((type *)0)->member ) *__mptr = (ptr);    10     (type *)( (char *)__mptr - offsetof(type,member) );})

container_of是根据一个结构体变量中的一个成员变量指针ptr,来获取指向这个结构体变量type的指针。member是结构体type中成员ptr的变量名。下面分解一步一步分析:

4.2.1 先分析第一句:const typeof( ((type *)0)->member ) *__mptr = (ptr);  

(1)(type *)0) 将0强转为一个地址,这个地址(0x0000)指向的是类型type的数据,就是指向结构体。当然,这只是个技巧,并不是真的在地址0x0000存放了数据。

(2)((type *)0)->member :‘->’是指针指取结构体成员的操作。指针就是刚才通过0强转的地址,即结构体指针。相当于地址0x0000 是结构体类型type的首地址,通过->’取其中的成员变量member。

(3)typeof( ((type *)0)->member ) *__mptr = (ptr):拿到了member成员的类型,然后定义一个指针变量__mptr,指向的类型就是结构体成员member的类型,初始化值为ptr。

4.2.2 再分析第二句:(type *)( (char *)__mptr - offsetof(type,member) );

(1)offsetof(type,member) : 定义如下:

#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)

((TYPE *)0) :将整型常量0强制转换为TYPE型的指针,即结构体类型。且这个指针指向的地址为0,也就是将地址0开始的一块存储空间映射为TYPE型的对象。

((TYPE *)0)->MEMBER :指向结构体中MEMBER成员。

&((TYPE *)0)->MEMBER):对结构体中MEMBER成员进行取址,而整个TYPE结构体的首地址是0,这里获得的地址就是MEMBER成员在TYPE中的相对偏移量。

(size_t) &((TYPE *)0)->MEMBER:最后将这个偏移量强制转换成size_t型数据也就是无符号整型。   

所以offsetof的作用就是求出结构体成员变量member在结构体中的偏移量。

(2)(char *)__mptr - offsetof(type,member):member类型的指针减去member在结构体中的偏移量,就是结构体的起始位置,即指向结构体。

至此综上所述,list_entry 也就是container_of的作用就是:根据结构体中的成员变量和此变量的指针,拿到结构体的指针。

4.3 再回到list_for_each_entry

1 #define list_for_each_entry(pos, head, member)                2     for (pos = list_entry((head)->next, typeof(*pos), member);    \//链表中的成员也是结构体,根据结构体成员head->next获取此链表成员
3          &pos->member != (head);     \                             //确认此时拿到的链表成员不是链表的头成员
4          pos = list_entry(pos->member.next, typeof(*pos), member))//获取链表中下一个成员结构体

 list_for_each_entry在内核中的应用也很常见,通常用于遍历某一个链表。

linux list详解

上一篇:ubuntu14.04/16.04/18.04镜像下载


下一篇:私人订制属于自己的Linux系统