---
# System prepended metadata

title: 宏、Linux 內核鏈表
tags: [C]

---

---
title: '宏、Linux 內核鏈表'
disqus: kyleAlien
---

宏、Linux 內核鏈表
===

## OverView of Content


:::success
* 如果喜歡讀更好看一點的網頁版本，可以到我新做的網站 [**DevTech Ascendancy Hub**](https://devtechascendancy.com/)
    
    本篇文章對應的是 [**Linux 宏拓展 | offsetof、container_of 宏、鏈表 | 使用與分析**](https://devtechascendancy.com/linux-macro_offsetof_containerof_list/)
:::

[TOC]

## Linux 內核宏拓展

Linux 內核中有許多數據結構，其中鏈表就是其中之一，它與我們計己的計的鏈表不同，更注重於覆用

### offsetof 宏 - 使用、分析 

> 一般在訪問 struct 時，會透過「關鍵字 `.`」來訪問成員，這其是 **透過指標訪問，只是編譯器自動幫我們計算了結構頭到 ++目標成員的偏移量++**

* **offsetof 宏使用**：要手動計算就需要使用到 `offsetof` 宏，原型如下：
    ```c=
    // size_t 可以看作 int

    #define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
    ```
    
    使用 `offsetof` 宏的如下

    ```c=
    // 複製 offsetof 內核宏
    #define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)

    struct MyOffsetClass {
        int BookCount;
        short chairCount;
        char nickname[11];
    };

    void test_offsetof() {
        // 計算 nickname 在結構中的偏移量
        int offset = offsetof(struct MyOffsetClass, nickname);
        printf("offset: %d\n", offset);

        struct MyOffsetClass myClz;
        myClz.nickname[0] = 'Z';

        // 嘗試手動修改 offect 的數值，驗證是否正確
        char *pVal = ((char*) &myClz + offset);
        printf("pVal: %c\n", *pVal);

    }
    ```
    > ![](https://i.imgur.com/TORhtIw.png)

* **offsetof 宏分析**：可以拆解為以下步驟，這些步驟會有跟符號的結合的優先性有關，簡易的優先性如下表（由高到低）
    
    | 運算符號 | 描述 | 結合性 |
    | -------- | -------- | -------- |
    | () | 函數呼叫 |  |
    | [] | Array 引用 | 先於 `*` 符號結合 |
    | -> | 指標指向成員 | 左到右 |
    | . | Struct 成員引用 |  |
    | -/+ | 負號、正號 |  |
    | ++/-- | 遞增、遞減 |  |
    | ! | 邏輯否 |  |
    | ~ | 1 的補數 | 右到左 |
    | * | 指標引用 |  |
    | & | 記憶體位置 |  |
    | sizeof | 計算物件 Byte 大小 |  |
    | (type) | 強制轉型 |  |
    | * | 乘法 |  |
    | / | 除法 | 左到右 |
    | % | 取模 |  |
    | +/- | 加、減 | 左到右 |
    
    > 接下來我們來一步一步分析 `offsetof` 宏
    
    1. `(TYPE *)0` 強制轉型，轉型為指定 **特定類型（`TYPE`）指標**
    
    2. `((TYPE *)0)->MEMBER` 透過指標 **取得目標成員（`MEMBER`）**
    
    3. `&((TYPE *)0)->MEMBER` **取得成員（`MEMBER`）的地址**，這裡要注意結合順序，`->` 符號的結合優先度高於 `&` 符號
        
        :::success
        * 這個步驟等同於 `&((TYPE *)0)->MEMBER` 減去 `&((TYPE *)0)`，兩者相減得到偏移量 (也就是 `Target Member addr` - `Header addr`)

            | 結構成員 | 表示方法 |
            | -------- | -------- 
            | `Header member` | `(TYPE *)0` |
            | `Target Member` | `((TYPE *)0)->MEMBER` |

        :::
    
    4. `(size_t)` 最後強制轉型整數輸出，就變為指定結構變數的偏移量（`offset`）數值；
        
        以下我們測試一下這幾個步驟，是否可以算出成員的偏移量

        ```c=
        struct MyOffsetClass {
            int BookCount;
            short chairCount;
            char nickname[11];
        };

        void analyze_offset() {
            struct MyOffsetClass* ptr = (struct MyOffsetClass*) 0;

            // 將 0 轉為指定結構的指標
            printf("set ptr type, ptr addr: %p\n", ptr);
            
            // 使用 0 轉譯的指標，指向目標成員 nickname
            printf("target member addr: %p\n", ptr->nickname);
            
            // 取得 nickname 的地址
            printf("get member offset: %p\n", &(ptr)->nickname);
            
            // 轉為整數類型 int
            printf("finally offset: %p\n", (int) (&(ptr)->nickname));

        }
        ```
        > ![image](https://hackmd.io/_uploads/rkD0Yfh2a.png)


### container_of 宏 - 使用、分析

* 若我們知道一個 struct 其中的一個 member 的指標，就 **可以透過 `container_of` 宏 得到整個結構的 Header 指標**；其 `container_of` 原型如下：

    ```c=
    // 1. ptr:      指向成員的指標
    // 2. type:     目標結構
    // 3. member:   結構成員
    // 
    // 該宏返回的就是指向該結構體的 Ptr
    #define container_of(ptr, type, member) ({			\
        const typeof(((type *)0)->member) * __mptr = (ptr);	\
        (type *)((char *)__mptr - offsetof(type, member)); })
    ```

    :::success
    * **`typeof` 關鍵字**：

        透過 typeof(a) 得到變數 a 的**類型**，所以 **`typeof` 的其中一個作用就是由變量名得到變量的數據類型**
    :::
    
* **`container_of` 宏的使用如下**：說明請看以下註解

    ```c=
    // 複製 offsetof 內核宏
    #define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)

    // 複製 container_of 內核宏
    #define container_of(ptr, type, member) ({			\
        const typeof(((type *)0)->member) * __mptr = (ptr);	\
        (type *)((char *)__mptr - offsetof(type, member)); })


    struct ClassInformation {
        int BookCount;
        short chairCount;
        char nickName[11];
    };

    void test_container_of() {
        struct ClassInformation info;
        // 1. 直接印出 ClassInformation 結構的 Header 地址
        printf("ClassInformation head addr: %p\n", &info);

        // 2. 透過 container_of 取得 ClassInformation 結構的 Header 地址
        char* p = &info.nickName;
        struct ClassInformation *c = container_of(
            p,                     // ptr
            struct ClassInformation,     // type
            nickName);        // member
        printf("Use container_of get ClassInformation head addr: %p\n", c);
    }
    ```
    使用 `container_of` **可以求出原結構 Header 地址**
    > ![](https://i.imgur.com/mhn3K4W.png)


* **container_of 宏分析**：步驟也可以簡單拆解成幾個步驟，這裡分為兩個宏步驟分析講解 (請先了解上一小節的 `offsetof` 宏分析)
    ```c=
    // 1. ptr:      指向成員的指標
    // 2. type:     目標結構
    // 3. member:   結構成員

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

    
    1. **分析 `const typeof(((type *)0)->member) * __mptr = (ptr);`**：
        
        使用 typeof 取得變量類型，並宣告一個該類型的指標 `__mptr`；**經過這個步驟就取得指定結構的指定成員的地址**
    
        ```c=
        // 複製 container_of 內核宏的第一階段
        #define container_of_step_1(ptr, type, member)   const typeof(((type *)0)->member) * __mptr = (ptr)

        void test_container_of_step_1() {
            struct ClassInformation info;
            // 1. 直接印出 ClassInformation 結構的 Header 地址
            printf("ClassInformation head addr: %p\n", &info);

            // 2. 透過 container_of 取得 ClassInformation 結構的 Header 地址
            char* p = &info.nickName;

            container_of_step_1(
                    p,                     // ptr
                    struct ClassInformation,     // type
                    nickName);        // member

            printf("Step 1, get specific member address: %p\n", __mptr);
        }

        ```

        > 如下圖：我們可以透過自己定義的 `container_of_step_1` 宏取得 `ClassInformation` 結構的 `nickName` 的地址
        > 
        > ![image](https://hackmd.io/_uploads/Sk9Exmn3p.png)

        :::info
        * 可用 **`typeof` 關鍵字** 得到類型，再用該類型進行宣告

            > `((type *)0)->member` 相當於取出指定成員的地址，之後在透過 `typeof` 關鍵字得到該成員的類型
            > 
            > 以當前案例來講，nickName 的類型就是 char array
        :::
        
    2. **分析 `(type *)((char *)__mptr - offsetof(type, member));`**：
        
        將第一步的 `__mptr` 轉為指定類型的指標，再透過 `offsetof` 宏取得當前的偏移量，再與上面的指標相減，**最終就可以得到 struct 的 header 了**
    
        ```c=
        // 複製 container_of 內核宏的第一階段
        #define container_of_step_1(ptr, type, member)   const typeof(((type *)0)->member) * __mptr = (ptr)

        // 複製 container_of 內核宏的第二階段
        #define container_of_step_2(ptr, type, member)   (type *)((char *)__mptr - offsetof(type, member))
        void test_container_of_step_2() {
            struct ClassInformation info;
            // 1. 直接印出 ClassInformation 結構的 Header 地址
            printf("ClassInformation head addr: %p\n", &info);

            // 2. 透過 container_of 取得 ClassInformation 結構的 Header 地址
            char* p = &info.nickName;

            container_of_step_1(
                    p,                     // ptr
                    struct ClassInformation,     // type
                    nickName);        // member
            printf("Step 1, get specific member address: %p\n", __mptr);

            char * header= container_of_step_2(
                    p,                     // ptr
                    struct ClassInformation,     // type
                    nickName);        // member
            printf("Step 2, get struct header: %p\n", header);

        }
        ```

        > ![image](https://hackmd.io/_uploads/S1ZyZQ33T.png)


## Linux 內核鏈表 - 概述

Linux 內核鏈表實現了一個單純了鏈表結構 (雙向鏈表)，並包括了 `插入`、`刪除`、`迭代`... 等等功能，數據則是使用者填充 (這是最大的不同)


普通雙向鏈表必須鏈接上整個指定結構
> ![](https://i.imgur.com/ZRxVnh7.png)

Linux 內核只會指向結構中的特定成員
> ![](https://i.imgur.com/6TXQFiC.png)

### Linux 鏈表介紹：定義鏈表變量、操作鏈表

> Linux 鏈表的相關操作定義在 [**list.h**](https://elixir.bootlin.com/linux/latest/source/include/linux/list.h#L23) 中

1. **初始化鏈表**：以下有兩個方案 ^1.^ `LIST_HEAD_INIT`、^2.^ `LIST_HEAD`，兩者的差異在 `LIST_HEAD` 宏會幫你定義變數

    * 使用 `LIST_HEAD`  宏可以初始化鏈表結構 `list_head`，之後可以用來定義鏈表節點 `next`、`prev` 變數

        ```c=
        // types.h

        struct list_head {            // 個人覺得～ 這個結構更像是鏈表的節點
            struct list_head *next, *prev;
        };

        // ----------------------------------------------------------------------
        // list.h
        
        // 方案 1
        #define LIST_HEAD_INIT(name) { &(name), &(name) }    // 結構體賦值


        // 方案 2
        #define LIST_HEAD(name) \
            struct list_head name = LIST_HEAD_INIT(name)
        ```
    
    * 另外再多介紹一個 **`INIT_LIST_HEAD` 函數**：它可以為鏈表做初始化，也是將 `next`、`prev` 都指向自己
    
        ```c=
        static inline void INIT_LIST_HEAD(struct list_head *list)
        {
            // 等同於 list->next = list
            WRITE_ONCE(list->next, list);
            // 等同於 list->prev = list
            WRITE_ONCE(list->prev, list);
        }
        ```
        
        :::info
        * `WRITE_ONCE` 宏是針對個平台 CPU 架構的宏，用來確保該操作只被執行一次（這裡不特別介紹）
        :::
        
    
2. **插入節點**：插入鏈表節點的核心函數 `__list_add` 如下

    ```c=
    // list.h

    static inline void __list_add(struct list_head *new,
                      struct list_head *prev,
                      struct list_head *next)
    {
        if (!__list_add_valid(new, prev, next))    // 檢查是否合法 ( 先忽略
            return;

        next->prev = new;    // 1. next 指向新 Node 節點
        new->next = next;    // 2. 將新 Node 節點 next 指向原先的 next
        new->prev = prev;    // 3. 將新 Node 節點 prev 指向原先的 prev

        // 看成 prev->next = new;
        WRITE_ONCE(prev->next, new);    // 4. pre 指向新 Node 節點
    }
    ```
    > ![](https://i.imgur.com/BOJjQDG.png)

    * **`list_add` 函數**：插入 Header 之後

        ```c=
        static inline void list_add(struct list_head *new, struct list_head *head)
        {
            // @ 查看 __list_add
            // head 作為 pre
            // head->next 作為 next
            __list_add(new, head, head->next);
        }
        ```
        :::info
        * Header 不會變，往 Header 後面添加節點
        :::


    * **`list_add_tail` 函數**：插入 Tail，如同上面分析 `__list_add`，只不過傳入不同參數

        ```c=
        // list.h

        static inline void list_add_tail(struct list_head *new, struct list_head *head)
        {
            // 尾端插入
            // head->prev 作為 pre
            // head 作為 next
            __list_add(new, head->prev, head);
        }
        ```
        :::info
        * Header 的上一個 (`head->prev`) 就是最後一個節點，因為這是雙向鏈表！ 
        :::

### Linux 鏈表使用 - 添加節點實做

* 首先將 [**`list.h`**](https://elixir.bootlin.com/linux/v4.4/source/include/linux/list.h) 中幾個鏈表的實作、鏈表結構 (`list_head`) 簡化並複製過來測試、使用，如下

    ```c=
    #include <stdio.h>
    #include <stdlib.h>

    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)

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

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

    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 int list_empty(const struct list_head *head)
    {
        return head->next == head;
    }
    ```
    
* 接著我們來使用以上從 Linux 核心複製過來的宏，才做一些測試

    1. **初始化鏈表**：使用 `LIST_HEAD` 宏初始化，順便定義變數

        ```c=
        int main(void) {

            LIST_HEAD(MyList);     // 初始化並定義 MyList 變數

            return 0;
        }
        ```
        
    2. 測試該 Linked 鏈結，如果指向自己就代表列表為空
        ```c=
        void show_list_empty(void *ptr) {
            if(list_empty(ptr) == 1) {
                printf("list empty.\n");
            } else {
                printf("list not empty.\n");
            }
        }

        int main(void) {

            LIST_HEAD(MyList);

            // 測試列表是否為空
            show_list_empty(&MyList);

            return 0;
        }
        ```
        > ![image](https://hackmd.io/_uploads/SyZhU73nT.png)


    3. 添加節點再測試列表是否為空：首先定義一個結構，並且在該結構中加入鏈表結構 `list_head`（代表該結構是一個列表節點）

        ```c=
        struct MyBook {
            // 標示列表節點結構
            struct list_head list;
            
            void* content;
            int page;
            short catalog;
            char* book_name;
        };
        ```
        
        接著我們在指定列表（`MyList`）中添加兩個節點，在看看列表是否為空
        ```c=
        int main() {

            LIST_HEAD(MyList);    // 初始化

            show_list_empty(&MyList);

            struct MyBook java;
            list_add(&java, &MyList);    // 在 MyList 中添加 java 原素進列表
            printf("Add java book ~\n");

            struct MyBook c;
            list_add(&c, &MyList);    // 在 MyList 中添加 c 原素進列表
            printf("Add c programming book ~\n");

            show_list_empty(&MyList);
            return 0;
        }}
        ```
        > ![](https://i.imgur.com/EtZkFlo.png)


### Linux 鏈表使用 - 遍歷列表實做

* 我們繼續對鏈表測試，延續上一個小節，在這裡我們再添加兩個宏，用來遍歷列表（`list_for_each`）、取得列表子項目的結構 Headr 指標（`list_entry`）

    > `list_for_each` 是從 head 結構中的下一個元素開始遍歷元素，直至 header
    
    ```mermaid
    graph LR;
    
    
    subgraph 遍歷
    head(head 結束) --> |next| 元素1_開始 --> |next| 元素2 --> |next| 元素3 --> |next| head
    end
    ```
    
    ```c=
    #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_for_each(pos, head) \
        for (pos = (head)->next; pos != (head); pos = pos->next)

    #define list_entry(ptr, type, member) \
        container_of(ptr, type, member)
    ```
    
    :::danger
    * 這裡要特別提及一點：**請把 `list_head` 成員放置到結構的開頭，否則可能會計算偏移量錯誤、解釋結構錯誤**

        ```c=
        struct MyBook {
            // 列表結構，請放置到結構的開頭
            struct list_head list;      // 2 個指標 *next, *prev

            void* content;
            int page;
            short catalog;
            char* book_name;
        };
        ```
    :::

* **使用範例如下**：說明請看註解
    
    ```c=
    int main() {
        LIST_HEAD(MyList);    // 初始化列表

        struct MyBook java;
        java.book_name = "Learn Java\0";
        java.page = 333;
        list_add(&java, &MyList);    // 元素添加進進列表
        printf("java book header address: %p\n", &java);

        struct MyBook c;
        c.book_name = "Learn C\0";
        c.page = 222;
        list_add_tail(&c, &MyList);    // 元素添加進列表尾端
        printf("c book header address: %p\n", &c);

        printf("------ foreach MyList address: %p ------\n", &MyList);

        struct list_head* item;
        struct MyBook* book;
        list_for_each(item, &MyList) {
            // 透過 MyBook 結構中的 list_head 元素（也就是 item）
            // 來計算出該結構的開頭
            book = list_entry(item, struct MyBook, list);

            printf("Current item address: %p, book: %p\n", item, book);

            printf("Book(%s), page(%d).\n\n", book->book_name, book->page);
        }

        return 0;
    }
    ```
    
    > 
    > ![image](https://hackmd.io/_uploads/H12smU3nT.png)


## 更多的 C 語言相關文章

關於 C 語言的應用、研究其實涉及的層面也很廣闊，但主要是有關於到系統層面的應用（所以 C 語言又稱之為系統語言），為了避免文章過長導致混淆重點，所以將文章係分成如下章節來幫助讀者更好地從不同的層面去學習 C 語言

### C 語言基礎

* **C 語言基礎**：有關於到 C 語言的「語言基礎、細節」

    :::info
    * [**理解C語言中的位元操作：位元運算基礎與宏定義**](https://devtechascendancy.com/bitwise-operations-and-macros-in-c/)

    * [**C 語言解析：void 意義、NULL 意義 | main 函數調用、函數返回值意義 | 臨時變量的產生**](https://devtechascendancy.com/meaning_void_null_return-value_temp-vars/)

    * [**C 語言中的 Struct 定義、初始化 | 對齊、大小端 | Union、Enum**](https://devtechascendancy.com/c-struct_alignment_endianness_union_enum/)

    * [**C 語言儲存類別、作用域 | 修飾語、生命週期 | 連結屬性**](https://devtechascendancy.com/c-storage-scope-modifiers-lifecycle-linkage/)

    * [**指標 & Array & typedef | 指標應用的關鍵 9 點 | 指標應用、細節**](https://devtechascendancy.com/pointers-arrays-const-typedef-sizeof-null/)

    :::

### 編譯器、系統開念

* **編譯器、系統開念**：是學習完 C 語言的基礎（或是有一定的程度）之後，從編譯器以及系統的角度重新檢視 C 語言的一些細節

    :::warning
    * [**理解電腦記憶體管理 | 深入瞭解記憶體 | C 語言程式與記憶體**](https://devtechascendancy.com/computer-memory_manager-c-explained/)

    * [**C 語言記憶體區塊規劃 | Segment 段 | 字符串特性**](https://devtechascendancy.com/c-memory-segmentation-string-properties/)

    * [**編譯器的角度看程式 | 低階與高階、作業系統、編譯器、直譯器、預處理 | C語言函數探討**](https://devtechascendancy.com/compiler-programming-os-c-functions/)
    :::

### C 語言與系統開發

* **C 語言與系統開發**：在這裡會說明 C 語言的實際應用，以及系統為 C 語言所提供的一些函數、庫... 等等工具，看它們是如何實現、應用

    :::danger
    * [**了解 C 語言函式庫 | 靜態、動態函式庫 | 使用與編譯 | Library 庫知識**](https://devtechascendancy.com/understanding-c-library-static-dynamic/)

    * [**Linux 宏拓展 | offsetof、container_of 宏、鏈表 | 使用與分析**](https://devtechascendancy.com/linux-macro_offsetof_containerof_list/)
    :::
    
## Appendix & FAQ

:::info
:::

###### tags: `C`
