内核的数据结构

2026年3月5日 · 约 10 分钟

链表

单向链表

struct list_element
{
    void* data;
    struct list_element *next;
}

双向链表

struct list_element
{
    void* data;
    struct list_element *next;
    struct list_element *prev;
}

linux中的链表

在 Linux 内核中，链表（Linked List）的实现和使用方式与我们在大学数据结构课程中常见的普通链表有着非常显著的区别。内核采用的是一种高度优化的侵入式双向循环链表（Intrusive Doubly Circular Linked List）。

这种设计定义在 <linux/list.h> 头文件中，它的核心思想是：不是在链表节点中包含数据，而是在数据结构中包含链表节点。

核心数据结构：list_head 内核提供了一个只包含指针、不包含任何业务数据的标准结构体：

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

你需要将这个 list_head 嵌入到你自己的自定义结构体中，而不是把你的数据放进链表节点里。所以也叫做侵入式

struct my_data {
    int id;
    char name[20];
    struct list_head list; /* 将链表节点嵌入到业务结构体中 */
};

链表的初始化

静态初始化（通常用于全局链表头）：

LIST_HEAD(my_list_head); 
// 这会声明一个名为 my_list_head 的 struct list_head，并将其 next 和 prev 指向自己。

动态/运行时初始化（通常用于结构体内部的链表头）：

struct list_head my_head;
INIT_LIST_HEAD(&my_head);

链表的增删改查

头插法（类似于栈）：

// 将 new 节点插入到 head 之后
list_add(struct list_head *new, struct list_head *head);

尾插法（类似于队列）：

// 将 new 节点插入到 head 之前（因为是循环链表，head 的 prev 就是尾部）
list_add_tail(struct list_head *new, struct list_head *head);

删除节点：

// 将 entry 从链表中移除，并将其指针指向安全的位置（通常是特殊的毒化地址 LIST_POISON1/2）
list_del(struct list_head *entry);

链表的遍历

既然链表里只有 next 和 prev 指针，当我们遍历链表时，如何获取包含这些指针的真实数据结构（如 struct my_data）呢？内核使用了一个非常著名的宏 container_of（封装在 list_entry 中）。它可以通过结构体成员的地址，利用指针偏移量反向计算出整个宿主结构体的首地址。

list_for_each_entry(pos, &my_list_head, list) {
    printk("ID: %d, Name: %s\n", pos->id, pos->name);
}

如果在遍历链表的过程中需要删除节点，必须使用带有 _safe 后缀的版本，否则会导致指针跑飞（Page Fault）：

struct my_data *pos, *n;
list_for_each_entry_safe(pos, n, &my_list_head, list) {
    if (pos->id == 5) {
        list_del(&pos->list);
        kfree(pos); // 释放内存
    }
}

list_for_each_entry_safe宏

list_for_each_entry_safe(curr, n, &person_list, list) {
    if (curr->age > 60) {
        // ...
    }
}

for (curr = list_first_entry(&person_list, typeof(*curr), list),
     n = list_next_entry(curr, list);
     &curr->list != (&person_list);
     curr = n, n = list_next_entry(n, list)) 
{  // <--- 注意看这里！这个大括号就是你写的那个大括号！
    
    if (curr->age > 60) {
        // ...
    }
    
}  // <--- 这是你写的右大括号！

container_of宏

普通的 C 语言里，大括号 {} 通常只能用来包裹代码块（比如 if、for 或者函数的内部），它本身是没有返回值的。

但在 Linux 内核代码（如 container_of）中看到的 ({ … }) 写法，其实不是标准的 C 语言语法，而是 GCC 编译器提供的一个特殊扩展功能，叫做语句表达式 (Statement Expressions)。

由于 Linux 内核重度依赖 GCC（以及兼容 GCC 扩展的 Clang），所以内核源码里几乎到处都是这种写法。

1. ({ … }) 是怎么工作的？

它的核心规则非常简单：包裹在 ({ 和 }) 内部的复合语句可以作为一个完整的表达式来使用，而整个表达式的值，就是大括号里面最后一条语句的值。

来看一个极简的例子：

int result = ({
    int a = 1;
    int b = 2;
    int sum = a + b;
    sum; // 这是最后一条语句，它的值将被作为整个 ({...}) 的返回值
});

// 最终 result 的值就是 3

2. 为什么内核的宏特别喜欢用 ({ … })？

如果仅仅是为了包裹代码，C 语言宏里常用的 do { … } while(0) 也能做到，但 do-while 不能作为表达式返回一个值！

({ … }) 在宏里面有着无可替代的三大优势：

优势一：完美解决多行代码的返回值问题在 container_of 宏里，内核需要先做类型检查，再做减法运算，最后把算出来的结构体指针返回。有了 ({ … })，最后一行强转后的指针地址，就顺理成章地变成了整个宏的返回值，可以直接赋值给外面的变量。

优势二：安全定义局部变量，避免命名冲突宏在预编译阶段只是纯粹的文本替换。如果在宏里直接定义变量，很容易和调用者原本代码里的变量重名，导致编译报错。有了 {}，这就形成了一个局部的作用域。比如 container_of 里面定义的局部指针 __mptr，它的生命周期和作用域只在这个 {} 内部，绝不会污染外面的代码。

队列

什么是 kfifo？ kfifo 是内核提供的一个高度优化的环形缓冲区（Ring Buffer），定义在 <linux/kfifo.h> 中。它主要用于在内核的两个子系统之间，或者中断上下文与普通上下文之间，安全、高效地传递字节流或记录。

普通的数组队列在不断入队、出队后，数据会不断向数组尾部移动，前面空出来的内存就被浪费了。环形缓冲区通过把数组“首尾相连”解决了这个问题。

kfifo 的核心魔法：位运算替代求模

我们在大学写环形队列时，计算指针走到数组尾部后如何“绕回”头部，通常会使用求模（取余）运算：next_index = (current_index + 1) % size;但在内核中，求模运算（%）是一条非常昂贵的 CPU 指令（除法指令）。对于追求极致性能的内核来说，这是不可接受的。内核大牛们是怎么优化的呢？他们定下了一个死规矩：kfifo 的容量（size）必须严格是 $2^n$ （2 的幂次方，如 1024, 2048, 4096…）。一旦容量是 $2^n$ ，求余数的操作就可以被极其廉价的按位与（Bitwise AND）操作完美替代： $x \pmod{size} \equiv x \ \& \ (size - 1)$

第二个魔法：单核无锁并发（Lockless）

kfifo 最牛的地方在于：在“一个生产者、一个消费者”（Single Producer, Single Consumer, SPSC）的场景下，它是完全无锁的！

它内部维护了两个毫无符号的整型变量：in（入队游标，一直往前加）和 out（出队游标，一直往前加）。

生产者只负责修改 in。

消费者只负责修改 out。

因为他们互不干扰对方的游标，只要通过内存屏障（Memory Barrier）确保 CPU 指令不会被乱序执行，就可以完美实现无锁（Lockless）的数据传递，这在网卡收发包等高频中断场景下是救命的性能保障

基本使用套路

内核封装了非常友好的宏来操作 `kfifo`：
#include <linux/kfifo.h>

// 1. 声明并初始化一个大小为 1024 字节的 kfifo
// 宏会自动帮你检查大小是否为 2 的幂次方
DEFINE_KFIFO(my_fifo, unsigned char, 1024);

// 或者动态分配
// struct kfifo my_fifo;
// kfifo_alloc(&my_fifo, 1024, GFP_KERNEL);

static int my_func(void) {
    unsigned char data_in = 'A';
    unsigned char data_out;

    // 2. 入队 (Put)：将数据放入队列
    kfifo_put(&my_fifo, data_in);

    // 3. 出队 (Get)：从队列中取出数据
    if (kfifo_get(&my_fifo, &data_out)) {
        printk("Got data: %c\n", data_out);
    }

    return 0;
}