linux 内核 list 结构及相关接口 详解

list 结构在内核实现的位置：include/linux/list.h

1. 基本数据结构

Linux内核中的链表是通过 list_head 结构体实现的双向循环链表：

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

2. 链表组织形式图解

2.1 空链表

┌─────────────┐
│  list_head  │
├─────────────┤
│ next ────┐  │
│          │  │
│          ▼  │
│          ●──┼──┐
├─────────────┤  │
│          ●──┼──┘
│          ▲  │
│          │  │
│ prev ────┘  │
└─────────────┘

2.2 含有多个节点的链表

Next 指针循环：
    HEAD ─────next────▶ NODE1 ─────next────▶ NODE2 ─────next────▶ NODE3
     ▲                                                               │
     │                                                               │
     └───────────────────────────next───────────────────────────────┘
Prev 指针循环：
    HEAD ◀────prev───── NODE1 ◀────prev───── NODE2 ◀────prev───── NODE3
     │                                                               ▲
     │                                                               │
     └───────────────────────────prev───────────────────────────────┘

3. 核心接口详解

3.1 初始化操作

// 静态初始化
#define LIST_HEAD_INIT(name) { &(name), &(name) }
#define LIST_HEAD(name) \
    struct list_head name = LIST_HEAD_INIT(name)

// 动态初始化
static inline void INIT_LIST_HEAD(struct list_head *list)
{
    list->next = list;
    list->prev = list;
}

3.2 添加节点

// 在head后面插入new节点
static inline void list_add(struct list_head *new, struct list_head *head)
{
    __list_add(new, head, head->next);
}

// 在head前面插入new节点（尾部插入）
static inline void list_add_tail(struct list_head *new, struct list_head *head)
{
    __list_add(new, head->prev, head);
}

// 内部实现
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;
}

3.3 删除节点

static inline void list_del(struct list_head *entry)
{
    __list_del(entry->prev, entry->next);
    entry->next = LIST_POISON1;  // 防止重复删除
    entry->prev = LIST_POISON2;
}

static inline void __list_del(struct list_head *prev, struct list_head *next)
{
    next->prev = prev;
    prev->next = next;
}

3.4 遍历操作

// 基本遍历
#define list_for_each(pos, head) \
    for (pos = (head)->next; pos != (head); pos = pos->next)

// 安全遍历（允许删除当前节点）
#define list_for_each_safe(pos, n, head) \
    for (pos = (head)->next, n = pos->next; pos != (head); \
         pos = n, n = pos->next)

// 遍历并获取容器结构
#define list_for_each_entry(pos, head, member) \
    for (pos = list_entry((head)->next, typeof(*pos), member); \
         &pos->member != (head); \
         pos = list_entry(pos->member.next, typeof(*pos), member))

3.5 获取容器结构

// 从list_head成员获取包含它的结构体
#define list_entry(ptr, type, member) \
    container_of(ptr, type, member)

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

4. 示例代码

#include <linux/list.h>
#include <linux/kernel.h>
#include <linux/slab.h>

// 定义一个包含链表的结构体
struct student {
    char name[20];
    int id;
    struct list_head list;  // 链表节点
};

// 使用示例
void list_example(void)
{
    // 1. 初始化链表头
    LIST_HEAD(student_list);

    struct student *stu1, *stu2, *stu3;
    struct student *tmp;
    struct list_head *pos, *n;

    // 2. 分配并初始化节点
    stu1 = kmalloc(sizeof(struct student), GFP_KERNEL);
    strcpy(stu1->name, "Alice");
    stu1->id = 1001;
    INIT_LIST_HEAD(&stu1->list);

    stu2 = kmalloc(sizeof(struct student), GFP_KERNEL);
    strcpy(stu2->name, "Bob");
    stu2->id = 1002;
    INIT_LIST_HEAD(&stu2->list);

    stu3 = kmalloc(sizeof(struct student), GFP_KERNEL);
    strcpy(stu3->name, "Charlie");
    stu3->id = 1003;
    INIT_LIST_HEAD(&stu3->list);

    // 3. 添加到链表
    list_add(&stu1->list, &student_list);      // 头部插入
    list_add_tail(&stu2->list, &student_list); // 尾部插入
    list_add(&stu3->list, &stu1->list);        // 在stu1后面插入

    // 4. 遍历链表
    printk("Student list:\n");
    list_for_each_entry(tmp, &student_list, list) {
        printk("  Name: %s, ID: %d\n", tmp->name, tmp->id);
    }

    // 5. 删除一个节点
    list_del(&stu2->list);
    kfree(stu2);

    // 6. 安全遍历并删除所有节点
    list_for_each_safe(pos, n, &student_list) {
        tmp = list_entry(pos, struct student, list);
        list_del(pos);
        kfree(tmp);
    }

    // 7. 检查链表是否为空
    if (list_empty(&student_list)) {
        printk("List is empty\n");
    }
}

5. 链表操作图解

5.1 list_add 操作

Before:  HEAD ←→ NODE1 ←→ NODE2

After:   HEAD ←→ NEW ←→ NODE1 ←→ NODE2

5.2 list_add_tail 操作

Before:  HEAD ←→ NODE1 ←→ NODE2

After:   HEAD ←→ NODE1 ←→ NODE2 ←→ NEW

5.3 list_del 操作

Before:  HEAD ←→ NODE1 ←→ NODE2 ←→ NODE3

After:   HEAD ←→ NODE1 ←→ NODE3
         NODE2 (isolated)

6. 常用辅助函数

// 判断链表是否为空
static inline int list_empty(const struct list_head *head)
{
    return head->next == head;
}

// 判断一个链表节点是否是链表中的最后一个节点
static inline int list_is_last(const struct list_head *list,
                               const struct list_head *head)
{
    return list->next == head;
}

// 获取第一个/最后一个元素
#define list_first_entry(ptr, type, member) \
    list_entry((ptr)->next, type, member)

#define list_last_entry(ptr, type, member) \
    list_entry((ptr)->prev, type, member)

// 移动节点
static inline void list_move(struct list_head *list, struct list_head *head)
{
    __list_del(list->prev, list->next);
    list_add(list, head);
}

7. 优点总结

1. 侵入式设计：链表节点嵌入在数据结构中，避免额外的内存分配
2. 双向循环：支持双向遍历，操作灵活
3. 类型无关：通过宏和内联函数实现，适用于任何数据类型
4. 高效简洁：代码量少，执行效率高
5. 接口丰富：提供了完善的操作接口

Linux内核链表是一个优雅而高效的数据结构实现，广泛应用于内核的各个子系统中。