跳至主要内容

Linux Kernel Linked List

參考：https://hackmd.io/@sysprog/linux2025-lab0/%2F%40sysprog%2Flinux2025-lab0-a

Linux kernel 的 list_head（定義於 include/linux/list.h）是一個 intrusive、doubly、circular 的鏈結串列。

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

特色​

  • Intrusive（侵入式）：list_head 內嵌在使用者自己的 struct 裡，而非串列存資料指標。同一結構可同時掛在多個串列。
  • Circular（環狀）：head 的 prev 指向尾節點、尾節點 next 指回 head，插入刪除不需特判 NULL。
  • 空串列：head->next == head->prev == head。

container_of​

由成員指標回推整個外層 struct 的起始位址，是 intrusive list 取回資料的關鍵：

#define container_of(ptr, type, member) \
    ((type *)((char *)(ptr) - offsetof(type, member)))

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

常用巨集​

  • LIST_HEAD(name)：宣告並初始化一個串列 head。
  • list_add(new, head) / list_add_tail(new, head)：頭部 / 尾部插入。
  • list_del(entry)：刪除節點（O(1)）。
  • list_for_each(pos, head)：走訪每個 list_head 節點。
  • list_for_each_entry(pos, head, member)：直接走訪外層 struct，內部用 list_entry 取回。

走訪中若要刪除節點，需用 list_for_each_safe / list_for_each_entry_safe，先暫存 next 避免存取已釋放記憶體。