内核链表源码分析

Linux 内核链表不是“数据节点里保存下一个数据节点”，而是“数据结构里嵌入一个通用链表节点”

  1. 先理解普通链表为什么不够用
  2. 再理解 Linux 内核链表到底反过来了什么
  3. 重点讲 list_head、链表头、节点之间怎么连
  4. 重点讲 container_of 为什么能从小结构找到大结构

一、普通链表怎么写

最容易想到的链表是这样的：

1
2
3
4
5
struct student {
    int id;
    char name[20];
    struct student *next;
};

也就是说：

1
struct student *next;

指向下一个学生节点。

所以普通链表大概是：

1
student1 ---> student2 ---> student3 ---> NULL

这种写法很直观，但是问题也很明显。

如果现在不是学生，而是进程：

1
2
3
4
struct task {
    int pid;
    struct task *next;
};

那又要给 task 写一套链表操作。

如果又有文件结构体：

1
2
3
4
struct file {
    int fd;
    struct file *next;
};

又要写一套。

所以普通链表的问题是：

1
链表操作和具体数据类型绑定太死。

student 的链表只能操作 student，task 的链表只能操作 task。

二、Linux 内核链表的思路

Linux 内核不这样设计。

它先定义一个最通用的链表节点：

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

这个结构体里面没有 id，没有 name，没有 pid，没有任何业务数据。

它只负责一件事：

1
把节点前后连接起来。

所以 struct list_head 可以理解成一个“挂钩”。

三、Linux 链表不是“数据里指向数据”，而是“数据里嵌入挂钩”

比如我们定义学生：

1
2
3
4
5
struct student {
    int id;
    char name[20];
    struct list_head list;
};

注意这里：

1
struct list_head list;

不是指针，而是一个成员。

也就是说，每一个 student 对象里面，都自带一个链表挂钩。

可以想象成：

1
2
3
4
5
6
7
+-----------------------------+
| struct student              |
|                             |
| id                          |
| name                        |
| list  <--- 链表挂钩          |
+-----------------------------+

如果有三个学生：

1
2
3
struct student s1;
struct student s2;
struct student s3;

它们内部都有自己的 list：

1
2
3
s1.list
s2.list
s3.list

Linux 链表真正连接的是：

1
s1.list <--> s2.list <--> s3.list

不是直接连接：

1
s1 <--> s2 <--> s3

这一点非常重要。

四、Linux 内核链表是双向循环链表

struct list_head 里面有两个指针：

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

所以它是双向链表。

1
2
next 指向后一个节点
prev 指向前一个节点

而且 Linux 内核链表通常是循环链表。

也就是说，它不是这样：

1
head <--> node1 <--> node2 <--> node3 --> NULL

而是这样：

1
2
3
4
5
6
7
        +-----------------------------+
        |                             |
        v                             |
head <--> node1 <--> node2 <--> node3
^                                  |
|                                  |
+----------------------------------+

更简单地写：

1
head <--> node1 <--> node2 <--> node3 <--> head

链表尾部不会指向 NULL，而是重新指回 head。

五、链表头 head 是什么

Linux 内核链表通常会先定义一个链表头：

1
LIST_HEAD(student_list);

这个 student_list 本身也是一个：

1
struct list_head

但是它不是某个学生的数据，它只是一个头节点。

空链表时：

1
2
student_list.next = &student_list
student_list.prev = &student_list

也就是：

1
2
3
4
5
6
7
8
+----------------+
| student_list   |
| next ----------|----+
| prev ----------|----+
+----------------+    |
        ^             |
        |             |
        +-------------+

空链表可以理解为：

1
head 自己指向自己

所以空链表不是 NULL，而是：

1
2
head->next == head
head->prev == head

这是 Linux 内核链表很重要的特点。

六、加入第一个节点

假设有一个学生：

1
struct student s1;

它里面有：

1
s1.list

现在执行：

1
list_add_tail(&s1.list, &student_list);

意思是：

1
把 s1.list 插入到 student_list 这个链表的尾部。

插入之后：

1
student_list <--> s1.list <--> student_list

也就是：

1
2
3
4
5
head.next = &s1.list
head.prev = &s1.list

s1.list.next = &head
s1.list.prev = &head

可以这样记：

1
2
3
链表头 head 不存数据；
真正的数据藏在 s1 里面；
链上挂的是 s1.list。

七、加入多个节点

继续加入 s2、s3：

1
2
list_add_tail(&s2.list, &student_list);
list_add_tail(&s3.list, &student_list);

最终结构是：

1
student_list <--> s1.list <--> s2.list <--> s3.list <--> student_list

但是在内存里，每个 list 又藏在自己的结构体里面：

1
2
3
4
5
6
+--------------------+       +--------------------+       +--------------------+
| student s1         |       | student s2         |       | student s3         |
| id                 |       | id                 |       | id                 |
| name               |       | name               |       | name               |
| list <-------------+------>| list <-------------+------>| list               |
+--------------------+       +--------------------+       +--------------------+

所以一定要记住：

1
2
链表看到的是 list_head；
用户真正想要的是 struct student。

这就引出了 container_of。

八、为什么需要 container_of

遍历链表时，我们拿到的是：

1
struct list_head *pos;

比如 pos 指向的是：

1
&s1.list

但是我们真正想访问的是：

1
2
s1.id
s1.name

也就是说，我们需要从：

1
&s1.list

反推出：

1
&s1

这就是 container_of 的作用。

九、container_of 的本质

看这个结构体：

1
2
3
4
5
struct student {
    int id;
    char name[20];
    struct list_head list;
};

假设整个 student 对象的起始地址是：

1
0x1000

里面成员大概这样分布：

1
2
3
0x1000  id
0x1004  name
0x1018  list

那么：

1
&s1.list

可能是：

1
0x1018

但是 s1 的起始地址是：

1
0x1000

所以：

1
s1 的地址 = s1.list 的地址 - list 在 student 中的偏移量

也就是：

1
0x1000 = 0x1018 - 0x18

这就是 container_of 的核心思想。

它就是地址计算。

十、container_of 怎么用

它的形式是：

1
container_of(ptr, type, member)

含义是：

1
2
3
ptr：某个成员的地址
type：外层结构体类型
member：这个成员在外层结构体中的名字

例如：

1
2
3
struct student *stu;

stu = container_of(pos, struct student, list);

意思是：

1
2
pos 是 struct student 里面 list 成员的地址；
请根据这个 list 的地址，反推出整个 struct student 的地址。

所以：

1
container_of(pos, struct student, list)

可以从：

1
&s1.list

得到：

1
&s1

十一、list_entry 是什么

Linux 内核里还有一个宏：

1
list_entry(ptr, type, member)

它本质上就是对 container_of 的包装。

大概可以理解为：

1
2
#define list_entry(ptr, type, member) \
    container_of(ptr, type, member)

所以：

1
2
3
struct student *stu;

stu = list_entry(pos, struct student, list);

意思是：

1
通过 pos 这个 list_head 指针，找到它所在的 struct student。

十二、遍历链表怎么理解

最常用的遍历是：

1
2
3
4
5
struct student *stu;

list_for_each_entry(stu, &student_list, list) {
    printf("%d %s\n", stu->id, stu->name);
}

这个宏看起来复杂，但是可以按中文理解：

1
list_for_each_entry(stu, &student_list, list)

意思是：

1
2
3
4
遍历 student_list 这条链表；
每个大节点的类型是 struct student；
链表成员的名字叫 list；
每次遍历出来的学生对象放到 stu 里。

所以参数分别是：

1
2
3
stu              遍历出来的结构体指针
&student_list    链表头
list             struct student 里面的链表成员名

公式模板：

1
2
3
4
5
struct xxx *pos;

list_for_each_entry(pos, &head, member) {
    // 使用 pos->xxx
}

比如学生：

1
2
3
4
5
struct student *stu;

list_for_each_entry(stu, &student_list, list) {
    printf("%d\n", stu->id);
}

比如进程：

1
2
3
4
5
struct my_task *task;

list_for_each_entry(task, &task_list, list) {
    printf("%d\n", task->pid);
}

十三、list_add 和 list_add_tail 的区别

1. list_add

1
list_add(&new->list, &head);

表示把新节点插入到链表头后面。

也就是头插法。

原来：

1
head <--> A <--> B <--> C <--> head

插入 new 后：

1
head <--> new <--> A <--> B <--> C <--> head

所以 list_add 会让新节点出现在最前面。

2. list_add_tail

1
list_add_tail(&new->list, &head);

表示把新节点插入到链表尾部。

原来：

1
head <--> A <--> B <--> C <--> head

插入 new 后：

1
head <--> A <--> B <--> C <--> new <--> head

所以 list_add_tail 保持插入顺序。

可以这样记：

1
2
list_add       头插，越新的越靠前
list_add_tail  尾插，先来的在前面

如果只是学习和写测试代码，建议先用：

1
list_add_tail

因为它更符合直觉。

十四、删除节点怎么理解

删除节点：

1
list_del(&stu->list);

假设链表是：

1
head <--> A <--> B <--> C <--> head

现在删除 B：

1
list_del(&B->list);

删除之后：

1
head <--> A <--> C <--> head

它本质上就是让：

1
2
A.next = C
C.prev = A

也就是说，跳过 B。

但是注意：

1
list_del(&stu->list);

只是把 stu->list 从链表里摘掉。

如果 stu 是 malloc 出来的，还需要：

1
free(stu);

也就是说：

1
2
list_del 只负责从链表断开；
free 才负责释放内存。

十五、删除时最容易出错的地方

如果一边遍历一边删除，不能随便用：

1
2
3
4
list_for_each_entry(pos, &head, list) {
    list_del(&pos->list);
    free(pos);
}

这样可能出问题。

因为遍历宏后面还需要通过当前节点找到下一个节点。把当前节点释放了，它可能就找不到下一个了。

这种情况应该用安全版本：

1
2
3
4
5
6
7
struct student *pos;
struct student *tmp;

list_for_each_entry_safe(pos, tmp, &student_list, list) {
    list_del(&pos->list);
    free(pos);
}

记忆方式：

1
2
3
只遍历，不删除：list_for_each_entry

边遍历，边删除：list_for_each_entry_safe

这个非常重要。

十六、完整例子：学生链表

示例代码

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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

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

#define INIT_LIST_HEAD(ptr) do { \
    (ptr)->next = (ptr);         \
    (ptr)->prev = (ptr);         \
} while (0)

#define LIST_HEAD(name) \
    struct list_head name = { &(name), &(name) }

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_tail(struct list_head *new,
                                 struct list_head *head)
{
    __list_add(new, head->prev, head);
}

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);
}

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

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

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

#define list_for_each_entry(pos, head, member)                  \
    for (pos = list_entry((head)->next, typeof(*pos), member);   \
         &pos->member != (head);                                \
         pos = list_entry(pos->member.next, typeof(*pos), member))

struct student {
    int id;
    char name[20];
    struct list_head list;
};

int main(void)
{
    LIST_HEAD(student_list);

    struct student *s1 = malloc(sizeof(struct student));
    struct student *s2 = malloc(sizeof(struct student));
    struct student *s3 = malloc(sizeof(struct student));

    s1->id = 1;
    strcpy(s1->name, "Alice");

    s2->id = 2;
    strcpy(s2->name, "Bob");

    s3->id = 3;
    strcpy(s3->name, "Cindy");

    INIT_LIST_HEAD(&s1->list);
    INIT_LIST_HEAD(&s2->list);
    INIT_LIST_HEAD(&s3->list);

    list_add_tail(&s1->list, &student_list);
    list_add_tail(&s2->list, &student_list);
    list_add_tail(&s3->list, &student_list);

    struct student *stu;

    list_for_each_entry(stu, &student_list, list) {
        printf("id = %d, name = %s\n", stu->id, stu->name);
    }

    list_del(&s2->list);
    free(s2);

    printf("After delete:\n");

    list_for_each_entry(stu, &student_list, list) {
        printf("id = %d, name = %s\n", stu->id, stu->name);
    }

    list_del(&s1->list);
    list_del(&s3->list);

    free(s1);
    free(s3);

    return 0;
}

这段代码的逻辑是：

1
2
3
4
5
6
1. 定义一个链表头 student_list
2. 创建三个 student 节点
3. 每个 student 里面都有一个 list_head 成员
4. 把 s1.list、s2.list、s3.list 挂到 student_list 上
5. 遍历链表时，通过 list_head 找回 student
6. 打印 student 的数据

测试脚本

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
# 编译：gcc -g3 -O0 -Wall -Wextra -std=gnu11 list_dbg.c -o list_dbg
# 执行：gdb -x list_dbg_fixed.gdb ./list_dbg

set pagination off
set print pretty on
set print address on
set print array on
set print null-stop on

define print_sep
    printf "==================================================\n"
end

define print_title
    printf "\n"
    print_sep
    printf "%s\n", $arg0
    print_sep
end

define print_node
    printf "%s 对象地址       = %p\n", $arg0, $arg1
    printf "%s.list 地址      = %p\n", $arg0, &$arg1->list
    printf "%s.list.next      = %p\n", $arg0, $arg1->list.next
    printf "%s.list.prev      = %p\n", $arg0, $arg1->list.prev
end

define print_list
    printf "当前链表中的所有学生:\n"
    set $node = student_list.next
    set $i = 0
    while $node != &student_list
        set $stu = (struct student *)((char *)$node - $list_off)
        printf "  [%d] student=%p  list=%p  id=%d  name=%s  next=%p  prev=%p\n", $i, $stu, &$stu->list, $stu->id, $stu->name, $stu->list.next, $stu->list.prev
        set $node = ((struct list_head *)$node)->next
        set $i = $i + 1
    end
end

# 注意：如果的代码行号不同，需要修改这三个断点
# 88：INIT_LIST_HEAD 全部完成之后，第一次 list_add_tail 之前
# 92：三个 list_add_tail 全部完成之后
# 99：list_del(&s2->list) 之后，free(s2) 之前

b 88
b 92
b 99

run

print_title "阶段1: 初始化完成后，查看关键变量基础地址"

set $list_off = (long)&((struct student *)0)->list

printf "offsetof(struct student, list) = %ld, 0x%lx\n", $list_off, $list_off
printf "sizeof(struct list_head) = %ld\n", (long)sizeof(struct list_head)
printf "sizeof(struct student)   = %ld\n", (long)sizeof(struct student)

printf "\n链表头 student_list 的地址:\n"
printf "&student_list     = %p\n", &student_list
printf "student_list.next = %p\n", student_list.next
printf "student_list.prev = %p\n", student_list.prev

printf "\n指针变量本身的地址，位于栈上:\n"
printf "&s1 = %p\n", &s1
printf "&s2 = %p\n", &s2
printf "&s3 = %p\n", &s3

printf "\nmalloc 分配的堆内存地址，也就是 struct student 起始地址:\n"
printf "s1 = %p\n", s1
printf "s2 = %p\n", s2
printf "s3 = %p\n", s3

print_title "阶段2: student 结构体内存布局，以 s1 为例"

printf "s1              = %p\n", s1
printf "&s1->id         = %p\n", &s1->id
printf "&s1->name       = %p\n", &s1->name
printf "&s1->list       = %p\n", &s1->list
printf "s1 + list偏移量 = %p\n", (char *)s1 + $list_off

print_title "阶段3: 初始化后的节点状态"

print_node "s1" s1
printf "\n"
print_node "s2" s2
printf "\n"
print_node "s3" s3

continue

print_title "阶段4: 添加所有节点后的完整链表连接"

printf "head 地址 = %p\n", &student_list
printf "head.next = %p\n", student_list.next
printf "head.prev = %p\n", student_list.prev

printf "\n"
print_node "s1" s1
printf "\n"
print_node "s2" s2
printf "\n"
print_node "s3" s3

printf "\n"
print_list

print_title "阶段5: 验证 container_of 的工作原理"

printf "已知 &s1->list              = %p\n", &s1->list
printf "手动计算出来的 s1 地址      = %p\n", (struct student *)((char *)&s1->list - $list_off)
printf "真实的 s1 地址              = %p\n", s1

printf "\n解释:\n"
printf "container_of 的本质就是:\n"
printf "结构体起始地址 = 成员地址 - 成员在结构体中的偏移量\n"

print_title "阶段6: 查看 s1 原始内存"

printf "按字节查看 40 字节，包括 id、name、list.next、list.prev:\n"
x/40xb s1

printf "\n按 8 字节查看 5 组数据:\n"
x/5gx s1

delete 2

continue

print_title "阶段7: 删除 s2 节点后，free(s2) 之前"

printf "s1->list.next，现在应该指向 &s3->list:\n"
printf "s1->list.next = %p\n", s1->list.next
printf "&s3->list     = %p\n", &s3->list

printf "\ns3->list.prev，现在应该指向 &s1->list:\n"
printf "s3->list.prev = %p\n", s3->list.prev
printf "&s1->list     = %p\n", &s1->list

printf "\ns2 还没有 free，所以此时仍可观察 s2->list 的旧值:\n"
print_node "s2" s2

printf "\n删除后的链表遍历结果:\n"
print_list

print_title "自动调试完成"

printf "现在可以继续手动调试。\n"
printf "常用命令: n, s, p 变量, x/格式 地址, bt, q\n"

编译

1
gcc -g3 -O0 -Wall -Wextra -std=gnu11 list_dbg.c -o list_dbg

执行

1
gdb -x list_dbg_fixed.gdb ./list_dbg

输出结果

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
dku@dku:~/Desktop/list_head$ gdb -x list_dbg_fixed.gdb ./list_dbg
GNU gdb (Ubuntu 15.0.50.20240403-0ubuntu1) 15.0.50.20240403-git
Copyright (C) 2024 Free Software Foundation, Inc.
License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law.
Type "show copying" and "show warranty" for details.
This GDB was configured as "x86_64-linux-gnu".
Type "show configuration" for configuration details.
For bug reporting instructions, please see:
<https://www.gnu.org/software/gdb/bugs/>.
Find the GDB manual and other documentation resources online at:
    <http://www.gnu.org/software/gdb/documentation/>.

For help, type "help".
Type "apropos word" to search for commands related to "word"...
Reading symbols from ./list_dbg...
Breakpoint 1 at 0x1390: file list_dbg.c, line 88.
Breakpoint 2 at 0x13d5: list_dbg.c:92. (2 locations)
Breakpoint 3 at 0x1448: file list_dbg.c, line 99.

This GDB supports auto-downloading debuginfo from the following URLs:
  <https://debuginfod.ubuntu.com>
Enable debuginfod for this session? (y or [n]) [answered N; input not from terminal]
Debuginfod has been disabled.
To make this setting permanent, add 'set debuginfod enabled off' to .gdbinit.
[Thread debugging using libthread_db enabled]
Using host libthread_db library "/lib/x86_64-linux-gnu/libthread_db.so.1".

Breakpoint 1, main () at list_dbg.c:88
88          list_add_tail(&s1->list, &student_list);

==================================================
阶段1: 初始化完成后，查看关键变量基础地址
==================================================
offsetof(struct student, list) = 24, 0x18
sizeof(struct list_head) = 16
sizeof(struct student)   = 40

链表头 student_list 的地址:
&student_list     = 0x7fffffffdc20
student_list.next = 0x7fffffffdc20
student_list.prev = 0x7fffffffdc20

指针变量本身的地址，位于栈上:
&s1 = 0x7fffffffdbe8
&s2 = 0x7fffffffdbf0
&s3 = 0x7fffffffdbf8

malloc 分配的堆内存地址，也就是 struct student 起始地址:
s1 = 0x5555555592a0
s2 = 0x5555555592d0
s3 = 0x555555559300

==================================================
阶段2: student 结构体内存布局，以 s1 为例
==================================================
s1              = 0x5555555592a0
&s1->id         = 0x5555555592a0
&s1->name       = 0x5555555592a4
&s1->list       = 0x5555555592b8
s1 + list偏移量 = 0x5555555592b8

==================================================
阶段3: 初始化后的节点状态
==================================================
s1 对象地址       = 0x5555555592a0
s1.list 地址      = 0x5555555592b8
s1.list.next      = 0x5555555592b8
s1.list.prev      = 0x5555555592b8

s2 对象地址       = 0x5555555592d0
s2.list 地址      = 0x5555555592e8
s2.list.next      = 0x5555555592e8
s2.list.prev      = 0x5555555592e8

s3 对象地址       = 0x555555559300
s3.list 地址      = 0x555555559318
s3.list.next      = 0x555555559318
s3.list.prev      = 0x555555559318

Breakpoint 2.1, main () at list_dbg.c:94
94          list_for_each_entry(stu, &student_list, list) {

==================================================
阶段4: 添加所有节点后的完整链表连接
==================================================
head 地址 = 0x7fffffffdc20
head.next = 0x5555555592b8
head.prev = 0x555555559318

s1 对象地址       = 0x5555555592a0
s1.list 地址      = 0x5555555592b8
s1.list.next      = 0x5555555592e8
s1.list.prev      = 0x7fffffffdc20

s2 对象地址       = 0x5555555592d0
s2.list 地址      = 0x5555555592e8
s2.list.next      = 0x555555559318
s2.list.prev      = 0x5555555592b8

s3 对象地址       = 0x555555559300
s3.list 地址      = 0x555555559318
s3.list.next      = 0x7fffffffdc20
s3.list.prev      = 0x5555555592e8

当前链表中的所有学生:
  [0] student=0x5555555592a0  list=0x5555555592b8  id=1  name=Alice  next=0x5555555592e8  prev=0x7fffffffdc20
  [1] student=0x5555555592d0  list=0x5555555592e8  id=2  name=Bob  next=0x555555559318  prev=0x5555555592b8
  [2] student=0x555555559300  list=0x555555559318  id=3  name=Cindy  next=0x7fffffffdc20  prev=0x5555555592e8

==================================================
阶段5: 验证 container_of 的工作原理
==================================================
已知 &s1->list              = 0x5555555592b8
手动计算出来的 s1 地址      = 0x5555555592a0
真实的 s1 地址              = 0x5555555592a0

解释:
container_of 的本质就是:
结构体起始地址 = 成员地址 - 成员在结构体中的偏移量

==================================================
阶段6: 查看 s1 原始内存
==================================================
按字节查看 40 字节，包括 id、name、list.next、list.prev:
0x5555555592a0: 0x01    0x00    0x00    0x00    0x41    0x6c    0x69    0x63
0x5555555592a8: 0x65    0x00    0x00    0x00    0x00    0x00    0x00    0x00
0x5555555592b0: 0x00    0x00    0x00    0x00    0x00    0x00    0x00    0x00
0x5555555592b8: 0xe8    0x92    0x55    0x55    0x55    0x55    0x00    0x00
0x5555555592c0: 0x20    0xdc    0xff    0xff    0xff    0x7f    0x00    0x00

按 8 字节查看 5 组数据:
0x5555555592a0: 0x63696c4100000001      0x0000000000000065
0x5555555592b0: 0x0000000000000000      0x00005555555592e8
0x5555555592c0: 0x00007fffffffdc20
id = 1, name = Alice
id = 2, name = Bob
id = 3, name = Cindy

Breakpoint 3, main () at list_dbg.c:99
99          free(s2);

==================================================
阶段7: 删除 s2 节点后，free(s2) 之前
==================================================
s1->list.next，现在应该指向 &s3->list:
s1->list.next = 0x555555559318
&s3->list     = 0x555555559318

s3->list.prev，现在应该指向 &s1->list:
s3->list.prev = 0x5555555592b8
&s1->list     = 0x5555555592b8

s2 还没有 free，所以此时仍可观察 s2->list 的旧值:
s2 对象地址       = 0x5555555592d0
s2.list 地址      = 0x5555555592e8
s2.list.next      = 0x555555559318
s2.list.prev      = 0x5555555592b8

删除后的链表遍历结果:
当前链表中的所有学生:
  [0] student=0x5555555592a0  list=0x5555555592b8  id=1  name=Alice  next=0x555555559318  prev=0x7fffffffdc20
  [1] student=0x555555559300  list=0x555555559318  id=3  name=Cindy  next=0x7fffffffdc20  prev=0x5555555592b8

==================================================
自动调试完成
==================================================
现在可以继续手动调试。
常用命令: n, s, p 变量, x/格式 地址, bt, q

初始化后内存中的关系为：

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
s1 对象
0x5555555592a0
┌──────────────────────────────┐
│ id = 1                       │
│ name = "Alice"               │
│                              │
│ list                         │
│ 0x5555555592b8               │
│ next = 0x5555555592e8 ───────────────> s2->list
│ prev = 0x7fffffffdc20 ───────────────> student_list
└──────────────────────────────┘


s2 对象
0x5555555592d0
┌──────────────────────────────┐
│ id = 2                       │
│ name = "Bob"                 │
│                              │
│ list                         │
│ 0x5555555592e8               │
│ next = 0x555555559318 ───────────────> s3->list
│ prev = 0x5555555592b8 ───────────────> s1->list
└──────────────────────────────┘


s3 对象
0x555555559300
┌──────────────────────────────┐
│ id = 3                       │
│ name = "Cindy"               │
│                              │
│ list                         │
│ 0x555555559318               │
│ next = 0x7fffffffdc20 ───────────────> student_list
│ prev = 0x5555555592e8 ───────────────> s2->list
└──────────────────────────────┘

十七、可以这样背 Linux 链表的使用步骤

以后看到 Linux 内核链表，就按这五步走。

第一步：定义数据结构

1
2
3
4
5
struct student {
    int id;
    char name[20];
    struct list_head list;
};

记住：

1
数据结构里必须嵌入 struct list_head。

第二步：定义链表头

1
LIST_HEAD(student_list);

记住：

1
链表头不存数据，只是入口。

第三步：创建节点并初始化

1
2
3
4
5
6
struct student *stu = malloc(sizeof(struct student));

stu->id = 1;
strcpy(stu->name, "Alice");

INIT_LIST_HEAD(&stu->list);

记住：

1
初始化的是 stu->list，不是 stu。

第四步：插入链表

1
list_add_tail(&stu->list, &student_list);

记住：

1
插入的是 &stu->list，不是 stu。

这是很多初学者最容易忘的。

错误写法：

1
list_add_tail(stu, &student_list);

正确写法：

1
list_add_tail(&stu->list, &student_list);

因为链表操作函数只认识 struct list_head。

第五步：遍历链表

1
2
3
4
5
struct student *pos;

list_for_each_entry(pos, &student_list, list) {
    printf("%d\n", pos->id);
}

记住：

1
遍历出来的是 struct student *，不是 struct list_head *。

因为 list_for_each_entry 内部已经帮用了 container_of。

十八、最容易混淆的三个对象

一定要区分这三个东西。

1. 链表头

1
student_list

它的类型是：

1
struct list_head

它是链表入口，不保存学生数据。

2. 链表成员

1
stu->list

它的类型是：

1
struct list_head

它是嵌入在学生结构体里的挂钩。

3. 数据节点

1
stu

它的类型是：

1
struct student *

它才是真正保存数据的对象。

可以画成：

1
2
3
4
student_list
   |
   v
stu->list  ----反推出---->  stu

更完整一点：

1
2
3
链表头：       student_list
链表挂钩：     stu->list
真实数据：     stu->id, stu->name

十九、一句话记住 Linux 内核链表

1
2
3
Linux 内核链表把 list_head 嵌入到用户结构体中，
链表操作只连接 list_head，
需要访问数据时再通过 container_of 找回外层结构体。

这句话就是核心。

二十、几个常用宏的记忆表

宏/函数 作用 记忆方式
LIST_HEAD(name) 定义并初始化链表头 创建一个空链表
INIT_LIST_HEAD(ptr) 初始化一个 list_head 让它自己指向自己
list_add(new, head) 头插 插到 head 后面
list_add_tail(new, head) 尾插 插到 head 前面
list_del(entry) 删除节点 从链表摘掉
list_del_init(entry) 删除并重新初始化 摘掉后恢复单独状态
list_entry(ptr, type, member) 找外层结构体 从小成员找大结构
list_for_each_entry(pos, head, member) 遍历 遍历每个外层结构体
list_for_each_entry_safe(pos, tmp, head, member) 安全遍历 遍历时可以删除

二十一、代码模板

以后写 Linux 链表，就套这个。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
struct my_node {
    int data;
    struct list_head list;
};

LIST_HEAD(my_list);

struct my_node *node = malloc(sizeof(struct my_node));
node->data = 100;

INIT_LIST_HEAD(&node->list);

list_add_tail(&node->list, &my_list);

struct my_node *pos;

list_for_each_entry(pos, &my_list, list) {
    printf("%d\n", pos->data);
}

把它抽象成：

1
2
3
4
5
6
7
8
9
10
11
12
struct 类型名 {
    数据成员;
    struct list_head 链表成员名;
};

LIST_HEAD(链表头名);

list_add_tail(&节点->链表成员名, &链表头名);

list_for_each_entry(遍历指针, &链表头名, 链表成员名) {
    使用 遍历指针->数据成员;
}

二十二、口诀记忆

1
2
3
4
5
6
7
结构体里放 list，
链表头用 HEAD。
插入传 list 地址，
遍历给结构体指针。
删除用 list_del，
边删边遍历加 safe。
container_of 从成员找整体。

再压缩一点：

1
2
嵌入 list，挂到 head；
链上走 list，取数据靠 container_of。

二十三、最重要的理解图

脑子里形成这张图：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
struct student
+----------------------+
| id                   |
| name                 |
| list  <--------------+---- 链表真正连接这里
+----------------------+

struct student
+----------------------+
| id                   |
| name                 |
| list  <--------------+---- 链表真正连接这里
+----------------------+

struct student
+----------------------+
| id                   |
| name                 |
| list  <--------------+---- 链表真正连接这里
+----------------------+

链表关系是：

1
head <--> s1.list <--> s2.list <--> s3.list <--> head

但访问数据时要变成：

1
2
3
s1.list ----container_of----> s1
s2.list ----container_of----> s2
s3.list ----container_of----> s3

所以可以看到：

1
list_for_each_entry(stu, &student_list, list)

翻译成中文：

1
2
3
沿着 student_list 这条链上的每一个 list，
反推出它所在的 student，
然后把这个 student 交给 stu。

二十四、总结

第一，Linux 内核链表是双向循环链表。

第二，链表头 head 本身不保存数据，只是一个哨兵节点。

第三，真正挂到链表上的是结构体里面的：

1
struct list_head list;

第四，遍历时拿到的是 list_head，但最终要通过 container_of 找回外层结构体。

第五，Linux 内核链表的强大之处在于它是通用链表，任何结构体只要嵌入 struct list_head，就可以使用同一套链表操作函数。

1
2
3
4
5
6
struct list_head        负责连接
struct student          负责数据
container_of            从连接节点找回数据节点
list_add_tail           尾插
list_del                删除
list_for_each_entry     遍历

Linux 链表通过把通用的 list_head 嵌入到具体结构体中，实现了面向各种数据类型的通用链表操作。

许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。