Linux内核中的链表

介绍

Linux的链表(Linked list)和很多其他的实现很不一样。通常来说,一个链表结构体会包含需要相互连接的数据,例如:

1
2
3
4
5
struct my_list {
void *my_item;
struct my_list *next;
struct my_list *prev;
}

Linux内核的实现仅仅定义个了一个简单的结构体list_head,它是个双向链表:

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

使用时,直接将它作为结构体的一个成员变量:

1
2
3
4
5
struct my_cool_list {
struct list_head list; /* kernel's list structure */
int my_cool_data;
void *my_cool_void;
};

看起来就好像是链表包含在它所连接的数据中!这样做的好处在于,你不用为每一种需要相互连接的数据类型都定义一个结构体,只需要将该数据类型“捆绑”在该链表上即可。

使用方法

内核中链表的实现在include/linux/list.h文件中。这里有一个精简的可用版本

下面有一个使用示例(文件来源:test_list.c):

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
#include <stdio.h>
#include <stdlib.h>
#include "list.h"
struct kool_list {
int to;
struct list_head list;
int from;
};
int main(int argc, char **argv)
{
struct kool_list *tmp;
struct list_head *pos, *q;
unsigned int i;
struct kool_list mylist;
INIT_LIST_HEAD(&mylist.list); // 初始化list
// 为mylist添加元素
for (i = 5; i != 0; --i) {
// 动态分配对象,使用用户的输入初始化该对象
tmp = (struct kool_list *)malloc(sizeof(struct kool_list));
printf("enter to and from: ");
scanf("%d %d", &tmp->to, &tmp->from);
// 将新对象tmp加入到mylist中,也可以使用list_add_tail()添加到末尾
list_add(&(tmp->list), &(mylist.list));
}
printf("\n");
// list_for_each()是一个宏,用于循环
// 参数1:用于循环计数,指向当前对象的list成员
// 参数2:指向链表的指针
printf("traversing the list using list_for_each():\n");
list_for_each(pos, &mylist.list) {
// 如上所述,pos->next指向下一个对象的list成员而非我们关心的to和from,
// list_entry通过list变量的地址计算出数据结构kool_list的地址,通过该
// 地址引用to和from成员变量。该机制本文后面有详述
tmp = list_entry(pos, struct kool_list, list);
printf("to = %d from = %d\n", tmp->to, tmp->from);
}
printf("\n");
// 使用list_for_each_entry()更方便
printf("traversing the list using list_for_each_entry()\n");
list_for_each_entry(tmp, &mylist.list, list)
printf("to = %d from = %d\n", tmp->to, tmp->from);
printf("\n");
// 需要删除或者移动对象时,需要使用更安全的list_for_each_safe()
printf("deleting the list using list_for_each_safe(): \n");
list_for_each_safe(pos, q, &mylist.list) {
tmp = list_entry(pos, struct kool_list, list);
printf("free item to = %d from = %d\n", tmp->to, tmp->from);
list_del(pos);
free(tmp);
}
return 0;
}

test_list.clist.h放到同一个目录下,编译运行即可。上面的代码只展示了基本功能,想了解更多的用法请阅读源码。

实现机制

该实现的核心在于list_entry这个宏定义:

1
2
#define list_entry(ptr, type, member) \
((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))

上面示例中的宏调用展开如下:

1
((struct kool_list *)((char *)(pos) - (unsigned long)(&((struct kool_list *)0)->list)))

给出链表结构体struct list_head的地址pos,宏定义list_entry计算出了包含该链表成员的结构体struct kool_list的地址。首先必须得到成员list在结构体中的位置(内存偏移),然后根据该偏移量计算出结构体的地址。

list_entry

现在的问题是,这个偏移量是如何得到的。假设有一个结构体struct foo_bar,下面的表达式计算成员boo在结构体中的偏移:

1
(unsigned long)(&((struct foo_bar *)0)->boo)

将内存地址0转换成我们想要的类型struct foo_bar,然后得到我们感兴趣的成员的地址,也就是该成员在结构体中的偏移量。我们已经知道了这个成员在结构体实例中的绝对地址(即pos),于是可以推算出结构体实例的地址。下面的测试代码(文件来源:compute_offset.c)验证了这一点:

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
#include <stdio.h>
#include <stdlib.h>
struct foobar {
unsigned int foo;
char bar;
char boo;
};
int main(int argc, char** argv)
{
struct foobar tmp;
printf("address of &tmp is= %p\n\n", &tmp);
printf("address of tmp->foo= %p \t offset of tmp->foo= %lu\n",
&tmp.foo, (unsigned long) &((struct foobar *)0)->foo);
printf("address of tmp->bar= %p \t offset of tmp->bar= %lu\n",
&tmp.bar, (unsigned long) &((struct foobar *)0)->bar);
printf("address of tmp->boo= %p \t offset of tmp->boo= %lu\n\n",
&tmp.boo, (unsigned long) &((struct foobar *)0)->boo);
printf("computed address of &tmp using:\n");
printf("address and offset of tmp->foo= %p\n",
(struct foobar *) (((char *) &tmp.foo) - ((unsigned long) &((struct foobar *)0)->foo)));
printf("address and offset of tmp->bar= %p\n",
(struct foobar *) (((char *) &tmp.bar) - ((unsigned long) &((struct foobar *)0)->bar)));
printf("address and offset of tmp->boo= %p\n",
(struct foobar *) (((char *) &tmp.boo) - ((unsigned long) &((struct foobar *)0)->boo)));
return 0;
}

编译运行得到如下结果:

1
2
3
4
5
6
7
8
9
10
address of &tmp is= 0x7ffcf635c9b0
address of tmp->foo= 0x7ffcf635c9b0 offset of tmp->foo= 0
address of tmp->bar= 0x7ffcf635c9b4 offset of tmp->bar= 4
address of tmp->boo= 0x7ffcf635c9b5 offset of tmp->boo= 5
computed address of &tmp using:
address and offset of tmp->foo= 0x7ffcf635c9b0
address and offset of tmp->bar= 0x7ffcf635c9b0
address and offset of tmp->boo= 0x7ffcf635c9b0

通过每个成员都能够计算出的结构体地址。因此,链表成员变量可以放在结构体中的任意位置。

参考

本文整理自:

  1. Linux Kernel Linked List Explained
  2. Linked Lists