Linux 内核的 list.h_list.h文件

0. Linux 的内核的数据结构，应该属 list.h 中的 list_head 最重要、最常见。

• list_head是一个双向的，带有伪头部（哨兵）的 双向环形链表。
• 这个双向链表的每个节点的类型可以不一样

应用：

1. 内核的定时器使用链表的话，包括用户态的定时器，都会首选 list_head。
2. list_head 虽然是内核的数据结构，但是比较特殊，将它复制到用户态，也可以直接用 gcc 编译通过运行。
3. 之前在看 openwrt 中有一个 uloop 的用户态的库，就是使用 list_head

说在前面：

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

这个宏就是为了计算下面的 size,原理：将地址 0 的位置强制标记为结构体指针的类型，那么它的member成员变量所对应的地址就是size的值。

那么我们经常看到的 contain_of 这个宏就好解释了：

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

• 中间的那行：ptr 是 member 的指针，是一个指针赋值，将 ptr 指针赋值给 __mptr
• 最后面的一行：因为 offsetof(type,member) 计算了 size 的值，而__mptr记录着 member 的地址，它往前移动size的值就是结构体开始的地址，再将它强制转为为结构体的指针类型，就得到了我们想要的结构体。
• 那要 ptr 就可以，为什么要多一个中间变量__mptr？因为这是一个指针赋值给指针，在 C 编译器，指针赋值给指针，如果两边的指针类型不匹配，需要强制将右值的指针的类型进行手动转换，否则会报错！这个就是一个检验报错的机制。

typeof( ((type *)0)->member )
1

• 返回 member 的类型。在这里没有多余的意思。

1. 笔记

a. 结构体定义

结构体的成员是两个指针变量

// include/linux/types.h
struct list_head {
	struct list_head *next, *prev;
};
1
2
3
4

b. 初始化

// include/linux/list.h
/*
 * Simple doubly linked list implementation.
 *
 * Some of the internal functions ("__xxx") are useful when
 * manipulating whole lists rather than single entries, as
 * sometimes we already know the next/prev entries and we can
 * generate better code by using them directly rather than
 * using the generic single-entry routines.
 */

#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
10
11
12
13
14
15
16
17
18
19
20
21

上面三个都是初始化函数，创建一个结构体实例，这个结构体就是链表的头部。一般这个链表是不保存数据的，只是起一个哨兵的作用。实例中图示如下，创建一个结构体示例，类型为struct list_head，指针 prev 指向自身结构体（struct list_head）：

c. 链表的增

/*
 * 在 prev 和 next 之间插入一个节点 new
 */
#ifndef CONFIG_DEBUG_LIST
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;
}
#else
extern void __list_add(struct list_head *new,
			      struct list_head *prev,
			      struct list_head *next);
#endif

/**
 * 在链表头部（链表头）后面插入
 */
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
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

d. 链表的删

/*
 * 删除 prev 和 next 之间的节点（但是不释放内存）
 */
static inline void __list_del(struct list_head * prev, struct list_head * next)
{
	next->prev = prev;
	prev->next = next;
}

/**
 * 删除节点 entry ，但是不释放内存
 */
#ifndef CONFIG_DEBUG_LIST
static inline void __list_del_entry(struct list_head *entry)
{
	__list_del(entry->prev, entry->next);
}

/**
 * 删除节点 entry ，但是不释放内存
 * 同时设置 entry 的 prev, next 指针为非法
 */
static inline void list_del(struct list_head *entry)
{
	__list_del(entry->prev, entry->next);
	entry->next = LIST_POISON1;
	entry->prev = LIST_POISON2;
}
#else
extern void __list_del_entry(struct list_head *entry);
extern void list_del(struct list_head *entry);
#endif
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

e. 链表的查

前置内容：

// 一个包含 list_head 的结构体定义
struct ListNode
{
    int val;
    // list.h 内定义的核心结构体
    struct list_head mylist;
};

// 它的示例这样写：
struct ListNode first_node;
struct ListNode second_node;
1
2
3
4
5
6
7
8
9
10
11

• member：指成员变量，struct list_head 类型的名字——mylist
• type： 指包含 struct list_head 的结构体类型——struct ListNode
• ptr: 指已经实例化链表的节点的 strust list_head 的指针
• head：一般指链表的头节点中的 strust list_head 的指针
• pos：这个得看函数就是遍历的临时变量，类似于（for(pos = head; pos != NULL; pos = pos.next)），主要是区分类型。
  • 在 list_for_each_entry_safe 这样的函数，它的类型是链表节点的指针
  • 如果是list_for_each_safe它是 strust list_head 的指针

最常用的两个，遍历的是结构体（包含 struct list_head 和数据成员的结构体）：

/**
 * list_for_each_entry	-	iterate over list of given type
 * @pos:	the type * to use as a loop cursor.
 * @head:	the head for your list.
 * @member:	the name of the list_head within the struct.
 */
#define list_for_each_entry(pos, head, member)				\
	for (pos = list_first_entry(head, typeof(*pos), member);	\
	     &pos->member != (head);					\
	     pos = list_next_entry(pos, member))

/**
 * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry
 * @pos:	the type * to use as a loop cursor.
 * @n:		another type * to use as temporary storage
 * @head:	the head for your list.
 * @member:	the name of the list_head within the struct.
 */
#define list_for_each_entry_safe(pos, n, head, member)			\
	for (pos = list_first_entry(head, typeof(*pos), member),	\
		n = list_next_entry(pos, member);			\
	     &pos->member != (head); 					\
	     pos = n, n = list_next_entry(n, member))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

f. 一些技巧

• 如果全部使用 list_add：在哨兵节点后插入节点，可以作stack使用（先进后出）
• 如果全部使用list_add_tail：在哨兵节点前面插入节点，可以做queue使用（先进先出）

---

---

2. 一个例子

#include "list.h"
#include <stdio.h>

// 一个 entry 的结构体定义
struct ListNode
{
    int val;
    // list.h 内定义的核心结构体
    struct list_head mylist;
};

int main()
{
	// 初始化一个哨兵头节点
    LIST_HEAD(head_node);

    // 第一个有用节点
    struct ListNode first_node = 
    { 
        .val = 1,
        .mylist = LIST_HEAD_INIT(first_node.mylist)
    };
    list_add(&first_node.mylist, &head_node);
    printf("%d\n", first_node.val);
    
    // 第二个有用节点
    struct ListNode second_node = 
    { 
        .val = 2,
        .mylist = LIST_HEAD_INIT(second_node.mylist)
    };
    list_add(&second_node.mylist, &head_node);
    printf("%d\n", second_node.val);

	// 不能使用 for 循环，不然会造成死循环，还没有时间看为什么，估计是可以解决的
    // for (int i = 0; i < 5; i++)
    {
        struct ListNode node = 
        { 
            .val = 10,
            .mylist = LIST_HEAD_INIT(node.mylist)
        };
        list_add(&node.mylist, &head_node);
    }

	/* 	头文件宏下的  
	 *	@pos： entry 结构体的实例指针，
	 *	@head：一般正常地使用，就是哨兵节点的指针。如果自己使用一些奇淫技巧，那么就自己确定他的指针位置
	 *	@member：entry 结构体内的 struct list_head 的变量名
	*/
    struct ListNode *pos_ptr = NULL;
    list_for_each_entry(pos_ptr, &head_node, mylist)
    {
        printf("%d\n", pos_ptr->val);
    }

    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

2. 头文件源码（每个版本不一样）

• 文件直接从内核里导出来，可以在用户态使用。
• list.h

/* SPDX-License-Identifier: GPL-2.0 */
#ifndef LIST_H
#define LIST_H

#include <stdbool.h>
#include <stddef.h>

/* Are two types/vars the same type (ignoring qualifiers)? */
#define __same_type(a, b) __builtin_types_compatible_p(typeof(a), typeof(b))

/**
 * container_of - cast a member of a structure out to the containing structure
 * @ptr:	the pointer to the member.
 * @type:	the type of the container struct this is embedded in.
 * @member:	the name of the member within the struct.
 *
 */
#define container_of(ptr, type, member) ({				\
	void *__mptr = (void *)(ptr);					\
	_Static_assert(__same_type(*(ptr), ((type *)0)->member) ||	\
		      __same_type(*(ptr), void),			\
		      "pointer type mismatch in container_of()");	\
	((type *)(__mptr - offsetof(type, member))); })

#define LIST_POISON1  ((void *) 0x100)
#define LIST_POISON2  ((void *) 0x122)

/*
 * Circular doubly linked list implementation.
 *
 * Some of the internal functions ("__xxx") are useful when
 * manipulating whole lists rather than single entries, as
 * sometimes we already know the next/prev entries and we can
 * generate better code by using them directly rather than
 * using the generic single-entry routines.
 */

struct list_head {
	struct list_head *next, *prev;
};

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

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

/**
 * INIT_LIST_HEAD - Initialize a list_head structure
 * @list: list_head structure to be initialized.
 *
 * Initializes the list_head to point to itself.  If it is a list header,
 * the result is an empty list.
 */
static inline void INIT_LIST_HEAD(struct list_head *list)
{
	list->next = list;
	list->prev = list;
}

/*
 * Insert a new entry between two known consecutive entries.
 *
 * This is only for internal list manipulation where we know
 * the prev/next entries already!
 */
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;
}

/**
 * list_add - add a new entry
 * @new: new entry to be added
 * @head: list head to add it after
 *
 * Insert a new entry after the specified head.
 * This is good for implementing stacks.
 */
static inline void list_add(struct list_head *new, struct list_head *head)
{
	__list_add(new, head, head->next);
}

/**
 * list_add_tail - add a new entry
 * @new: new entry to be added
 * @head: list head to add it before
 *
 * Insert a new entry before the specified head.
 * This is useful for implementing queues.
 */
static inline void list_add_tail(struct list_head *new, struct list_head *head)
{
	__list_add(new, head->prev, head);
}

/*
 * Delete a list entry by making the prev/next entries
 * point to each other.
 *
 * This is only for internal list manipulation where we know
 * the prev/next entries already!
 */
static inline void __list_del(struct list_head *prev, struct list_head *next)
{
	next->prev = prev;
	prev->next = next;
}

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

/**
 * list_del - deletes entry from list.
 * @entry: the element to delete from the list.
 * Note: list_empty() on entry does not return true after this, the entry is
 * in an undefined state.
 */
static inline void list_del(struct list_head *entry)
{
	__list_del_entry(entry);
	entry->next = LIST_POISON1;
	entry->prev = LIST_POISON2;
}

/**
 * list_is_head - tests whether @list is the list @head
 * @list: the entry to test
 * @head: the head of the list
 */
static inline int list_is_head(const struct list_head *list, const struct list_head *head)
{
	return list == head;
}

/**
 * list_empty - tests whether a list is empty
 * @head: the list to test.
 */
static inline int list_empty(const struct list_head *head)
{
	return head->next == head;
}

/**
 * list_entry - get the struct for this entry
 * @ptr:	the &struct list_head pointer.
 * @type:	the type of the struct this is embedded in.
 * @member:	the name of the list_head within the struct.
 */
#define list_entry(ptr, type, member) \
	container_of(ptr, type, member)

/**
 * list_first_entry - get the first element from a list
 * @ptr:	the list head to take the element from.
 * @type:	the type of the struct this is embedded in.
 * @member:	the name of the list_head within the struct.
 *
 * Note, that list is expected to be not empty.
 */
#define list_first_entry(ptr, type, member) \
	list_entry((ptr)->next, type, member)

/**
 * list_next_entry - get the next element in list
 * @pos:	the type * to cursor
 * @member:	the name of the list_head within the struct.
 */
#define list_next_entry(pos, member) \
	list_entry((pos)->member.next, typeof(*(pos)), member)

/**
 * list_entry_is_head - test if the entry points to the head of the list
 * @pos:	the type * to cursor
 * @head:	the head for your list.
 * @member:	the name of the list_head within the struct.
 */
#define list_entry_is_head(pos, head, member)				\
	(&pos->member == (head))

/**
 * list_for_each_entry - iterate over list of given type
 * @pos:	the type * to use as a loop cursor.
 * @head:	the head for your list.
 * @member:	the name of the list_head within the struct.
 */
#define list_for_each_entry(pos, head, member)				\
	for (pos = list_first_entry(head, typeof(*pos), member);	\
	     !list_entry_is_head(pos, head, member);			\
	     pos = list_next_entry(pos, member))

/**
 * list_for_each_entry_safe - iterate over list of given type. Safe against removal of list entry
 * @pos:	the type * to use as a loop cursor.
 * @n:		another type * to use as temporary storage
 * @head:	the head for your list.
 * @member:	the name of the list_head within the struct.
 */
#define list_for_each_entry_safe(pos, n, head, member)			\
	for (pos = list_first_entry(head, typeof(*pos), member),	\
		n = list_next_entry(pos, member);			\
	     !list_entry_is_head(pos, head, member);			\
	     pos = n, n = list_next_entry(n, member))

#endif /* LIST_H */
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213