Linux 核心原始程式碼巨集: container_of

--- tags: LINUX KERNEL, LKI --- # Linux 核心原始程式碼巨集: `container_of` > 資料整理: [jserv](https://wiki.csie.ncku.edu.tw/User/jserv) :::success `container_of` 巨集在 Linux 核心原始程式碼出現將近 7 千次 (v5.13)，不僅在 linked list 和 hash table 一類通用資料結構中可簡化程式設計，甚至是 Linux 核心達成物件導向程式設計的關鍵機制之一。若要征服 Linux 核心原始程式碼，對 `container_of` 巨集的掌握度絕對要充分。 ::: ## 跟你想像不同的 `struct` 考慮以下 C 程式: ```c struct data { short a; char b; double c; }; ``` 假設依據 `struct data` 建立的物件為 `x`，也就是宣告為 `struct data x;`，給定指標 `char *p = (char *) &x;` 你或許會認為物件 `x` 在記憶體 (明確來說，是指虛擬記憶體分頁) 展現的樣貌如下圖: ![](https://i.imgur.com/NihOvLg.png) 也就是 `data` 這個結構體中，成員 `a` (型態為 `short` 整數) 佔 2 個位元組、成員 `b` (型態為 `char`，在 C 語言規格保證至少佔 1 個位元組)，以及緊接著出現的成員 `c` (型態為 `double`，在 C 語言規格中，至少需要 8 個位元組)。我們常借助示意圖來理解事物，但也可能無意間偏離事實。以下是測試程式碼 (檔名: `data.c`) ```c= #include <stdio.h> struct data { short a; char b; double c; }; int main() { struct data x = {.a = 25, .b = 'A', .c = 12.45}; char *p = (char *) &x; printf("a=%d\n", *((short *) p)); p += sizeof(short); printf("b=%c\n", *((char *) p)); p += sizeof(char); printf("c=%lf\n", *((double *) p)); return 0; } ``` 編譯和執行: ```shell $ gcc -o data data.c $ ./data ``` 輸出的前 2 行符合預期，即 `a=25` 和 `b=A`，但 `c=` 的輸出跟預期的 `12.45` 不同，為什麼呢？你或許會納悶： > 成員 `c` 在結構體 `data` 中，不就是自開頭位移 `sizeof(short)` (即成員 `a`) 和 `sizeof(char)` (即成員 `b`) 嗎？我們將第 15 行的 `return 0;` 換為以下程式碼: ```c=15 printf("p=%p, &x.c=%p\n", p, &(x.c)); ``` 在 Aarch64 (64 位元 Arm 架構) Linux 上執行會得到: (受限於 [ASLR](https://en.wikipedia.org/wiki/Address_space_layout_randomization)，每次執行結果都可能不同，這不影響我們判斷) ``` p=0xffffd6161a4b, &x.c=0xffffd6161a50 ``` 從執行結果可知，表示式 `(char *) &x + sizeof(short) + sizeof(char)` 和 `&(x.c)` 實際是不同的數值，既然指標內含值不同，進行 dereference (即 `*` 操作) 當然不會得到預期的輸出。問題出在我們忽略編譯器為了滿足 alignment 需求，進行的 [structure padding](http://www.catb.org/esr/structure-packing/)。解決方式之一，是修改上述程式碼的第 6 行，將 `};` 改為以下: ```c=6 } __attribute__((packed)); ``` 這裡的 `__attribute__((packed))` 是 GNU extension，引述 GCC 手冊 [Common Type Attributes](https://gcc.gnu.org/onlinedocs/gcc/Common-Type-Attributes.html): > This attribute, attached to a `struct`, `union`, or C++ `class` type definition, specifies that each of its members (other than zero-width bit-fields) is placed to minimize the memory required. This is equivalent to specifying the packed attribute on each of the members. 原來要額外加上 `packed` 屬性，結構體的成員實際排列和空間佔用才會跟程式碼順序一致，這是 C 語言程式設計其中一個陷阱，`packed` 過的結構體可能會犧牲資料存取的效率。 > 延伸閱讀: [你所不知道的 C 語言：記憶體管理、對齊及硬體特性](https://hackmd.io/@sysprog/c-memory) 為了提升程式碼的可攜性 (portability)，C89/C99 提供 [offsetof](https://man7.org/linux/man-pages/man3/offsetof.3.html) 巨集，可接受給定成員的型態及成員的名稱，傳回「成員的位址減去 struct 的起始位址」。示意如下: ![](https://i.imgur.com/DYiZ1sd.jpg) [offsetof](https://man7.org/linux/man-pages/man3/offsetof.3.html) 定義於 `<stddef.h>`，因此我們應該在第 1 行後面新增一行: ```c #include <stddef.h> ``` 再將上述程式碼的第 13 行的 `p += sizeof(char);` 敘述換為以下: ```c p = (char *) &x + offsetof(struct data, c); ``` 這樣無論結構體是否 `packed`，均可符合預期地執行。另外，如果你覺得 `offsetof(struct data, c)` 書寫很冗長，可換為: ```c offsetof(typeof(x), c) ``` 其中 [typeof](https://gcc.gnu.org/onlinedocs/gcc/Typeof.html) 也是 GNU extension，可在編譯時期得到物件 `x` 或 `*p` (型態也是 `struct data`) 的型態，這樣改寫後，我們就聚焦在「物件」和「成員名稱」。在一些老舊的編譯器，如 [Sun WorkShop Compiler](https://en.wikipedia.org/wiki/Oracle_Developer_Studio)，用以下方式定義 `offsetof` 巨集: ```c #define offsetof(TYPE, MEMBER) ((size_t) &((TYPE*)0)->MEMBER) ``` 但後來的 GCC 和 clang 就用 builtin function 取代，例如 `__builtin_offsetof`。Linux 核心原始程式碼 [include/linux/stddef.h](https://github.com/torvalds/linux/blob/master/include/linux/stddef.h) 定義 `offsetof` 巨集: ```c #ifdef __compiler_offsetof #define offsetof(TYPE, MEMBER) __compiler_offsetof(TYPE, MEMBER) #else #define offsetof(TYPE, MEMBER) ((size_t)&((TYPE *)0)->MEMBER) #endif ``` 上述程式碼已於 [commit 14e8307](https://github.com/torvalds/linux/commit/14e83077d55ff4b88fe39f5e98fb8230c2ccb4fb) 更改為： ```c #define offsetof(TYPE, MEMBER) __builtin_offsetof(TYPE, MEMBER) ``` 在較新的 GCC 中，對應有效的 `__compiler_offsetof` 巨集。當巨集展開時，針對老舊的編譯器可能會成為 `(size_t)&((TYPE *)0)->MEMBER` 敘述，其原理是先將 TYPE 型態結構體的地址變更為 `0`，然後再加上成員 `MEMBER` 的偏移量。值得思忖的是，`&((TYPE *)0)->MEMBER中` 這樣對地址為 `0` 的記憶體區域進行操作，難道不會導致程式崩潰嗎？答案是，不會！編譯器處理 `&((TYPE *)0)->MEMBER` 時，不會真正去存取地址為 `0` 的記憶體區段，只是將 `0` 看做指標操作的一個運算元，除非額外有 dereference 操作。 ## `container_of` 巨集作為資料封裝的基礎巨集 `container_of` 則在 [offsetof](https://man7.org/linux/man-pages/man3/offsetof.3.html) 的基礎上，擴充為「給定成員的位址、struct 的型態，及成員的名稱，傳回此 struct 的位址」，以下是示意圖 ![](https://i.imgur.com/IgayoN9.jpg) 請不要小看這巨集，畢竟大量在 Linux 核心原始程式碼採用的巨集，應有其獨到之處。在 `container_of` 巨集出現前，程式設計的思維往往是: 1. 給定結構體起始地址 2. 求出結構體特定成員的記憶體內容 3. 傳回結構體成員的地址，作日後存取使用 `container_of` 巨集則逆轉上述流程，特別在 C 語言程式設計中，我們通常會定義一系列公開介面 (interface)，從而區隔各式實作 (implementation)。更明確來說，考慮以下 UML: ![](https://i.imgur.com/Ck9NHy3.png) `Object` 作為抽象的展現，是所有衍生物件的基底，`Vehicle` 正如其寓意，泛指交通工具，而 `Car` 和 `Truck` 就是特定的交通工具「模板」。在 C 語言可用以下程式碼描述: ```c typedef struct { int ref; } Object; typedef struct { Object base; /* Vehicle-specific members */ } Vehicle; typedef struct { Vehicle base; /* Car-specific members */ } Car; void vehicleStart(Vehicle *obj) { if (obj) printf("%x derived from %x\n", obj, obj->base); } int main(void) { Car c; vehicleStart((Vehicle *) &c); } ``` > 完整程式碼: [doxygen-oop-in-c](https://github.com/jserv/doxygen-oop-in-c) 這段程式碼雖然只是印出物件之間的「繼承」關係，但蘊含重要的特性: * `Car` 是實作本體，無論結構體再複雜，都有 `base` 這個成員，其型態為 `Vehicle` * 同理，`Vehicle` 也包含一個 `base` 成員，後者的型態為 `Object` * `Object` 是公開介面，內部只有 `ref` 成員，可充當 [reference counting](https://en.wikipedia.org/wiki/Reference_counting) 使用，本例沒有特別意義於是，只要依循同樣的規則，無論有多少 `Car`, `Truck` 或更多的交通工具「模板」，我們都可藉由結構體的 `base` 成員，得知繼承關係，從而存取到上一層的公開資訊。物件導向程式設計的「封裝」(encapsulation)、繼承 (inheritance)，和多型 (polymorphism) 都可運用這樣的手法來達成。 > 延伸閱讀: [你所不知道的 C 語言：物件導向程式設計篇](https://hackmd.io/@sysprog/c-oop) 舉例來說，Linux 核心內建 V4L2 (video for Linux APIs, version 2) 框架來提供豐富的 Linux 多媒體處理，原始程式碼 [drivers/media/i2c/imx214.c](https://github.com/torvalds/linux/blob/master/drivers/media/i2c/imx214.c) 則是其中一個裝置驅動程式，部分程式碼列表如下: ```c struct imx214 { struct device *dev; ... struct v4l2_ctrl_handler ctrls; ... }; static int imx214_set_ctrl(struct v4l2_ctrl *ctrl) { struct imx214 *imx214 = container_of(ctrl->handler, struct imx214, ctrls); ... /* Applying V4L2 control value only happens * when power is up for streaming */ if (!pm_runtime_get_if_in_use(imx214->dev)) return 0; ... } static const struct v4l2_ctrl_ops imx214_ctrl_ops = { .s_ctrl = imx214_set_ctrl, }; ``` 顯然，定義在 [drivers/media/i2c/imx214.c](https://github.com/torvalds/linux/blob/master/drivers/media/i2c/imx214.c) 的結構體 `imx214` 是 imx214 這個裝置驅動程式特有的定義，在其他 C 程式也無從得知，但 `v4l2_` 開頭的結構體則是 V4L2 框架的公開介面，上述程式碼的 `imx214_set_ctrl` 函式最終會被註冊為 V4L2 的一個實作，利用 `container_of` 巨集，我們就可隱藏 imx214 實作細節，但又能存取到 `imx214` 結構體的開頭，從而繼續存取到其他實作相關的成員。 > 延伸閱讀: [解析 Linux 共享記憶體機制](https://hackmd.io/@sysprog/linux-shared-memory) 也許乍看這沒什麼了不起，又不是語言糖 (syntax sugar)，也不是什麼神奇的演算法，但我們見識到 Linux 核心開發者追求的「優雅」 —— 清晰地界定介面和實作本體。 ## `container_of` 實作手法關於 `container_of` 巨集的實作手法，可參見下圖: ![](https://i.imgur.com/6h0Bgax.jpg) 對應的原始程式碼如下: ```c /* container_of() - Calculate address of object that contains address ptr * @ptr: pointer to member variable * @type: type of the structure containing ptr * @member: name of the member variable in struct @type * * Return: @type pointer of object containing ptr */ #define container_of(ptr, type, member) \ __extension__({ \ const __typeof__(((type *) 0)->member) *(__pmember) = (ptr); \ (type *) ((char *) __pmember - offsetof(type, member)); \ }) ``` 解析巨集的過程中，我們可留意 `__extension__`，依據 GCC 手冊 [Alternate Keywords](https://gcc.gnu.org/onlinedocs/gcc/Alternate-Keywords.html) > `-pedantic` and other options cause warnings for many GNU C extensions. You can prevent such warnings within one expression by writing `__extension__` before the expression. `__extension__` has no effect aside from this. 儘管 GCC 幾乎支援 C 和 C++ 最新的規格，但仍考慮到傳統 C 程式 (即最廣泛支援的 [ANSI C](https://en.wikipedia.org/wiki/ANSI_C) C89 或 C90，注意: C90 和 C89 幾乎一致，差別在於 C90 納入 ISO/IEC 9899:1990 標準時，進行格式和排版調整)，提供 `-pedantic` 編譯選項，讓編譯器主動提醒開發者，是否用到 C89/C90 以外的特徵。由於上述巨集用到 [typeof](https://gcc.gnu.org/onlinedocs/gcc/Typeof.html) 這個 GNU extension，於是特別用 `__extension__` 標注，避免 GCC 搭配 `-pedantic` 編譯選項時，會拋出警告訊息。上述程式碼是從 struct 中的 member 推算出原本 struct 的位址。解析: * 先透過 `__typeof__` 得到 type 中的成員 `member` 的型別，並宣告一個指向該型別的指標 `__pmember` * 將 `ptr` 指派到 `__pmember` * `__pmember` 目前指向的是 `member` 的位址 * `offsetof(type, member)` 可得知 `member` 在 `type` 這個結構體位移量，即 offset * 將絕對位址 `(char *) __pmember` 減去 `offsetof(type, member)` ，可得到結構體的起始位址。計算 offset 時要轉成 `char *`，以確保 address 的計算符合預期 (可參考 [The (char *) casting in container_of() macro in linux kernel](https://stackoverflow.com/questions/20421910/the-char-casting-in-container-of-macro-in-linux-kernel) 的說明) * 最後 `(type *)` 再將起始位置轉型為指向 `type` 的指標 > 延伸閱讀: > * [你所不知道的 C 語言：指標篇](https://hackmd.io/@sysprog/c-pointer) > * [你所不知道的 C 語言：技巧篇](https://hackmd.io/@sysprog/c-trick) 值得留意的是，Linux 核心原始程式碼提供的 `container_of` 巨集定義事實上更複雜: ```c= #define container_of(ptr, type, member) ({ \ void *__mptr = (void *)(ptr); \ BUILD_BUG_ON_MSG(!__same_type(*(ptr), ((type *)0)->member) && \ !__same_type(*(ptr), void), \ "pointer type mismatch in container_of()"); \ ((type *)(__mptr - offsetof(type, member))); }) ``` 第 3 行藉由 `BUILD_BUG_ON_MSG` 巨集達到 static assert 的作用，儘量在編譯時期就查驗 `container_of` 巨集的使用是否合法：預先進行指標型態的檢查 > 延伸閱讀: [Linux 核心巨集: BUILD_BUG_ON_ZERO](https://hackmd.io/@sysprog/c-bitfield) 關於 `__same_type` 巨集，可見 [include/linux/compiler_types.h](https://github.com/torvalds/linux/blob/master/include/linux/compiler_types.h): ```c /* Are two types/vars the same type (ignoring qualifiers)? */ #define __same_type(a, b) __builtin_types_compatible_p(typeof(a), typeof(b)) ``` 同樣是運用 GNU extension 達成。 ## 應用案例: 雙向環狀鏈結串列接下來，我們仿效 Linux 核心 [include/linux/list.h](https://github.com/torvalds/linux/blob/master/include/linux/list.h) 的精簡雙向環狀鏈結串列 (circular doubly-linked list，以下簡稱 `list`) 實作。關鍵概念是，將結構體 `list_head` 嵌入到所需的結構體中，再藉由 `container_of` 巨集得知 list 個別節點的地址。示意如下圖: ![](https://i.imgur.com/kOvwKZw.png) 自 `Head` 開始，鏈結 list 各節點，個別節點皆嵌入 `list_head` 結構體，不過 `Head` 是個特例，無法藉由 `container_of` 巨集來找到對應的節點，因為後者並未嵌入到任何結構體之中，其存在是為了找到 list 整體。程式碼列表: ```c #include <stddef.h> /* struct list_head - Head and node of a doubly-linked list * @prev: pointer to the previous node in the list * @next: pointer to the next node in the list */ struct list_head { struct list_head *prev, *next; }; /* LIST_HEAD - Declare list head and initialize it * @head: name of the new object */ #define LIST_HEAD(head) struct list_head head = {&(head), &(head)} /* INIT_LIST_HEAD() - Initialize empty list head * @head: pointer to list head */ static inline void INIT_LIST_HEAD(struct list_head *head) { head->next = head; head->prev = head; } /* list_add_tail() - Add a list node to the end of the list * @node: pointer to the new node * @head: pointer to the head of the list */ static inline void list_add_tail(struct list_head *node, struct list_head *head) { struct list_head *prev = head->prev; prev->next = node; node->next = head; node->prev = prev; head->prev = node; } /* list_del() - Remove a list node from the list * @node: pointer to the node */ static inline void list_del(struct list_head *node) { struct list_head *next = node->next, *prev = node->prev; next->prev = prev; prev->next = next; } /* list_empty() - Check if list head has no nodes attached * @head: pointer to the head of the list */ static inline int list_empty(const struct list_head *head) { return (head->next == head); } /* list_is_singular() - Check if list head has exactly one node attached * @head: pointer to the head of the list */ static inline int list_is_singular(const struct list_head *head) { return (!list_empty(head) && head->prev == head->next); } /* list_splice_tail() - Add list nodes from a list to end of another list * @list: pointer to the head of the list with the node entries * @head: pointer to the head of the list */ static inline void list_splice_tail(struct list_head *list, struct list_head *head) { if (list_empty(list)) return; struct list_head *head_last = head->prev; struct list_head *list_first = list->next, *list_last = list->prev; head->prev = list_last; list_last->next = head; list_first->prev = head_last; head_last->next = list_first; } /* list_cut_position() - Move beginning of a list to another list * @head_to: pointer to the head of the list which receives nodes * @head_from: pointer to the head of the list * @node: pointer to the node in which defines the cutting point */ static inline void list_cut_position(struct list_head *head_to, struct list_head *head_from, struct list_head *node) { struct list_head *head_from_first = head_from->next; if (list_empty(head_from)) return; if (head_from == node) { INIT_LIST_HEAD(head_to); return; } head_from->next = node->next; head_from->next->prev = head_from; head_to->prev = node; node->next = head_to; head_to->next = head_from_first; head_to->next->prev = head_to; } /* list_entry() - Calculate address of entry that contains list node * @node: pointer to list node * @type: type of the entry containing the list node * @member: name of the list_head member variable in struct @type */ #define list_entry(node, type, member) container_of(node, type, member) /* list_first_entry() - get first entry of the list * @head: pointer to the head of the list * @type: type of the entry containing the list node * @member: name of the list_head member variable in struct @type */ #define list_first_entry(head, type, member) \ list_entry((head)->next, type, member) /* list_for_each - iterate over list nodes * @node: list_head pointer used as iterator * @head: pointer to the head of the list */ #define list_for_each(node, head) \ for (node = (head)->next; node != (head); node = node->next) ``` 上方程式碼的好處在於，只要 `list_head` 納入新的結構體的一個成員，即可操作，且不用自行維護一套 doubly-linked list 。 ![](https://i.imgur.com/d3bG8t6.png) > 延伸閱讀: [Linux 鏈結串列 struct list_head 研究](https://myao0730.blogspot.com/2016/12/linux.html) 注意到 `list_entry` 利用 `container_of` 巨集，藉由 `struct list_head` 這個公開介面，「反向」去存取到自行定義的結構體開頭地址。以下為圖解: - [ ] `list_head` 結構體 ```c struct list_head { struct list_head *prev, *next; }; ``` ```graphviz digraph list_head { rankdir=LR; node[shape=record, style=bold]; head [label="{<prev>prev|<next>next}"]; } ``` - [ ] 在自行定義的結構體置入 `list_head` 物件 ```c typedef struct { char *value; struct list_head list; } my_data; ``` ```graphviz digraph list { rankdir=LR; node[shape=record, style=bold]; subgraph cluster_0 { node [shape=record]; value [label="{value}"]; head [label="{<prev>prev|<next>next}"]; style=bold; label=my_data } } ``` 簡化為下圖： ```graphviz digraph list_ele { rankdir=LR; node[shape=record]; node [shape=record]; head [label="value|{<left>prev|<right>next}", style=bold]; } ``` - [ ] `LIST_HEAD - Declare list head and initialize it` ```c #define LIST_HEAD(head) struct list_head head = {&(head), &(head)} ``` ```graphviz digraph list_init { rankdir=LR; node[shape=record]; style=bold node [shape=record]; head [label="{<left>prev|<right>next}", style="bold"]; head:right:e -> head:left:w[arrowhead=normal, arrowtail=normal, dir=both]; } ``` - [ ] `list_entry() - Calculate address of entry that contains list node` ```c #define list_entry(node, type, member) container_of(node, type, member) ``` ```graphviz digraph container { rankdir=LR; node[shape=record]; compound=true; style=bold; subgraph cluster_0 { container [label = "container" style=filled,color=white]; subgraph cluster_1 { node [shape=record]; element [label="|{|}", style="bold"]; label = "member" } } element -> container[ltail=cluster_1, lhead=cluster_0]; } ``` - [ ] `list_for_each - iterate over list nodes` ```c #define list_for_each(node, head) \ for (node = (head)->next; node != (head); node = node->next) ``` ```graphviz digraph ele_list { rankdir=LR; node[shape=record]; h [label="head", style=dashed, color=grey]; h -> e1:right:w [style=dashed, color=grey]; e1 [label="head node|{<left>prev|<right>next}", style="bold", color=grey]; e2 [label="cat|{<left>prev|<right>next}", style="bold"]; e3 [label="...", style="bold"]; e4 [label="eat|{<left>prev|<right>next}", style="bold"]; e5 [label="fat|{<left>prev|<right>next}", style="bold"]; e1:right:e -> e2:left:w[arrowhead=normal, arrowtail=normal, dir=both]; e2:right:e -> e3:left:w[arrowhead=normal, arrowtail=normal, dir=both]; e3:right:e -> e4:left:w[arrowhead=normal, arrowtail=normal, dir=both]; e4:right:e -> e5:left:w[arrowhead=normal, arrowtail=normal, dir=both]; e5:right:e -> e1:left:w[arrowhead=normal, arrowtail=normal, dir=both]; } ``` > 延伸閱讀: [你所不知道的C語言: linked list 和非連續記憶體操作](https://hackmd.io/@sysprog/c-linked-list)

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.