Linux 核心資料結構

Linux 的串列 API 是侵入式的：連結資訊嵌入由子系統擁有的物件中。侵入式設計移除個別節點配置，並讓一個物件參與數個索引，但容器 API 不擁有記憶體，也不提供同步。

循環雙向連結串列 #

struct list_head 只包含連結：

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

struct job {
    unsigned long id;
    struct list_head pending_link;
    struct list_head owner_link;
};

串列頭與嵌入節點具有相同型別。在空串列中，next 與 prev 都指回串列頭。在非空串列中，沿任一方向前進最終都會回到串列頭。因為串列頭是哨兵而不是承載資料的物件，迭代沒有 null 終止符。

一個物件可以透過不同成員出現在多個串列中。每個操作都必須指定正確成員；混用 pending_link 與 owner_link 會損壞兩個串列。

初始化與基本變更 #

宣告時使用 LIST_HEAD()，初始化現有物件時使用 INIT_LIST_HEAD()：

static LIST_HEAD(pending_jobs);

struct queue {
    spinlock_t lock;
    struct list_head jobs;
};

static void queue_init(struct queue *queue)
{
    spin_lock_init(&queue->lock);
    INIT_LIST_HEAD(&queue->jobs);
}

LIST_HEAD_INIT(name) 是初始化器運算式，適合放在較大的靜態初始化器內。任何串列操作前都必須完成初始化。

插入位置相對於哨兵：

list_add(&job->pending_link, &pending_jobs);      /* after head */
list_add_tail(&job->pending_link, &pending_jobs); /* before head */

list_add() 實作在前端的堆疊式插入；list_add_tail() 實作在後端的佇列式插入。list_move() 與 list_move_tail() 會解除現有節點的連結，並將它插入目的地的前端或尾端。

list_del() 會解除節點連結並毒化其連結，以暴露意外重複使用。分離節點必須再次成為有效、自連結的空節點時，使用 list_del_init()：

if (!list_empty(&pending_jobs)) {
    struct job *job =
        list_first_entry(&pending_jobs, struct job, pending_link);

    list_del_init(&job->pending_link);
    finish_job(job);
}

不要將一個連結成員加入兩次。自連結節點可以使用 list_empty(&job->pending_link) 檢查，但只有在每次移除都重新初始化節點時，該慣例才有效。

透過 container_of 恢復所有權 #

迭代器會抵達 struct list_head *，但子系統程式碼需要其包含物件。container_of(ptr, type, member) 會從 ptr 減去 member 的編譯期偏移，並保留編譯期型別檢查。list_entry() 專門化該模式：

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

struct job *job =
    list_entry(node, struct job, pending_link);

只有當 node 確實表示存活 struct job 的指定成員時，結果才有效。兩個巨集都不會執行動態型別驗證。

具型別迭代可避免明確轉換：

struct job *job;

list_for_each_entry(job, &pending_jobs, pending_link)
    run_job(job);

較少見的走訪模式有反向與接續變體。請選擇文件化且最窄的巨集，而不要自行撰寫 next 與 prev，因為巨集編碼了哨兵處理。

迭代時刪除 #

一般迭代會在迴圈主體後讀取目前節點的下一個連結。刪除目前節點會使該操作失效。_safe 迭代器會先儲存下一個物件：

struct job *job, *next;

list_for_each_entry_safe(job, next, &pending_jobs, pending_link) {
    if (job_cancelled(job)) {
        list_del(&job->pending_link);
        kfree(job);
    }
}

「安全」表示對此迴圈的刪除安全。它不會防護另一個 CPU、中斷或回呼修改串列，也不會建立 kfree() 合法的條件。外部參照可能需要參照計數、RCU 或其他生命週期協定。

拼接串列 #

拼接操作會以常數時間重新連結整個串列：

LIST_HEAD(batch);

build_batch(&batch);
list_splice_tail_init(&batch, &pending_jobs);

• list_splice() 在目的地串列頭之後插入。
• list_splice_tail() 在目的地串列頭之前插入。
• _init 變體也會重新初始化來源串列頭。

使用沒有 _init 的 list_splice() 後，來源串列頭仍會指向已轉移的鏈。將該來源視為獨立串列進行迭代可能會錯誤迴圈，因為其連結不再描述分開的循環串列。當所有權轉移且來源必須變空時，請使用 _init 變體。

list_cut_position() 會將前綴移至另一個串列頭。與每個串列變更一樣，呼叫者必須確保所有節點與串列頭都屬於預期串列。

雜湊單向連結串列 #

雜湊表需要許多 bucket 頭，因此 hlist 使用單指標串列頭：

struct hlist_head {
    struct hlist_node *first;
};

struct hlist_node {
    struct hlist_node *next;
    struct hlist_node **pprev;
};

struct cache_entry {
    unsigned long key;
    struct hlist_node hash_node;
};

pprev 指向指向該節點的連結：可能是 bucket 的 first 成員，或前一個節點的 next 成員。因此，刪除可以在常數時間內更新前驅連結，而不必儲存傳統的 prev 指標。非對稱表示法會在每個 bucket 頭節省一個指標，當表格有許多 bucket 時很重要。

static struct hlist_head table[256];

static void cache_insert(struct cache_entry *entry)
{
    unsigned int bucket = hash_long(entry->key, 8);

    hlist_add_head(&entry->hash_node, &table[bucket]);
}

static struct cache_entry *cache_find(unsigned long key)
{
    struct cache_entry *entry;

    hlist_for_each_entry(entry, &table[hash_long(key, 8)], hash_node)
        if (entry->key == key)
            return entry;
    return NULL;
}

程式依賴 hlist_unhashed() 時，使用 INIT_HLIST_NODE() 初始化獨立節點。使用 hlist_del_init() 進行移除後再使用，當目前迴圈會刪除項目時使用 hlist_for_each_entry_safe()。

並行與生命週期由呼叫者負責 #

串列與 hlist 操作是指標重寫，而非交易。API 不會隱含提供鎖、參照計數、用於發布承載欄位的記憶體屏障，或回收寬限期。子系統必須定義：

1. 哪一個鎖會序列化插入與刪除；
2. 哪些內容可以走訪容器；
3. 讀取者如何取得物件參照；
4. 被移除物件何時可以釋放。

當關鍵區段不能睡眠時，自旋鎖可以保護走訪與變更。在可睡眠程序內容中，互斥鎖較適合。對讀取為主的結構，list_add_rcu()、list_del_rcu() 與 hlist_for_each_entry_rcu() 等 RCU 特定 API 允許無鎖讀取者，但只能搭配必要的發布原語，以及寬限期後的延遲回收。沒有完整協定就混用一般與 RCU 變體並不安全。

_safe 迭代尾碼與 _rcu 尾碼解決不同問題：_safe 會在本機刪除期間保留迴圈游標，而 _rcu 會參與並行讀取者的生命週期方案。

參考資料 #

• 核心文件：連結串列
• 核心原始碼：include/linux/list.h
• 核心文件：RCU 串列 API