菜鸟-创作你的创作

linux内核双向链表详解

lichongyang

下面我用内核源码级 + 图解思维 + 面试/实战导向，系统地给你讲清楚
👉 Linux 内核双向链表（list_head）。
这是内核、驱动、操作系统面试必考点之一。

一、为什么 Linux 内核要自己实现双向链表？

内核不能使用 C 标准库，必须：

👉 所以内核设计了 侵入式双向链表（intrusive list）

二、核心数据结构：struct list_head

📁 源码位置：

include/linux/list.h

1️⃣ 定义

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

⚠️ 注意：

三、侵入式链表（重点理解）

1️⃣ 普通链表（用户态）

struct node {
    int data;
    struct node *next;
};

2️⃣ 内核侵入式链表

struct task_struct {
    int pid;
    struct list_head tasks;
};

📌 链表指针嵌入到业务结构中

四、链表初始化（非常重要）

1️⃣ 静态初始化

LIST_HEAD(my_list);

等价于：

struct list_head my_list = { &my_list, &my_list };

2️⃣ 动态初始化

struct list_head my_list;
INIT_LIST_HEAD(&my_list);

📌 空链表：
head.next == head.prev == &head

五、节点插入原理（源码级）

1️⃣ 内部核心函数

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

2️⃣ 头插 & 尾插

list_add(new, head);      // 头插
list_add_tail(new, head); // 尾插

🔍 本质：

list_add(new, head)        => __list_add(new, head, head->next)
list_add_tail(new, 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;
}


list_del(entry);

⚠️ 注意：

👉 驱动中必须配合 kfree()

七、container_of（灵魂级宏）

1️⃣ 宏定义

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

📌 作用：

通过 list_head* 找回外层结构体地址

2️⃣ 使用示例

struct task_struct *task;
task = list_entry(pos, struct task_struct, tasks);

本质：

container_of(pos, struct task_struct, tasks);

八、遍历链表（面试高频）

1️⃣ 普通遍历

struct list_head *pos;

list_for_each(pos, &my_list) {
    struct node *n = list_entry(pos, struct node, list);
}

2️⃣ 安全遍历（删除时必须用）

struct list_head *pos, *n;

list_for_each_safe(pos, n, &my_list) {
    list_del(pos);
}

📌 safe = 先保存 next

3️⃣ 直接遍历结构体（推荐）

struct node *p;

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

九、完整示例（驱动 / 内核风格）

struct my_node {
    int data;
    struct list_head list;
};

LIST_HEAD(my_list);

struct my_node *n1 = kmalloc(sizeof(*n1), GFP_KERNEL);
n1->data = 10;
INIT_LIST_HEAD(&n1->list);

list_add(&n1->list, &my_list);

struct my_node *pos;
list_for_each_entry(pos, &my_list, list) {
    printk("%d\n", pos->data);
}

十、Linux 链表的设计优势（必答）

优点说明
O(1) 插删双向
零额外开销无节点结构
高复用任意结构
cache 友好嵌入式

十一、常见坑（面试会问）

❌ 忘记初始化

list_add(new, head); // 野指针

❌ 删除时普通遍历

list_for_each(pos, head) {
    list_del(pos); // 崩
}

❌ 删除后继续使用

list_del(entry);
// entry->next 可能已失效

十二、一句话终极总结（背）

Linux 内核链表是侵入式双向循环链表，
用 list_head 组织结构，
用 container_of 找回数据，
用宏保证 O(1) 与高性能。

退出移动版