源码阅读之旅，Linux 内核链表妙在哪？
本帖最后由 深藏功名丿小志 于 2024-12-24 22:34 编辑# 一、导读
自从上次刷了一题LeetCode `两数之和`后，我就去研读了 `uthash`的源码，对其链表的使用方法感到非常震撼。
随后，我又发现Linux内核链表的实现也采用了类似的思想。
接下来，我将和大家分享传统链表与Linux内核链表实现之间的差异。
# 二、传统链表结构
在C语言中，传统链表的实现通常如下所示：
```c
/**
* @Author:typedef公众号
*/
typedef struct Node {
int data; // 数据域
struct Node* prev; // 指向前一个节点的指针
struct Node* next; // 指向后一个节点的指针
} Node;
```
每个节点包含数据和指向上一个以及下一个节点的指针，还有一些用户数据。如下图所示：
从上述代码和结构可以看出，传统链表的缺点十分显著。其数据结构紧密依赖于特定的用户自定义结构体，缺乏通用性。
因为指针指向的用户区域结构体变化多样，所以链表的操作函数难以被重复利用，在不同的项目或模块中需要重复编写类似的操作逻辑，这极大地降低了开发效率。
# 三、Linux 内核链表结构
Linux 的链表结构设计为链表的指针直接指向用户结构体中的链表节点。例如：
```c
/**
* @Author:typedef公众号
*/
struct list {// 定义双向链表节点结构
struct list *prev;
struct list *next;
};
typedef struct {// 定义包含链表节点的结构体
int data;
struct list node;
} my_struct;
```
它将链表节点抽象出来，定义在一个通用的结构体 `struct list`中，数据结构如下图所示：
!(data/attachment/forum/202412/24/221711q4d2hxzn4ggf82kk.png "Linux list.png")
偷偷吐槽一下，画图看着简单实际好难，这两张图花了我一个小时...:
言归正传，咱继续分析...
那么问题来了，因为链表存放的都是 `struct list`类型对象，而用户数据是 `my_struct`类型对象，这样我不是获取不到用户对象了嘛？
而其中的精髓也就在此处，Linux 是通过 `container_of` 宏实现的，原型如下。
```c
/**
* 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.
*
* WARNING: any const qualifier of @PTR is lost.
*/
#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))); })
```
参数介绍：
* ptr：指向结构体成员的指针。
* type：包含该成员的结构体的类型。
* member：结构体中的成员名称。
这个宏的目的是根据结构体成员的地址获取该结构体的起始地址。实现的核心原理是利用指针运算和结构体成员的偏移量来获得结构体的起始地址。
假如有一个类型为 `my_struct`的 `user`对象，则 `container_of(&user.node, my_struct, node)`返回的对象就是 `user`。
我们再来看下内部是如何实现的。
> void *__mptr = (void *)(ptr);
第一行是将 `ptr`转换为 `void *`，后面再进行减法运算时，实际上是将指针当作 `char *`类型来处理（因为 `void *`在进行算术运算时会被转换为 `char *`类型），这样就可以按照字节为单位准确地减去成员在结构体中的偏移量，而不受原始成员指针类型的影响。
> static_assert(__same_type(*(ptr), ((type *)0)->member) ||
__same_type(*(ptr), void),
> "pointer type mismatch in container_of()");
第二行是一个静态断言，用于检查 `ptr`所指向的成员的类型是否与 `type`结构体中 `member`成员的类型相同，或者 `ptr`是否为 `void *`类型。如果不满足条件，编译时会产生错误提示 “pointer type mismatch in container_of ()”。
> ((type *)(__mptr - offsetof(type, member)));
第三行通过 `offsetof(type, member)`获取成员 `member`在结构体 `type`中的偏移量。然后将 `__mptr`转换为 `char *`类型指针，以便按字节进行减法运算，从成员的地址 `__mptr`中减去成员相对于结构体起始位置的偏移量，从而计算出整个结构体的首地址。最后，将结果转换为 `type *`类型的指针，表示整个结构体的首地址。
其中，`offsetof`宏用于计算结构体成员相对于结构体起始地址的偏移量，其定义如下：
```c
#define offsetof(TYPE, MEMBER) ((size_t)&((TYPE *)0)->MEMBER)
```
它的工作原理是：首先将 `0`强制转换为 `type *`类型的结构体指针（表示结构体起始地址为0），然后通过 `->MEMBER`访问该假设结构体的 `MEMBER`成员，此时 `MEMBER`的地址就是其相对于结构体开头的偏移量。
感觉这些代码写的好 `骚`哦，大为震撼，哈哈...
Linux内核链表结构提供了更高的通用性和操作复用性。通过将数据和节点解耦，我们可以在不同的数据结构中重用相同的链表操作，简化了代码的复杂度。
# 四、链接
* `https://github.com/torvalds/linux/blob/master/include/linux/container_of.h`
* `https://github.com/troydhanson/uthash`
# 五、最后
我把 `uthash` 源码放到文章目录 `六、附件`了，如果您也想阅读源码但没有梯子，可以直接下载，只要看 `example.c`以及 `uthash.h` 文件就行了。
我鼓励大家积极阅读源码，尽管过程中可能会遇到一些挑战和困难，但这也是锻炼思维和提升技能的宝贵机会。欢迎交流...
# 六、附件
[!(/source/plugin/zhanmishu_markdown/template/editor/images/upload.svg) 附件：uthash-master.zip](forum.html?mod=attachment&aid=2341264 "attachment")
感觉linux好复杂啊，很多都涉及在权限上了 yangjiaxu 发表于 2024-12-31 15:32
感觉linux好复杂啊，很多都涉及在权限上了
真正搞Linux开发的会喜欢，我们门外汉就感觉很复杂{:dizzy:} 和操作系统的列表很像啊 呐咯密密 发表于 2025-1-20 14:10
和操作系统的列表很像啊
也许就是一样的，没仔细看过源码 链表用熟了的话，就是一大利器，用不好的话，怎么崩的都不知道 飞思啦 发表于 2025-3-6 16:34
链表用熟了的话，就是一大利器，用不好的话，怎么崩的都不知道
说的太对了，不过这种都有封装好的接口。 非常棒 太强了吧 我尝试了一下，果然是这样！
++
非常棒++
非常棒 谢谢分享 我之前在项目中用过传统链表，确实存在操作函数难以复用的问题绝影孤狼 发表于 2025-3-12 10:05
我之前在项目中用过传统链表，确实存在操作函数难以复用的问题
尽量找第三方库去使用，不要重复造轮子了 Linux内核链表的实现方式确实很独特 深藏功名丿小志 发表于 2025-3-15 10:40
尽量找第三方库去使用，不要重复造轮子了
轮子还是要造的，工作还是要干的，鱼还是要摸的。
页:
[1]