Linux 內核雙向循環鏈表深度解析（三）：核心數據結構與基礎操作

編輯：關於C語言

前言

Linux 內核鏈表 (list_head) 是「侵入式、無類型、循環雙向」的經典設計。本文 (上篇) 詳細講解 list_head 結構、初始化、節點增刪移、遍歷宏的實現原理與用法，並附帶完整用戶態可編譯示例。

核心設計思想

侵入式： 鏈表節點 list_head 嵌入業務結構體，而非業務數據嵌入節點。
無類型： list_head 只含 prev/next，通過 container_of / list_entry 反推宿主結構體指針。
循環雙向： 空鏈表 head->next == head && head->prev == head，操作統一無需特判頭尾。

關鍵數據結構

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

初始化宏

// 靜態初始化
#define LIST_HEAD_INIT(name) { &(name), &(name) }
#define LIST_HEAD(name) struct list_head name = LIST_HEAD_INIT(name)

// 動態初始化
#define INIT_LIST_HEAD(ptr) do { (ptr)->next = (ptr); (ptr)->prev = (ptr); } while(0)

內部底層插入 `__list_add`

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

在 prev 和 next 之間插入 new，prev/next/new 均不可為 NULL。

常用插入封裝

// 頭插法 (新節點變為第一個數據節點)
static inline void list_add(struct list_head *new, struct list_head *head) {
    __list_add(new, head, head->next);
}

// 尾插法 (新節點變為最後一個數據節點)
static inline void list_add_tail(struct list_head *new, struct list_head *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;
}

static inline void list_del(struct list_head *entry) {
    __list_del(entry->prev, entry->next);
    entry->next = LIST_POISON1; // 0x00100100
    entry->prev = LIST_POISON2; // 0x00200200
}

static inline void list_del_init(struct list_head *entry) {
    __list_del(entry->prev, entry->next);
    INIT_LIST_HEAD(entry); // 刪除後自構成空鏈表
}

毒化指針 (LIST_POISON1/2) 用於捕獲 Use-after-free：訪問已刪除節點會觸發頁錯誤。用戶態可改為 NULL。

移動節點

static inline void list_move(struct list_head *list, struct list_head *head) {
    __list_del(list->prev, list->next);
    list_add(list, head); // 移到頭部
}

static inline void list_move_tail(struct list_head *list, struct list_head *head) {
    __list_del(list->prev, list->next);
    list_add_tail(list, head); // 移到尾部
}

宿主結構體反推：`list_entry` / `container_of`

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

#define list_entry(ptr, type, member) container_of(ptr, type, member)

原理：(type*)0->member 取得成員在結構體中的**偏移量**，用 ptr - offset 反推宿主起始地址。

遍歷宏家族

// 正向遍歷 (含 prefetch 優化)
#define list_for_each(pos, head) \
    for (pos = (head)->next; prefetch(pos->next), pos != (head); pos = pos->next)

// 反向遍歷
#define list_for_each_prev(pos, head) \
    for (pos = (head)->prev; prefetch(pos->prev), pos != (head); pos = pos->prev)

// 安全遍歷 (允許刪除當前節點)
#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); \
         prefetch(pos->member.next), &pos->member != (head); \
         pos = list_entry(pos->member.next, typeof(*pos), member))

完整用戶態示例 (可直接編譯運行)

#include 
#include 
#include "list.h" // 需從內核源碼提取或自行實現上述宏

typedef struct {
    char name[20];
    int  num;
    struct list_head list;
} Student;

int main() {
    struct list_head head;
    INIT_LIST_HEAD(&head);
    Student *stu = calloc(5, sizeof(Student));

    for (int i=0; i<5; ++i) {
        sprintf(stu[i].name, "Stu%d", i+1);
        stu[i].num = i+1;
        list_add(&stu[i].list, &head); // 頭插，輸出逆序
    }

    // 遍歷打印
    struct list_head *pos;
    Student *s;
    list_for_each_entry(s, &head, list) {
        printf("num=%d name=%s\n", s->num, s->name);
    }
    // 輸出：5,4,3,2,1

    // 刪除第 3 個 (stu[2])
    list_del(&stu[2].list);
    // 移動 stu[4] 到尾部
    list_move_tail(&stu[4].list, &head);

    free(stu);
    return 0;
}