linux 内核链表的实现_linux内核链表实现

    相比于普遍的链表实现方式，linux内核链表的实现方式可以说独树一帜。普遍的链表实现方式是在数据结构中嵌入链表指针，而linux内核链表的实现方式是将链表结点塞进数据结构里。
1.定义：（双向链表定义在<include/linux/list.h>中）

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

2.初始化头结点

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

#define LIST_HEAD(name) \
	struct list_head name = LIST_HEAD_INIT(name)
static inline void INIT_LIST_HEAD(struct list_head *list)
{
	list->next = list;
	list->prev = list;
}
1
2
3
4
5
6
7
8
9

(1) struct list_head name = LIST_HEAD_INIT(name) 等价于
   struct list_head name = { &(name), &(name) } 或
   struct list_head name = {
        .next = &(name),
         .prev = &(name),
   }
   由此可见，宏LIST_HEAD_INIT(name)将变量name初始化，并把prev，next都指向自身，如下图所示：
                                
   注：LIST_HEAD_INIT 与 INIT_LIST_HEAD的区别在于，前者定义并初始化结构体变量，后者通过一个内联函数初始结构的指针变量。
3.访问数据
    内核链表不同于普通链表的是，它是内嵌到数据对象中，这么说来，就是同类型的对象内部都嵌有这个链表，并且是通过这个链表穿针引线在一起，我们关心的是对象中的数据内容，那么究竟是如何通过对象内部的链表来访问其中的数据内容的呢？

#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)
1
2
3
4
5
6
7
8

(1) #define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER) 将0x0地址强制转换为TYPE类型，然后取TYPE的成员MEMBER地址。
   因为起始地址为0，得到的MEMBER的地址就直接是该成员相对于TYPE对象的偏移地址了。

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

(2) a.先看const typeof(((type *)0)->member)*__mptr = (ptr);首先将0x0转换为type类型的指针变量，再引用member成员，typeof(x)返回的是x的数据类型； 所以typeof(((type *)0)->member)返回的就是member成员的数据类型，该语句就是将__mptr强制转换为member成员的数据类型，然后再将ptr赋给它。
   b.接着(type *)((char *)__mptr - offsetof(type, member));先将__mptr强制转换为char*类型（因为char* 类型进行加减的话，加减量为sizeof(char)*offset，char占一个字节空间，这样指针加减的步长就是1个字节，实现加一减一。）然后减去type结构中member成员的地址偏移，得到type结构的地址，最后把该地址强制转换为type*类型。
   c.#define list_entry(ptr, type, member) container_of(ptr, type, member) 该宏定义作为右值，返回type类型对象的地址。
   type->member，表明member是type中的成员，所以可以得知member是内嵌的链表，type则是对象指针，那么ptr是链表类型指针，并且是属于那个穿针引线的链表中的某一个链表节点，所有的对象结构都挂在ptr所在的链表上。
    该宏定义可以返回ptr对应链表节点的对象的地址。关键是对应，找到的对象的地址是ptr这个链表所对应的那个对象的地址。ptr和member之间的关系就是，ptr是member类型的指针。
4.插入结点

static inline void __list_add(struct list_head *new,
			      struct list_head *prev,
			      struct list_head *next)
{
	next->prev = new;
	new->next = next;
	new->prev = prev;
	prev->next = new;
}

static inline void list_add(struct list_head *new, struct list_head *head)
{
	__list_add(new, head, head->next);
}

static inline void list_add_tail(struct list_head *new, struct list_head *head)
{
	__list_add(new, head->prev, head);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

(1)static inline void __list_add(struct list_head *new, struct list_head *prev,struct list_head *next) 在prev与next之间插入结点new，如下图所示。

(2)static inline void list_add(struct list_head *new, struct list_head *head)在head头结点之后插入new新结点。
(3)static inline void list_add_tail(struct list_head *new, struct list_head *head)在head头结点之前插入new新结点。
5.删除结点

static inline void __list_del(struct list_head * prev, struct list_head * next)
{
	next->prev = prev;
	prev->next = next;
}


static inline void list_del(struct list_head *entry)
{
	__list_del(entry->prev, entry->next);
	entry->next = LIST_POISON1;
	entry->prev = LIST_POISON2;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

(1)static inline void __list_del(struct list_head * prev, struct list_head * next) 用于删除prev与next之间的结点，其中
next->prev = prev;prev->next = next;如下图所示。

(2) static inline void list_del(struct list_head *entry) 删除指定结点entry。其中LIST_POISON1、LIST_POISON2
   在/include/linux/poison.h被定义。
   问题：为什么不把entry->next、entry->prev设置为NULL，而是置为LIST_POISON1和LIST_POISON2？
   答：LIST_POISON1和LIST_POISON2宏的作用：这些非NULL的指针会在普通环境中产生page faults， 从而被用作验证是否所有的链表节点都已经被初始化。(以下是源码的注释)

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

6.替换结点

/**
 * list_replace - replace old entry by new one
 * @old : the element to be replaced
 * @new : the new element to insert
 *
 * If @old was empty, it will be overwritten.
 */
//调整指针，使new的前后指针指向old的前后，反过来old的前后指针也指向new
static inline void list_replace(struct list_head *old,
				struct list_head *new)
{
	new->next = old->next;
	new->next->prev = new;
	new->prev = old->prev;
	new->prev->next = new;
}
//替换元素，最后将old初始化一下，不然old还是指向原来的两个前后节点（虽然人家不指向他）
static inline void list_replace_init(struct list_head *old,
					struct list_head *new)
{
	list_replace(old, new);
	INIT_LIST_HEAD(old); //把old->next = old;old->prev = old;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

7.移动结点

/**
 * list_move - delete from one list and add as another's head
 * @list: the entry to move
 * @head: the head that will precede our entry
 */
static inline void list_move(struct list_head *list, struct list_head *head)
{
	__list_del(list->prev, list->next);//删除list结点
	list_add(list, head);//把list结点添加道head结点之后
}
/**
 * list_move_tail - delete from one list and add as another's tail
 * @list: the entry to move
 * @head: the head that will follow our entry
 */
static inline void list_move_tail(struct list_head *list,
				  struct list_head *head)
{
	__list_del(list->prev, list->next);//删除list结点
	list_add_tail(list, head);//把list结点添加道head之前(即链表的尾部)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

8.遍历链表

#define list_first_entry(ptr, type, member) \
	list_entry((ptr)->next, type, member)
1
2

(1)上面传入的ptr是将各个type对象串起来的链表的头指针，ptr->next 就是该链表的第一个节点。上面返回值就是挂载在第一个节点上的对象地址。对象结构就是像下面这样挂载在链表上，如下图：

访问第一个对象就是：

type *type_first_ptr = list_first_entry(type_list, type, list);
/*
	type_list为链表头指针，type为对象结构，list为type结构内的链表
*/
1
2
3
4

(2) 遍历所有数据对象就是：

#define list_for_each_entry(pos, head, member)				\
	for (pos = list_entry((head)->next, typeof(*pos), member);	\
	     prefetch(pos->member.next), &pos->member != (head); 	\
	     pos = list_entry(pos->member.next, typeof(*pos), member))
/*
实际上就是一个for循环，循环内部由用户自己根据需要定义
初始条件：pos = list_entry((head)->next, typeof(*pos), member); pos为第一个对象地址
终止条件：&pos->member != (head);pos的链表成员不为头指针，环状指针的遍历终止判断
递增状态：pos = list_entry(pos->member.next, typeof(*pos), member) pos为下一个对象地址
所以pos就把挂载在链表上的所有对象都给遍历完了。至于访问对象内的数据成员，有多少个，用来干嘛用，则由用户
根据自己需求来定义了。
*/
1
2
3
4
5
6
7
8
9
10
11
12

prefetch(x)其功能是数据的预先读取，当确认后继续要读取某内存的信息的时候，可以采用prefetch将这一块数据读取到cache之中，以便后继快速访问；如果后继读取的内容仅仅被访问一次，那么是否prefetch也就没有意义了。后继访问的内存单元多次被读写才有意义。对于上述的list操作，在循环内部往往还会访问next指向的structure的内容，因此访问多次是可以期待的。