源码阅读之旅，Linux 内核链表妙在哪？

只看该作者 · 2024-12-24 22:34

[i=s] 本帖最后由深藏功名丿小志于 2024-12-24 22:34 编辑 [/i]<br /> <br />

一、导读

自从上次刷了一题LeetCode 两数之和后，我就去研读了 uthash的源码，对其链表的使用方法感到非常震撼。

随后，我又发现Linux内核链表的实现也采用了类似的思想。

接下来，我将和大家分享传统链表与Linux内核链表实现之间的差异。

二、传统链表结构

在C语言中，传统链表的实现通常如下所示：

/**
 * @Author:typedef公众号
 */
typedef struct Node {
  int data;              // 数据域
  struct Node* prev;     // 指向前一个节点的指针
  struct Node* next;     // 指向后一个节点的指针
} Node;

每个节点包含数据和指向上一个以及下一个节点的指针，还有一些用户数据。如下图所示：

传统链表结构.png

从上述代码和结构可以看出，传统链表的缺点十分显著。其数据结构紧密依赖于特定的用户自定义结构体，缺乏通用性。

因为指针指向的用户区域结构体变化多样，所以链表的操作函数难以被重复利用，在不同的项目或模块中需要重复编写类似的操作逻辑，这极大地降低了开发效率。

三、Linux 内核链表结构

Linux 的链表结构设计为链表的指针直接指向用户结构体中的链表节点。例如：

/**
 * @Author:typedef公众号
 */
struct list {  // 定义双向链表节点结构
  struct list *prev;
  struct list *next;
};

typedef struct {  // 定义包含链表节点的结构体
  int data;
  struct list node;
} my_struct;

它将链表节点抽象出来，定义在一个通用的结构体 struct list中，数据结构如下图所示：

偷偷吐槽一下，画图看着简单实际好难，这两张图花了我一个小时...:

言归正传，咱继续分析...

那么问题来了，因为链表存放的都是 struct list类型对象，而用户数据是 my_struct类型对象，这样我不是获取不到用户对象了嘛？

而其中的精髓也就在此处，Linux 是通过 container_of 宏实现的，原型如下。

/**
 * 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](home.php?mod=space&uid=199534) 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宏用于计算结构体成员相对于结构体起始地址的偏移量，其定义如下：

#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 文件就行了。

我鼓励大家积极阅读源码，尽管过程中可能会遇到一些挑战和困难，但这也是锻炼思维和提升技能的宝贵机会。欢迎交流...

六、附件

upload 附件：uthash-master.zip