Posted inC 作業系統 程式語言

Linux 宏拓展 | offsetof、container_of 宏、鏈表 | 使用與分析

No CommentsPosted inC, 作業系統, 程式語言
Linux 宏拓展 | offsetof、container_of 宏、鏈表 | 使用與分析

OverView of Content

本文將探討 Linux 核心程式設計中常用的宏拓展以及鏈表概念。

首先，我們將介紹兩個關鍵的 Linux 核心宏拓展：offsetof 巨集（宏）和 container_of 巨集（宏）。透過分析這兩個巨集的使用方法和原理，讀者將了解如何在核心程式設計中利用它們來實現高效的資料結構操作。

接著，我們將深入了解 Linux 核心中常用的鏈表概念。我們將介紹 Linux 核心中提供的鍊錶實現，即 list.h 頭檔中定義的鍊錶結構。我們將討論如何使用這些鍊錶操作，包括如何新增節點和遍歷清單。透過學習鍊錶的概念和使用方法，讀者將能夠更深入地理解 Linux 核心程式設計中的資料結構和演算法。

Linux 內核宏拓展

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

offsetof 宏：使用、分析

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

● offsetof 宏使用：要手動計算就需要使用到 offsetof 宏，原型如下：


// size_t 可以看作 int

#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)

使用 offsetof 宏的如下


// 複製 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);

}

● offsetof 宏分析：可以拆解為以下步驟，這些步驟會有跟符號的結合的優先性有關，簡易的優先性如下表（由高到低）

運算符號描述結合性
()函數呼叫
[]Array 引用先於 * 符號結合
->指標指向成員左到右
.Struct 成員引用
-/+負號、正號
++/–遞增、遞減
!邏輯否
~1 的補數右到左
*指標引用
&記憶體位置
sizeof計算物件 Byte 大小
(type)強制轉型
*乘法
/除法左到右
%取模
+/-加、減左到右

接下來我們來一步一步分析 offsetof 宏

A. (TYPE *)0 強制轉型，轉型為指定 特定類型（TYPE）指標

B. ((TYPE *)0)->MEMBER 透過指標 取得目標成員（MEMBER）

C. &((TYPE *)0)->MEMBER 取得成員（MEMBER）的地址，這裡要注意結合順序，-> 符號的結合優先度高於 & 符號

● 這個步驟等同於 &((TYPE *)0)->MEMBER 減去 &((TYPE *)0)，兩者相減得到偏移量 (也就是 Target Member addr - Header addr)

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

D. (size_t) 最後強制轉型整數輸出，就變為指定結構變數的偏移量（offset）數值；

以下我們測試一下這幾個步驟，是否可以算出成員的偏移量


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

}

container_of 宏：使用、分析

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


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

● typeof 關鍵字：

透過 typeof(a) 得到變數 a 的類型，所以 typeof 的其中一個作用就是由變量名得到變量的數據類型

● container_of 宏的使用如下：說明請看以下註解


// 複製 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 地址

● container_of 宏分析：步驟也可以簡單拆解成幾個步驟，這裡分為兩個宏步驟分析講解 (請先了解上一小節的 offsetof 宏分析)


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

A. 分析 const typeof(((type *)0)->member) * __mptr = (ptr);：

使用 typeof 取得變量類型，並宣告一個該類型的指標 __mptr；經過這個步驟就取得指定結構的指定成員的地址


// 複製 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 的地址

● 可用 typeof 關鍵字 得到類型，再用該類型進行宣告

((type *)0)->member 相當於取出指定成員的地址，之後在透過 typeof 關鍵字得到該成員的類型

以當前案例來講，nickName 的類型就是 char array

B. 分析 (type *)((char *)__mptr - offsetof(type, member));：

將第一步的 __mptr 轉為指定類型的指標，再透過 offsetof 宏取得當前的偏移量，再與上面的指標相減，最終就可以得到 struct 的 header 了


// 複製 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);

}

Linux 內核鏈表

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

普通雙向鏈表必須鏈接上整個指定結構

Linux 內核只會指向結構中的特定成員

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

Linux 鏈表的相關操作定義在 list.h 中

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

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


// 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 都指向自己


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

● WRITE_ONCE 宏是針對個平台 CPU 架構的宏，用來確保該操作只被執行一次（這裡不特別介紹）

B. 插入節點：插入鏈表節點的核心函數 __list_add 如下


// 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 節點
}

● list_add 函數：插入 Header 之後


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

● Header 不會變，往 Header 後面添加節點

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


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

● Header 的上一個 (head->prev) 就是最後一個節點，因為這是雙向鏈表！

Linux 鏈表使用：實做添加節點

● 首先將 list.h 中幾個鏈表的實作、鏈表結構 (list_head) 簡化並複製過來測試、使用，如下


#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 核心複製過來的宏，才做一些測試

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


int main(void) {

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

    return 0;
}

B. 測試該 Linked 鏈結，如果指向自己就代表列表為空


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

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


struct MyBook {
    // 標示列表節點結構
    struct list_head list;
    
    void* content;
    int page;
    short catalog;
    char* book_name;
};

接著我們在指定列表（MyList）中添加兩個節點，在看看列表是否為空


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

Linux 鏈表使用：實做遍歷列表

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

list_for_each 是從 head 結構中的下一個元素開始遍歷元素，直至 header

graph LR; subgraph 遍歷 head(head 結束) --> |next| 元素1_開始 --> |next| 元素2 --> |next| 元素3 --> |next| head end 

#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)

● 這裡要特別提及一點：請把 list_head 成員放置到結構的開頭，否則可能會計算偏移量錯誤、解釋結構錯誤


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

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

● 使用範例如下：說明請看註解


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

更多的 C 語言相關文章

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

C 語言基礎

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

● 理解C語言中的位元操作：位元運算基礎與宏定義

● C 語言解析：void 意義、NULL 意義 | main 函數調用、函數返回值意義 | 臨時變量的產生

● C 語言中的 Struct 定義、初始化 | 對齊、大小端 | Union、Enum

● C 語言儲存類別、作用域 | 修飾語、生命週期 | 連結屬性

● 指標 & Array & typedef | 指標應用的關鍵 9 點 | 指標應用、細節

編譯器、系統開念

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

● 理解電腦記憶體管理 | 深入瞭解記憶體 | C 語言程式與記憶體

● C 語言記憶體區塊規劃 | Segment 段 | 字符串特性

● 編譯器的角度看程式 | 低階與高階、作業系統、編譯器、直譯器、預處理 | C語言函數探討

C 語言與系統開發

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

● 了解 C 語言函式庫 | 靜態、動態函式庫 | 使用與編譯 | Library 庫知識

● Linux 宏拓展 | offsetof、container_of 宏、鏈表 | 使用與分析

Tags:
Leave a Comment

Comments

No comments yet. Why don’t you start the discussion?

發表迴響