---
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);
}
```
> 
* **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));
}
```
> 
### 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 地址**
> 
* **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` 的地址
>
> 
:::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);
}
```
> 
## Linux 內核鏈表 - 概述
Linux 內核鏈表實現了一個單純了鏈表結構 (雙向鏈表)，並包括了 `插入`、`刪除`、`迭代`... 等等功能，數據則是使用者填充 (這是最大的不同)
普通雙向鏈表必須鏈接上整個指定結構
> 
Linux 內核只會指向結構中的特定成員
> 
### 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 節點
}
```
> 
* **`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;
}
```
> 
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;
}}
```
> 
### 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;
}
```
>
> 
## 更多的 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`
Sign in with Wallet
Connect another wallet